Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<stdlib.h>
- #include<limits.h>
- #define V 5
- int parent[V];
- 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;
- }
- void main()
- {
- /* Let us create the following graph
- 2 3
- (0)--(1)--(2)
- | / \ |
- 6| 8/ \5 |7
- | / \ |
- (3)-------(4)
- 9*/
- int cost[V][V] = {{0, 2, 0, 6, 0},
- {2, 0, 3, 8, 5},
- {0, 3, 0, 0, 7},
- {6, 8, 0, 0, 9},
- {0, 5, 7, 9, 0},
- };
- /*int cost[V][V] = {{0,4,0,6,0},
- {4,0,3,2,5},
- {0,3,0,0,6},
- {6,2,0,0,7},
- {0,5,6,7,0}};*/
- int i,j,a,b,u,v,ne=1, mini, mincost=0;
- for(i=0;i<V;i++)
- for(j=0;j<V;j++)
- if(cost[i][j]==0)
- cost[i][j]=INT_MAX;
- printf("The edges of Minimum Cost Spanning Tree are\n");
- while(ne < V)
- { mini=INT_MAX;
- for(i=0;i<V;i++)
- {
- for(j=0;j<V;j++)
- {
- if(cost[i][j] < mini)
- {
- mini = cost[i][j];
- a = u = i;
- b = v = j;
- }
- }
- }
- u=find(u);
- v=find(v);
- if(uni(u,v))
- {
- printf("%d edge (%d,%d) =%d\n",ne++,a,b,mini);
- mincost += mini;
- }
- cost[a][b] = cost[b][a] = INT_MAX;
- }//end of while
- printf("\nMinimum cost = %d\n",mincost);
- }
Advertisement
Add Comment
Please, Sign In to add comment