Trend Posts
Author
View LUQMAN's profile
Showing posts with label Depth First Search method. Show all posts
Showing posts with label Depth First Search method. Show all posts
Monday, July 21, 2014
/*Check whether a given graph is connected or not using DFSmethod.*/
#include<stdio.h>
void dfs(int i);
int i,j,adj[1000][1000],v[1000],w,n,count;
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the graph in the form of adjacency matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&adj[i][j]);
printf("\n\nThe adjacency matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",adj[i][j]);
printf("\n");
}
for(i=1;i<=n;i++)
{
count=0;
for(j=1;j<=n;j++)
v[j]=0;
dfs(i);
if(count==n)
{
printf("\nThe entered graph is connected\n");
return;
}
}
printf("\nThe entered graph is not connected\n");
}
void dfs(int i)
{
int w;
count++;
v[i]=1;
for(w=1;w<=n;w++)
if(adj[i][w]==1 && !v[w])
dfs(w);
}
Subscribe to:
Posts (Atom)