Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


Description:
  KRUSKAL
Language: C/C++
Code:
#include <stdio.h>
#include <string.h>
#include<conio.h>


int main()
{
  int a[5][5]; int i, j;
  int k=1, t=0, n, e, min=999; 
  int u=0, v=0;
  int p[5];
  
  printf(" enter the number of nodes");
  scanf("%d", &n);
  printf("n enter the number of edges");
  scanf("%d", &e);
  
  
  
  for (i=1; i<=n; i++)
  {
      p[i]=0;
     for (j=1; j<=n; j++)
     {
     if(i<j)
      {
               printf( "dist bn %d and %d", i, j);
           scanf("%d", &a[i][j]);
           a[i][j]= a[j][i];
           }

     else
     continue;
     }
  }
  
  for (i=1; i<=n; i++)
  {
      for (j=1; j<=n; j++)
      {
          if (a[i][j]==0)
         
              a[i][j]=999;
          else
          printf("%d to %d= %d", i, j, a[i][j]);
      }
  }
  
  
  while(k<n)  /*iterations until we find n-1 edges*/
  {
      for (i=1; i<=n; i++)
      {
          for (j=1; j<=n; j++)
          {
              if(a[i][j]<min)
              {
                  min=a[i][j];
                  u=i; 
                  v=j;
              }
          }
      }
  }
  
  while(p[u]!=0)
  {
      u=p[u]; /*checking for possible loops containing u*/
  }
  
  while(p[v]!=0)
  {
      v=p[v]; /*checking for possible loops containing v*/
  }
  if (u!=v)
  {
      k=k++;
      printf("edge: %d - %d %d", u, v, min);
      t=t+min;
      p[v]=u; /*since we reached v through u*/
 
        a[u][v]=999;
        a[u][v]=a[v][u];
  }
  
printf("MST weight: %d", t);
return 0;
}
          
          
          
          
          
          
          
          
          
          
Comments: