ALGORITHM DFS(G)
//Implements a depth-first search traversal of a given graph//Input: GraphG = V , E//Output: Graph G with its vertices marked with consecutive integers
// in the order they are first encountered by the DFS traversal
mark each vertex inV with 0 as a mark of being “unvisited”
count ← 0
for each vertex v in V do
if v is marked with 0
DFS(v)
DFS(v)//visits recursively all the unvisited vertices connected to vertex v
//by a path and numbers them in the order they are encountered
//via global variable count
count← count + 1; mark v with count
for each vertex w in V adjacent to v do
if w is marked with 0
DFS(w)
C program:
#include<stdio.h>
int a[20][20],reach[20],n;
void dfs(int v)
{
int i;
reach[v]=1;
for (i=0;i<n;i++)
if (a[v][i]&&!reach[i])
{
printf("\n %d->%d",v,i);
dfs(i);
}
}
int main()
{
int i,j,count=0;
printf("Enter The Number OF Vertices\n");
scanf("%d",&n);
for (i=0;i<n;i++)
{
reach[i]=0;
for (j=0;j<n;j++)
{
a[i][j]=0;
}
}
printf("Enter The Adjacency Matrix\n");
for (i=0;i<n;i++)
for (j=0;j<n;j++)
{
printf("\nEnter connection bt vertex %c & vertex %c",i+65,j+65);
scanf("%d",&a[i][j]);
}
dfs(0);
printf("\n");
for (i=0;i<n;i++)
{
if (reach[i])
count++;
}
if (count==n)
printf("The Graph is connected\n");
else
printf("The Graph is not Connected\n");
return 0;
}
Output:
Enter The Number OF Vertices
5
Enter The Adjacency Matrix
Enter connection bt vertex A & vertex A0
Enter connection bt vertex A & vertex B1
Enter connection bt vertex A & vertex C0
Enter connection bt vertex A & vertex D0
Enter connection bt vertex A & vertex E1
Enter connection bt vertex B & vertex A1
Enter connection bt vertex B & vertex B0
Enter connection bt vertex B & vertex C1
Enter connection bt vertex B & vertex D0
Enter connection bt vertex B & vertex E0
Enter connection bt vertex C & vertex A0
Enter connection bt vertex C & vertex B1
Enter connection bt vertex C & vertex C0
Enter connection bt vertex C & vertex D1
Enter connection bt vertex C & vertex E0
Enter connection bt vertex D & vertex A0
Enter connection bt vertex D & vertex B0
Enter connection bt vertex D & vertex C1
Enter connection bt vertex D & vertex D0
Enter connection bt vertex D & vertex E1
Enter connection bt vertex E & vertex A1
Enter connection bt vertex E & vertex B0
Enter connection bt vertex E & vertex C0
Enter connection bt vertex E & vertex D1
Enter connection bt vertex E & vertex E0
0->1
1->2
2->3
3->4
The Graph is connected
