Depth First Search (DFS) C++ Program To Traverse A Graph Or Tree

This Tutorial Covers Depth First Search (DFS) in C++ in Which A Graph or Tree is Traversed Depthwise. You will Also Learn DFS Algorithm & Implementation:

Depth-first search (DFS) is yet another technique used to traverse a tree or a graph.

DFS starts with a root node or a start node and then explores the adjacent nodes of the current node by going deeper into the graph or a tree. This means that in DFS the nodes are explored depth-wise until a node with no children is encountered.

Once the leaf node is reached, DFS backtracks and starts exploring some more nodes in a similar fashion.

=> Watch Out The Beginners C++ Training Guide Here.

Depth First Search (DFS) In C++

Unlike BFS in which we explore the nodes breadthwise, in DFS we explore the nodes depth-wise. In DFS we use a stack data structure for storing the nodes being explored. The edges that lead us to unexplored nodes are called ‘discovery edges’ while the edges leading to already visited nodes are called ‘block edges’.

Next, we will see the algorithm and pseudo-code for the DFS technique.

DFS Algorithm

• Step 1: Insert the root node or starting node of a tree or a graph in the stack.
• Step 2: Pop the top item from the stack and add it to the visited list.
• Step 3: Find all the adjacent nodes of the node marked visited and add the ones that are not yet visited, to the stack.
• Step 4: Repeat steps 2 and 3 until the stack is empty.

Pseudocode

The pseudo-code for DFS is given below.

From the above pseudo-code, we notice that the DFS algorithm is called recursively on each vertex to ensure that all the vertices are visited.

Traversals With Illustrations

Let us now illustrate the DFS traversal of a graph. For clarity purposes, we will use the same graph that we used in the BFS illustration.

Let 0 be the starting node or source node. First, we mark it as visited and add it to the visited list. Then we push all its adjacent nodes in the stack.

Next, we take one of the adjacent nodes to process i.e. the top of the stack which is 1. We mark it as visited by adding it to the visited list. Now look for the adjacent nodes of 1. As 0 is already in the visited list, we ignore it and we visit 2 which is the top of the stack.

Next, we mark node 2 as visited. Its adjacent node 4 is added to the stack.

Next, we mark 4 which is the top of the stack as visited. Node 4 has only node 2 as its adjacent which is already visited, hence we ignore it.

At this stage, only node 3 is present in the stack. Its adjacent node 0 is already visited, hence we ignore it. Now we mark 3 as visited.

Now the stack is empty and the visited list shows the sequence of the depth-first traversal of the given graph.

If we observe the given graph and the traversal sequence, we notice that for the DFS algorithm, we indeed traverse the graph depth-wise and then backtrack it again to explore new nodes.

Depth-First Search Implementation

Let’s implement the DFS traversal technique using C++.

#include <iostream> 
#include <list> 
using namespace std; 
//graph class for DFS travesal  
class DFSGraph 
{ 
int V;    // No. of vertices 
list<int> *adjList;    // adjacency list 
void DFS_util(int v, bool visited[]);  // A function used by DFS 
public: 
    // class Constructor
DFSGraph(int V)
    {
 this->V = V; 
 adjList = new list<int>[V]; 
    }
    // function to add an edge to graph 
void addEdge(int v, int w){
adjList[v].push_back(w); // Add w to v’s list.
    }
    
void DFS();    // DFS traversal function 
}; 
void DFSGraph::DFS_util(int v, bool visited[]) 
{ 
    // current node v is visited 
visited[v] = true; 
cout << v << " "; 
  
    // recursively process all the adjacent vertices of the node 
list<int>::iterator i; 
for(i = adjList[v].begin(); i != adjList[v].end(); ++i) 
if(!visited[*i]) 
DFS_util(*i, visited); 
} 
  
// DFS traversal 
void DFSGraph::DFS() 
{ 
    // initially none of the vertices are visited 
bool *visited = new bool[V]; 
for (int i = 0; i < V; i++) 
visited[i] = false; 
  
    // explore the vertices one by one by recursively calling  DFS_util
for (int i = 0; i < V; i++) 
if (visited[i] == false) 
DFS_util(i, visited); 
} 
  
int main() 
{ 
    // Create a graph
DFSGraph gdfs(5); 
gdfs.addEdge(0, 1); 
gdfs.addEdge(0, 2); 
gdfs.addEdge(0, 3);
gdfs.addEdge(1, 2); 
gdfs.addEdge(2, 4);
gdfs.addEdge(3, 3); 
gdfs.addEdge(4, 4);

cout << "Depth-first traversal for the given graph:"<<endl; 
gdfs.DFS(); 
  
return 0; 
}

Output:

Depth-first traversal for the given graph:

0 1 2 4 3

We have once again used the graph in the program that we used for illustration purposes. We see that the DFS algorithm (separated into two functions) is called recursively on each vertex in the graph in order to ensure that all the vertices are visited.

Runtime Analysis

The time complexity of DFS is the same as BFS i.e. O (|V|+|E|) where V is the number of vertices and E is the number of edges in a given graph.

Similar to BFS, depending on whether the graph is scarcely populated or densely populated, the dominant factor will be vertices or edges respectively in the calculation of time complexity.

Iterative DFS

The implementation shown above for the DFS technique is recursive in nature and it uses a function call stack. We have another variation for implementing DFS i.e. “Iterative depth-first search”. In this, we use the explicit stack to hold the visited vertices.

We have shown the implementation for iterative DFS below. Note that the implementation is the same as BFS except the factor that we use the stack data structure instead of a queue.

#include<bits/stdc++.h> 
using namespace std; 
  
// graph class
class Graph 
{ 
int V;    // No. of vertices 
list<int> *adjList;    // adjacency lists 
public: 
Graph(int V)  //graph Constructor 
    {
this->V = V; 
adjList = new list<int>[V]; 
    }
void addEdge(int v, int w) // add an edge to graph 
    {
adjList[v].push_back(w); // Add w to v’s list. 
    }
void DFS();  // DFS traversal
  
    // utility function called by DFS 
void DFSUtil(int s, vector<bool> &visited); 
}; 
  
//traverses all not visited vertices reachable from start node s
void Graph::DFSUtil(int s, vector<bool> &visited) 
{ 
    // stack for DFS 
stack<int> dfsstack; 
   // current source node inside stack 
dfsstack.push(s); 
  
while (!dfsstack.empty()) 
    { 
        // Pop a vertex  
        s = dfsstack.top(); 
       dfsstack.pop(); 
  
        // display the item or node only if its not visited 
 if (!visited[s]) 
        { 
cout << s << " "; 
visited[s] = true; 
        } 
  
        // explore all adjacent vertices of popped vertex. 
        //Push the vertex to the stack if still not visited
for (auto i = adjList[s].begin(); i != adjList[s].end(); ++i) 
if (!visited[*i]) 
dfsstack.push(*i); 
    } 
}
// DFS 
void Graph::DFS() 
{ 
    // initially all vertices are not visited 
vector<bool> visited(V, false); 
  
for (int i = 0; i < V; i++) 
if (!visited[i]) 
DFSUtil(i, visited); 
} 
  
//main program
int main() 
{ 
    Graph gidfs(5);  //create graph 
gidfs.addEdge(0, 1); 
gidfs.addEdge(0, 2); 
gidfs.addEdge(0, 3);
gidfs.addEdge(1, 2); 
gidfs.addEdge(2, 4);
gidfs.addEdge(3, 3); 
gidfs.addEdge(4, 4);
 
cout << "Output of Iterative Depth-first traversal:\n"; 
gidfs.DFS(); 
  
return 0; 
}   

Output:

Output of Iterative Depth-first traversal:

0   3   2   4   1

We use the same graph that we used in our recursive implementation. The difference in output is because we use the stack in the iterative implementation. As the stacks follow LIFO order, we get a different sequence of DFS. To get the same sequence, we might want to insert the vertices in the reverse order.

BFS vs DFS

So far we have discussed both the traversal techniques for graphs i.e. BFS and DFS.

Now let us look into the differences between the two.

Applications Of DFS

• Detecting Cycles In The Graph: If we find a back edge while performing DFS in a graph then we can conclude that the graph has a cycle. Hence DFS is used to detect the cycles in a graph.
• Pathfinding: Given two vertices x and y, we can find the path between x and y using DFS. We start with vertex x and then push all the vertices on the way to the stack till we encounter y. The contents of the stack give the path between x and y.
• Minimum Spanning Tree And Shortest Path: DFS traversal of the un-weighted graph gives us a minimum spanning tree and shortest path between nodes.
• Topological Sorting: We use topological sorting when we need to schedule the jobs from the given dependencies among jobs. In the computer science field, we use it mostly for resolving symbol dependencies in linkers, data serialization, instruction scheduling, etc. DFS is widely used in Topological sorting.

Conclusion

In the last couple of tutorials, we explored more about the two traversal techniques for graphs i.e. BFS and DFS. We have seen the differences as well as the applications of both the techniques. BFS and DFS basically achieve the same outcome of visiting all nodes of a graph but they differ in the order of the output and the way in which it is done.

We have also seen the implementation of both techniques. While BFS uses a queue, DFS makes use of stacks to implement the technique.  With this, we conclude the tutorial on traversal techniques for graphs. We can also use BFS and DFS on trees.

We will learn more about spanning trees and a couple of algorithms to find the shortest path between the nodes of a graph in our upcoming tutorial.

=> See Here To Explore The Full C++ Tutorials list.