Thursday 24 April 2014

Wap to check whether Graph is connected or not by traversing a Graph

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();  
  }  

2 comments:
Write comments
  1. should be dfs(n) at end of the program

    ReplyDelete
  2. Informative article, just what I wanted to find

    ReplyDelete

Featured post

List of Universities in Karnataka offering M.Sc Computer Science

The post-graduate programme in Computer Science (M.Sc Computer Science) contains two academic years duration and having a four semesters....

Popular Posts

Copyright @ 2011-2022