Kruskal's algorithm in c
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in C:/*This article is compiled by Aashish */ #include<stdio.h> int i,j,k,a,b,u,v,n,ne=1; int min,mincost=0,cost[9][9],parent[9]; int find(int); int uni(int,int); int main() { printf("\nEnter the no. of vertices:"); scanf("%d",&n); printf("\nEnter the cost adjacency matrix\n"); for(i=1;i<=n;i++) { printf("\n"); for(j=1;j<=n;j++) { printf("a[%d][%d]: ",i,j); scanf("%d",&cost[i][j]); if(cost[i][j]==0) cost[i][j]=999; } } printf("\nThe edges of Minimum Cost Spanning Tree are\n\n"); while(ne<n) { for(i=1,min=999;i<=n;i++) { for(j=1;j<=n;j++) { if(cost[i][j]<min) { min=cost[i][j]; a=u=i; b=v=j; } } } u=find(u); v=find(v); if(uni(u,v)) { printf("\n%d edge (%d,%d) =%d\n",ne++,a,b,min); mincost +=min; } cost[a][b]=cost[b][a]=999; } printf("\n\tMinimum cost = %d\n",mincost); return 0; } int find(int i) { while(parent[i]) i=parent[i]; return i; } int uni(int i,int j) { if(i!=j) { parent[j]=i; return 1; } return 0; }output:-
Enter the no. of vertices:6 Enter the cost adjacency matrix a[1][1]: 0 a[1][2]: 3 a[1][3]: 1 a[1][4]: 6 a[1][5]: 0 a[1][6]: 0 a[2][1]: 3 a[2][2]: 0 a[2][3]: 5 a[2][4]: 0 a[2][5]: 3 a[2][6]: 0 a[3][1]: 1 a[3][2]: 5 a[3][3]: 0 a[3][4]: 5 a[3][5]: 6 a[3][6]: 4 a[4][1]: 6 a[4][2]: 0 a[4][3]: 5 a[4][4]: 0 a[4][5]: 0 a[4][6]: 2 a[5][1]: 0 a[5][2]: 3 a[5][3]: 6 a[5][4]: 0 a[5][5]: 0 a[5][6]: 6 a[6][1]: 0 a[6][2]: 0 a[6][3]: 4 a[6][4]: 2 a[6][5]: 6 a[6][6]: 0 The edges of Minimum Cost Spanning Tree are
1 edge (1,3) =1 2 edge (4,6) =2 3 edge (1,2) =3 4 edge (2,5) =3 5 edge (3,6) =4 Minimum cost = 13 --------------------------------
0 comments: