Graph Traversal | Depth first Search (DFS)

Graph Traversal

-> Graph traversal is a process of checking or updating each vertex in a graph.
-> It is also known as Graph Search.
-> Graph traversal means visiting each and exactly one node.
-> Tree traversal is a special case of graph traversal.

There are two techniques used in graph traversal-

1. Depth First Search (DFS)
2. Breadth First Search (BFS)



1. Depth First Search

-> Depth first search (DFS) is used for traversing a finite graph.

-> DFS traverses the depth of any particular path before exploring its breadth.

-> It explores one subtree before returning to the current node and then exploring the other subtree.

-> DFS uses stack instead of queue.

-> It traverses a graph in a depth-ward motion and gets the next vertex to start a search when a dead end occurs in any iteration.



/* C program to implement DFS (Depth first Search) */

#include<stdio.h>
void DFS(int i);
int visited[10],a[10][10],n;
int main()
{
int i,j;
printf("Enter number of Vertices:");
scanf("%d",&n);
printf("Enter adjacency matrix of the graph:");
for(i=0; i<n; i++)
for(j=0; j<n; j++)
scanf("%d",&a[i][j]);
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
int j;
printf("%d\t",i);
visited[i]=1;
for(j=0; j<n; j++)
if(visited[j]==0 && a[i][j]==1)
DFS(j);
}


OUTPUT:

Enter number of Vertices:5
Enter adjacency matrix of the graph:
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0

0       1       2       3       4