16 December, 2011

#include<stdio.h>
  
#include<stdlib.h>
  
void printArray(int a[][100],int n);
  
void AdjacencyMatrix(int a[][100], int n){
    int i,j;
    for(i = 0;i < n; i++)
    {
        for(j = 0;j < i; j++)
        {
            a[i][j] = a[j][i]= rand()%50;
            if( a[i][j]>40)a[i][j]=a[j][i]=999;
              
        }
    a[i][i] = 999;
    }
    printArray(a,n);
}
  
void printArray(int a[][100],int n){
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("%d\t",a[i][j]);
        }
        printf("\n");
    }
}
  
int root(int v,int p[]){
  
    while(p[v] != v)
        {v = p[v];}
          
return v;
}
  
void union_ij(int i,int j,int p[]){
    if(j > i)
        p[j] = i;
    else
        p[i] = j;
}
  
void kruskal(int a[][100],int n){
    int count, i, p[100], min, j, u, v, k, t[100][100], sum;
    count = k = sum = 0;
    for(i = 0; i < n; i++)
    {
        p[i] = i;
    }
    while(count < n)
    {
        min = 999;
        for(i = 0; i < n; i++)
        {
            for(j = 0;j < n; j++)
            {
              
                if(a[i][j] < min)
                {
                    min = a[i][j];
                    u = i;
                    v = j;
                      
                }
            }
        }
        if(min != 999)
        {
            i = root(u, p);
            j = root(v, p);
            if (i != j)
            {
                t[k][0] = u;
                t[k][1] = v;
                  
                k++;
                  
                sum += min;
                union_ij(i,j,p);
            }
        a[u][v] = a[v][u] = 999;
          
        }count +=1;
    }   
    if(count != n)
    {
        printf("spanning tree not exist\n");
    }
    if(count == n)
    {
        printf("Adges Spanning tree is\n");
        for(k = 0; k < n-1 ; k++)
        {
            printf(" %d -> %d ",t[k][0],t[k][1]);
        }
    printf("\ncost = %d \n",sum);
    }
}
  
int main()
{
    int a[100][100],n;
    printf("enter the number of vertices\n");
    scanf("%d",&n);
    AdjacencyMatrix(a,n);
    kruskal(a,n);
    return 0;
}
  

No comments:

Post a Comment