Thursday, 24 April 2014

Wap to check whether Graph is connected or not using adjacent matrix multiplication.

#include<stdio.h>
#include<conio.h>
int connect();
int d[20][20],a[20][20],n;
int main()
{
    int i,j,flag=0;
    printf("Enter the number of vertices in a graph: ");
    scanf("%d",&n);
    printf("Enter the adjacency matrix:\n");
    for(i=1;i<=n;i++)
    {
       for(j=1;j<=n;j++)
       {
          scanf("%d",&a[i][j]);
          d[i][j]=a[i][j];
       }
    }
    Printf("Adjacency Matrix is:\n");
    for(i=1;i<=n;i++)
      {
          for(j=1;j<=n;j++)
          {    
                            printf( "%d\t",d[i][j]);
                             }
                             printf("\n");
                             }
   for(i=1;i<=n-1;i++)
   {
   
   connect();
}
   printf("Multiplication of matrices is:\n");
   for(i=1;i<=n;i++)
   {
       for(j=1;j<=n;j++)
    {
        printf("%3d",d[i][j]);
      }
      printf("\n");
    }
    for(i=1;i<=n;i++)
    {
       for(j=1;j<=n;j++)
       {
       if(d[i][j]==0)
       flag=1;
   
    }
   
    }
    if(flag==0)
    {
   printf("connected");
    }
else
{
    printf("disconnected");
}
    getch();
}

int connect()
{
    int i,j,k,c[20][20]={0};  
   
         for(i=1;i<=n;i++)
    {
                       for(j=1;j<=n;j++)
                       {             

         for(k=1;k<=n;k++)
         {
            c[i][j]=c[i][j]+(d[i][k]*a[k][j]);
         }  
       }
   
     }
     for(i=1;i<=n;i++)
    {
                       for(j=1;j<=n;j++)
                       {    
                             d[i][j]=c[i][j];
                             }
                             }
                           


}

No comments:
Write comments

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-2016