Depth First Search
#include<stdio.h>
#include<stdlib.h>
void
dfs(int v);
int
a[50][50], n, visited[50];
int
s[20], top = -1, count=0;
void
creategraph()
{
int
i, j;
printf("\nEnter
the number of vertices in graph:
");
scanf("%d",&n);
printf("\nEnter
the adjacency matrix:\n");
for(i=1;
i<=n; i++)
for(j=1;j<=n;j++)
scanf("%d",
&a[i][j]);
}
void
dfs(int v)
{
int
i;
visited[v]=1;
s[++top] = v;
for(i=1;i<=n;i++)
{
if(a[v][i] ==
1&& visited[i] == 0 )
{
dfs(i);
count++;
}
}
}
int
main()
{
int
ch, start, i, j;
creategraph();
for(i=1;i<=n;i++)
visited[i]=0;
printf("\n
Enter the starting vertex:\t");
scanf("%d",
&start);
dfs(start);
printf("\nNodes
reachable from starting vertex %d are:\n", start);
for(i=1;i<=count;i++)
printf("%d\t",
s[i]);
}
Output:
Enter
the number of vertices in graph: 4
Enter
the adjacency matrix:
0 1 0 1
0 0 1
0
0 0 0
1
0 0 0
0
Enter
the starting vertex: 1
Nodes reachable
from starting vertex 1 are:
2 3
4
Enter
the number of vertices in graph: 4
Enter
the adjacency matrix:
0 1 0
1
0 0 1
0
0 0 0
1
0 0 0
0
Enter
the starting vertex: 2
Nodes reachable
from starting vertex 2 are:
3 4
