Trend Posts
Author
View LUQMAN's profile
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:
Post Comments (Atom)
0 comments:
Post a Comment
You are very Important to Us...
STAY TUNE...