DAA- DFS – Depth First Search

DFS – Depth First Search

Depth First Search (DFS) Algorithm

In the depth-first search (DFS) algorithm, firstly we traverse from the starting node of the graph G’, from there we extend our traversing down till we discover the desired node or the last node which is not having any child nodes to traverse. From the desired node the algorithm starts backtracking towards the latest node that is yet to be traversed.

Stack(Data structure) is being used in this DFS algorithm. The procedure is similar to that of a BFS algorithm.

Algorithm

• Step 1: PUT REPORT = 1 (start state) for each node in G’
• Step 2: Push the starting node A on the stack and put its REPORT = 2 (on hold state)
• Step 3: Repeat Steps 4 and 5 until STACK is empty
• Step 4: Pop the top node N. Process it and set its REPORT = 3 (activity state)
• Step 5: Push on the stack all the neighbors of N that are in the ready state (whose REPORT = 1) and set their
  REPORT = 2 (waiting state)
  [END OF LOOP]
• Step 6: EXIT

Example : 

 In the figure given below, consider the graph G’ along with its neighboring list. By using a depth-first search (DFS) algorithm, look after the sequence to print all the nodes of the graph starting from node H.

Solution :

Push H onto the stack

STACK : H   

POP the topmost element of the stack i.e. H, print it and push all the neighbors of H onto the stack that are in the start state.

Print H

STACK : A   

Pop the topmost element of the stack i.e. A, print it, and push all the neighbors of A onto the stack that are in the start state.

Print A  

Stack : B, D  

Pop the topmost element of the stack i.e. D, print it, and push all the neighbors of D onto the stack that are in the start state.

Print D  

Stack : B, F   

Pop the top most element of the stack i.e. F, print it and push all the neighbors of F onto the stack that are in the start state.

Print F  

Stack : B  

Pop the top of the stack i.e. B and push all the neighbors.

Print B   

Stack : C   

Pop the top of the stack i.e. C and push all the neighbors.

Print C   

Stack : E, G   

Pop the top of the stack i.e. G and push all the neighbors.

Print G  

Stack : E  

Pop the top of the stack i.e. E and push all the neighbors.

Print E  

Stack :  

Finally, the stack is empty now and all the nodes of the graph G’  have been explored.

The output series of the graph will be :

H → A → D → F → B → C → G → E  

#include<stdio.h>
#include<conio.h>
int b[20][20],traverse[20],n;
void dfs(int node) {
int x;
traverse[node]=1;
for (x=1;x<=n;x++)
  if(b[node][x] && !traverse[x]) {
printf("\n %d->%d",node,x);
dfs(i);
}
}
void main() {
int x,y,flag=0;
clrscr();
printf("\n Enter number of vertices of the graph:");
scanf("%d",&n);
for (x=1;x<=n;x++) {
traverse[x]=0;
for (y=1;y<=n;y++)
   b[x][y]=0;
}
printf("\n Enter the neighboring matrix:\n");
for (x=1;x<=n;x++)
  for (y=1;y<=n;y++)
   scanf("%d",&b[x][y]);
dfs(1);
printf("\n");
for (x=1;x<=n;x++) {
if traverse[x])
   flag++;
}
if(flag==n)
  printf("\n Graph is attached"); 
         else
  printf("\n Graph is not attached");
getch();
}