DAA: Depth-First Search Algorithm

Depth-first search: DFS is a traversing algorithm of a graph or tree in which one node is taken as arbitrary, and with the help of that arbitrary node, all its branches are explored.

How can we Traverse?

Step 1 - Pick a node and visit the adjacent unvisited vertex of the picked node and mark it as visited. Print it and push it in the stack.

Step 2 - If there is no adjacent vertex, pop it from the stack.

Step 3 - Repeat steps 1 and 2 until the stack is empty.

Example

Currently, we have an empty stack.

S is the root node picked and marked visited, also pushed in the stack. Now we look for the vertices adjacent to S. There are three nodes A, B, C. We take them in alphabetical order and start pushing in the stack.

We had reached A marked as visited and pushed into the stack. A has one adjacent node D.

We visit D and push it into the stack after marking it as visited. Now D does not have an adjacent vertex as it is the leaf node in the graph. Therefore, our A vertex is wholly traversed. Now we will come back as we have B and C to be visited.

We come at B, push it into the stack after marking it as visited. Since B also has an adjacent node D, but since D is marked as visited in previous steps, B does not have any unvisited adjacent node. So we will backtrack.

    Check the top of the stack for any previous adjacent nodes.

Now we come to C, which is the last unvisited node. We mark it visited and push it to the stack. Since C does not have any adjacent unvisited nodes, the graph is wholly traversed.

We start to pop the stack until we find any unvisited node of an adjacent vertex in the stack. Since there is no adjacent unvisited vertex, the stack is popped upto an empty size.

Graph for code

                 1

               /   \

              2     3

             / \   / \

            4   5 6   7

C++ code -

#include <iostream> 
#include <vector> 
#include <stack>   
using namespace std;   
class Graph 
{     
int numberVertex; // Number of nodes in graph     
vector<int>* adjacency;   
public:     // Constructor to initialize graph     
Graph(int numberVertex)    
 {       
  this->numberVertex = numberVertex;        
 adjacency = new vector<int>[numberVertex];    
 }      
 // Function to add edge between source and destination    
 void addEdge(int source, int destination)    
 {         
adjacency[source].push_back(destination);   
  }     
  // Function to perform Depth First Search    
 void dfs(int starting); };   
void Graph::dfs(int starting) 
{    
 bool visited[numberVertex];     // Mark visited array as false intially     
for (int i = 0; i < numberVertex; i++)         visited[i] = false;      
 stack<int> stack_vertex;      
 visited[starting] = true;    
 stack_vertex.push(starting); // Push current node       
vector<int>::iterator it;     // Iterate all visited nodes    
 while (!stack_vertex.empty()) 
{        
 starting = stack_vertex.top();       
  cout << starting << " ";        
 stack_vertex.pop();           
for (it = adjacency[starting].begin(); it != adjacency[starting].end(); ++it) 
{           
  if (!visited[*it])
 {              
   visited[*it] = true;              
   stack_vertex.push(*it);            
 }        
 }    
 } 
}  
 int main() 
{  
   // Number of vertices is 8     Graph graph(8);     
  // Create edges between vertices     
   graph.addEdge(1, 2);  
   graph.addEdge(2, 1);   
   graph.addEdge(2, 4);    
   graph.addEdge(4, 2);     
   graph.addEdge(2, 5);    
   graph.addEdge(5, 2);  
   graph.addEdge(1, 3);    
   graph.addEdge(3, 1);    
   graph.addEdge(3, 6);    
   graph.addEdge(6, 3);    
   graph.addEdge(3, 7);    
   graph.addEdge(7, 3);    
   cout << "Depth First Traversal is : ";    
 graph.dfs(1);    
   return 0; 
}

Output:

Depth First Traversal is: 1 3 7 6 2 5 4

 C code :

#include <stdio.h> 
#include <stdlib.h>   //Structure for each vertex in graph struct node 
{     
int data;    
 struct node* next;
 };   //Function to add a node at the end of a given root struct node* 
insert(struct node* root, int d) 
{    
 struct node* newPtr = (struct node*)malloc(sizeof(struct node));     
newPtr->data = d;     
newPtr->next = NULL;       
root->next = newPtr;       
return newPtr; 
}   //Function to perform DFS void explore(int node, int vis[], struct node start[]) 
{    
 printf("%d ", node);     vis[node] = 1;       struct node* ptr = start[node].next;       
for (; ptr != NULL; ptr = ptr->next) {         if (vis[ptr->data] == 0) 
{            
 explore(ptr->data, vis, start);         
}   
  } 
}   
int main() 
{    
 int no_of_vertices = 7, i, vis[8];       struct node start[8];     
  for (i = 1; i <= no_of_vertices; i++) 
{       
  start[i].data = i;         start[i].next = NULL;         vis[i] = 0;    
 }          
 /*     Creates the following graph :                 
                         1               
                       /   \              
                      2     3             
                     / \   / \           
                    4   5 6   7     
*/     
struct node* cur;    
 cur = insert(&start[1], 2);     
insert(cur, 3);    
 cur = insert(&start[2], 4);     
insert(cur, 5);    
 cur = insert(&start[3], 6);     
insert(cur, 7);       //The loop takes care of non connected graph also    
 printf("DFS of the graph : \n");    
 for (i = 1; i <= 7; i++) 
{         
if (vis[i] == 0)            
 explore(i, vis, start);  
   }       
return 0;   
}

Output : 1 2 4 5 3 6 7