Depth First Search (DFS) Algorithm

Description: -

The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.

• In this technique we start from a given vertex v and then mark it as visited.

• A vertex is said to be explored when all the vertices adjacent to it are visited.

• An vertex adjacent to v are put at the top of a stack next.

• The top vertex of this stack is explored next.

• Exploration continues until no unexplored vertices are left.

• The search process can be described recursively.

For example: DFS of this graph will be 1, 2, 4, 8, 5, 6, 3, 7

Algorithm: -

DFS(v)
{
 visited[v] = true;
 // visited is an array of vertices
 // visited so far, all elements are 0 initially
 for all vertices w adjacent to v do
 {
  if (!visited[w])
   DFS(w);
 }
}

Program: -

#include<stdio.h>
int graph[20][20]={0},visited[20]={0},n;
//this code is written by Monish Kumar Bairagi
void dfs(int v){
 int i;
 visited[v]=1;
 printf("%d ",v);
 for(i=1;i<=n;i++){
  if(graph[v][i]==1 && visited[i]==0){
   dfs(i);
  }
 }
}
//this code is written by Monish Kumar Bairagi
int main()
{
 int m,i,j,k;
 printf("Enter total no of vertices: "); scanf("%d",&n);
 printf("Enter total no of Edges: "); scanf("%d",&m);
 printf("Enter connected vertices:-\n");
 for(k=0;k<m;k++){
  printf("Enter U V: "); scanf("%d%d",&i,&j);
  graph[i][j]=1; graph[j][i]=1;
 }
 printf("Enter Starting vertex: "); scanf("%d",&k);
 printf("The DFS Solution of the Graph will be: ");
 dfs(k); printf("\n");
 return 0;
}

Output: -

Enter total no of vertices: 8
Enter total no of Edges: 10
Enter connected vertices:-
Enter U V: 1 2
Enter U V: 1 3
Enter U V: 2 4
Enter U V: 2 5
Enter U V: 3 6
Enter U V: 3 7
Enter U V: 4 8
Enter U V: 5 8
Enter U V: 6 8
Enter U V: 7 8
Enter Starting vertex: 1
The DFS Solution of the Graph will be: 1 2 4 8 5 6 3 7

Time-Complexity: -

O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.