Thursday, 24 April 2014

Wap to generate minimum spanning tree using Kruskal method.

This C program generates minimum spanning tree using kruskal method. There are several other method to achieve minimum spanning tree and they are :
  1. Kruskal's algorithm
  2. Prim's algorithm
  3. Boruvka's algorithm
Here we will use Kruskal's algorithm to get minimum spanning tree.
 #include<stdio.h>  
 #include<conio.h>  
  int main()  
  {  
    int a[10][10],b[50],i,j,k=0,l,v,n=0,f=0,s=0;  
    printf("enter the number of vertices\t");  
    scanf("%d",&v);  
    int chck[v];  
    printf("enter the adjacency matrix elements\n");  
    for(i=0;i<v;i++)  
    {  
            chck[i]=0;  
            for(j=0;j<v;j++)  
            {  
                    scanf("%d",&a[i][j]);  
            }  
    }  
    for(i=0;i<v;i++)  
    {  
            for(j=i;j<v;j++)  
            {  
                    if(a[i][j]>0 && i!=j)  
                    {  
                     b[n]=a[i][j];  
                     n++;  
                     l=n;   
                    }      
            }  
    }  
    for(i=0;i<(n-1);i++)  
    {  
            for(j=i+1;j<n;j++)  
            {  
                     if(b[i]>b[j])  
                     {  
                           b[i]=b[i]+b[j];  
                           b[j]=b[i]-b[j];  
                           b[i]=b[i]-b[j];  
                     }  
            }  
    }  
    printf("\n\n");  
    for(i=0;i<n;i++)  
    {  
            printf("%d\n",b[i]);  
    }  
    k=0;  
     for(i=0;i<v;i++)  
    {  
             if (f==1)  
             {  
             i=0;f=0;  
            }  
           for(j=i+1;j<v;j++)  
            {  
                    if(a[i][j]==b[k] && s<(v-1) &&i!=j)  
                    {  
                            if(chck[i]==1 && chck[j]==1)  
                            {  
                            k++;  
                            a[i][j]=0;  
                            f=1;  
                            }  
                            else  
                            {  
                             printf("V%dE%dV%d\t",i+1,b[k],j+1);  
                             chck[i]=31;  
                             chck[j]=1;  
                             k++;  
                             a[i][j]=0;  
                             f=1;  
                            }  
                    }  
            }  
    }  
    getch();  
 }  

1 comment:
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