Depth First Search or DFS for a Graph | DSA in C++ - Software Development PDF Download

Introduction

Overview of DFS

• DFS is a graph traversal algorithm that explores a graph by visiting vertices in a depthward motion.
• It starts at a specified source vertex and explores as far as possible along each branch before backtracking.
• DFS can be implemented using recursion or an iterative approach using a stack data structure.
• It is widely used for solving problems like finding connected components, detecting cycles, and solving mazes.

DFS Implementation in C++

To implement DFS, we need to represent the graph using an adjacency list or matrix. Here, we will use an adjacency list representation. We will also maintain a visited array to keep track of visited vertices.

C++ Code (Recursive DFS):

#include <iostream>

#include <vector>

using namespace std;

// Function to perform DFS recursively

void dfsUtil(vector<vector<int>>& graph, int v, vector<bool>& visited) {

    visited[v] = true;

    cout << v << " ";

    for (int u : graph[v]) {

        if (!visited[u]) {

            dfsUtil(graph, u, visited);

        }

    }

}

// Function to initialize DFS and handle disconnected components

void dfs(vector<vector<int>>& graph, int V) {

    vector<bool> visited(V, false);

    for (int v = 0; v < V; ++v) {

        if (!visited[v]) {

            dfsUtil(graph, v, visited);

        }

    }

}

// Driver code

int main() {

    int V = 5; // Number of vertices

    vector<vector<int>> graph(V);

    // Adding edges to the graph

    graph[0].push_back(1);

    graph[0].push_back(2);

    graph[1].push_back(2);

    graph[2].push_back(0);

    graph[2].push_back(3);

    graph[3].push_back(3);

    cout << "DFS traversal: ";

    dfs(graph, V);

    return 0;

}

Output:

DFS traversal: 0 1 2 3

Examples and Code Explanation

Let's go through two examples to understand how DFS works.

Example 1: Simple Connected Graph

Consider the following graph:

     0

    / \

   1   2

      / \

     3   3

The code provided in the previous section will produce the DFS traversal output: 0 1 2 3.

Explanation:

• We start with vertex 0 and mark it as visited.
• We then move to its adjacent vertices, which are 1 and 2. We choose vertex 1 and mark it as visited.
• Next, we explore the adjacent vertices of vertex 1, but it has no neighbors.
• We backtrack and move to vertex 2, marking it as visited.
• Vertex 2 has two adjacent vertices: 0 and 3. Since vertex 0 is already visited, we move to vertex 3 and mark it as visited.
• Finally, vertex 3 has no unvisited neighbors, and we backtrack to vertex 2.
• The DFS traversal order is 0 1 2 3.

Example 2: Disconnected Graph

Consider the following graph:

     0         3

    / \

   1   2

   4   5

The code provided in the previous section will produce the DFS traversal output: 0 1 2 3 4 5.

Explanation:

• We start with vertex 0 and mark it as visited.
• We then move to its adjacent vertices, which are 1 and 2. We choose vertex 1 and mark it as visited.
• Next, we explore the adjacent vertices of vertex 1, but it has no neighbors.
• We backtrack and move to vertex 2, marking it as visited.
• Vertex 2 has no unvisited neighbors, so we backtrack to vertex 0.
• Since vertex 3 is unvisited, we move to it and mark it as visited.
• Vertex 3 has no unvisited neighbors, so we backtrack to vertex 0.
• We move to vertex 4 and mark it as visited.
• Vertex 4 has no unvisited neighbors, so we backtrack to vertex 0.
• Finally, we move to vertex 5 and mark it as visited.
• Vertex 5 has no unvisited neighbors, and we backtrack to vertex 0.
• The DFS traversal order is 0 1 2 3 4 5.

Sample Problems and Solutions

Problem 1: Given an undirected graph, find the number of connected components.

• Initialize a counter variable to 0.
• Use the DFS algorithm to traverse the graph, incrementing the counter for each disconnected component encountered.
• The final counter value will represent the number of connected components.

Problem 2: Given a directed graph, check if it contains a cycle.

• Use the DFS algorithm to traverse the graph.
• Maintain a visited array and a recursion stack to detect cycles.
• If, during the DFS traversal, we encounter a vertex that is already visited and is present in the recursion stack, a cycle is detected.

Conclusion

Depth-First Search (DFS) is a powerful graph traversal algorithm used to explore graphs systematically. In this article, we provided a beginner's guide to DFS, explaining its basic concepts and providing a C++ implementation. We covered examples and code explanations to help you understand the algorithm better. Additionally, we presented sample problems and solutions to demonstrate the practical applications of DFS. By mastering DFS, you will be equipped to solve a wide range of graph-related problems efficiently.