Here is a C program to check whether graph is connected or not by traversing a graph. This program takes input of adjacency matrix where matrix elements will be in 0 and 1. "0" for not connecting edges and "1" for directly connected edges. The matrix provides a enough information to check whether a graph is connected or not by checking each of elements in the adjacency matrix.
#include<stdio.h> #include<conio.h> int a[20][20],reach[20],n; void dfs(int v) { int i; reach[v]=1; for(i=1;i<=n;i++) if(a[v][i] && !reach[i]) { printf("\n %d -> %d",v,i); dfs(i); } } void main() { int i,j,count=0; clrscr(); printf("\n@@@ Enter number of vertices:@@@"); scanf("%d",&n); for(i=1;i<=n;i++) { reach[i]=0; for(j=1;j<=n;j++) a[i][j]=0; } printf("\n Enter the adjacency matrix:\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&a[i][j]); printf ("\n>>> The entered adjacency matrix is \n" ); for (i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf ("%3d",a[i][j]); } printf ("\n"); } dfs(1); printf("\n"); for(i=1;i<=n;i++) { if(reach[i]) count++; } if(count==n) printf("\n Graph is connected"); else printf("\n Graph is not connected"); getch(); }
should be dfs(n) at end of the program
ReplyDeleteInformative article, just what I wanted to find
ReplyDelete