Graph Traversal using Depth First Search (DFS)

As its name suggests, is to search deeper into the graph, whenever possible. Given as input graph G = (V, E) and a source vertex S, from where the searching starts. First, we visit the starting node, then we travel through each node along a path, which begins at S. We visit a neighbour vertex of S and again a neighbour of a neighbour of S, and so on.

DFS Through Stack

In this method, a stack is used to keep track of unvisited neighbours of the node. But the question is that how can we distinguish the visited and unvisited nodes? Take another Boolean array VISITED, which will show the visited and unvisited nodes. Let's see the procedure and how it works?

Procedure

1.Push starting node into the stack.
2.Pop an element from the stack, if it has not been traversed then traverse it.
If it has already been traversed then just ignore it. after traversing make the 
value of visited array true for this node. 
3.Push all the unvisited adjacent nodes of the popped element on stack. No need to
Push the element even if it is already on the stack.
4. Repeat step 2 and 3 until stack is empty.      				   

Let's consider an example to clarify this method which is shown in the following Fig 1.

Fig 1.

Suppose, the starting node is 1.

Push(1)

Stack content:1

Pop()

Stack content:empty

visited[1] = TRUE

Push all the unvisited adjacent nodes 2, 5, 4 into the stack.

Stack content:2, 5, 4 and Top = 2

Pop()

Stack content:2, 5 and Top = 1

visited[4] = TRUE

Push adjacent nodes of 4. But there is no adjacent node.

Stack content:2,5 and Top = 1

Pop()

Stack content:2 and Top = 0

visited[5] = TRUE

Push unvisited adjacent nodes of 5.Adjacent node of 5 is 4 which is already visited.

Stack content:2 and Top = 0

Pop()

Stack content:empty and Top = -1

visited[2] = TRUE

Push unvisited node of 2.

Stack content:3 and Top = 0

Pop()

Stack content:empty and Top = -1

visited[3] = TRUE

Stack is empty and there is no adjacent node of 3.So we stop the process.

Finally, the DFS traversal is:

1, 4, 5, 2, 3

DFS Using Color Scheme

First, we will see the procedure and then we will understand the method by a suitable example which is shown in Fig 2.

Procedure

 DFS(G)
 for each vertex u &belongs; V[G] do
        color[u]<-white
        π[u]<-NIL
 time<-0
 for each vertex u &belongs; V[G] do
        if color[u]= white then
            DFS-VISIT(u)      

 DFS-VISIT(u)
 color[u]<-gray
 time<-time+1
 d[u]<-time
 for each v &belongs; Adj[u] do
     if color[v]=white then
         π[v]<-v
         DFS-VISIT(v)
 color[u]<-black
 time<-time+1
 f(u)<-time                                                             

Source code

#include <stdio.h> #include <stdlib.h> typedef struct listnode { int data; struct listnode* next; } listnode; typedef struct list { listnode *head; } list; typedef struct graph { int vertices; list* array; } graph; int visited[1000]; graph* creategraph(int n) { int i; graph* G=(graph *)(malloc(sizeof(graph))); G->vertices = n; G->array = (list *)malloc(n * sizeof(struct list)); for(i=0;i<n;i++) G->array[i].head = NULL; return G; } void addedge(graph* G, int src, int dest) { listnode* newnode; newnode=(listnode *)(malloc(sizeof(listnode))); newnode->data=dest; newnode->next=G->array[src].head; G->array[src].head=newnode; } void traverse(graph* G, int n) { graph* temp=G; int i; list* temp_list; listnode* temp_node; for(i=0;i<n;i++) { temp_node=temp->array[i].head; printf("[%d]->",i); while(temp_node!=NULL) { printf("%d ->", temp_node->data); temp_node=temp_node->next; } printf("NULL"); printf("\n"); } return; } void dfs(graph* G, int v) { int i, j; printf("%d ", v); visited[v]=1; listnode* temp_node=G->array[v].head; while(temp_node!=NULL) { if(!visited[temp_node->data]) { dfs(G,temp_node->data); } temp_node=temp_node->next; } } int main() { int n, i, j, k, temp, m, a, b; printf("Enter the number of nodes : "); scanf("%d",&n); printf("Enter the number of edges : "); scanf("%d",&m); printf("\nEnter the edges for creating adjacency list "); int ini=n+1; graph* G=creategraph(n+1); for(i=0;i<m;i++) { printf("\nenter the source and destination of an edge:"); scanf("%d%d",&a,&b); addedge(G,a,b); if(a<ini) ini=a; } printf("Traversing the adjacency list : \n"); traverse(G,n); printf("\nDFS traversal starting with %d : \n", ini); dfs(G,ini); return 0; }

Happy Exploring!