MST (Kruskals Algorithm)

01 /*
02 MST(Kruskal's)
03 */
04
05 #include<iostream.h>
06 #include<stdlib.h>
07
08 #define MAXN 102
09
10 int P[MAXN], Rank[MAXN];
11
12 int Node, edg, Cost;
13
14 struct edge {
15 int u, v;
16 int cost;
17 };
18
19 edge Edge[MAXN*MAXN];
20 edge Path[MAXN];
21
22 int com(const void *xy, const void *xz) {
23 edge *x = (edge*)xy;
24 edge *y = (edge*)xz;
25 return (x->cost - y->cost);
26 }
27
28 void In() { // initializing parent and rank for each node
29 int i;
30 for(i = 1; i<= Node; i++) {
31 P[i] = i;
32 Rank[i] = 1;
33 }
34 }
35
36 int Find(int n) { // find the parent of a node
37 if(P[n] != n)
38 P[n] = Find(P[n]);
39 return P[n];
40 }
41
42 void Link(int x, int y) { // joining the nodes
43 if(Rank[x] > Rank[y]) {
44 P[y] = x;
45 }
46 else {
47 P[x] = y;
48 if(Rank[x] == Rank[y])
49 Rank[y]++;
50 }
51 }
52
53 void Kruscal() {
54 int x, y, total = 0;
55 Cost = 0;
56 for(int i = 0; i<edg; i++) {
57 x = Find(Edge[i].u);
58 y = Find(Edge[i].v);
59 if(x != y) { // if not cycle
60
61 Path[total++] = Edge[i];
62 Link(x,y); // join those node
63 Cost += Edge[i].cost;
64 if(total == Node - 1) break// already taken all nodes ?
65 }
66 }
67 }
68
69 void Cal() {
70 qsort(Edge,edg,sizeof(edge),com); // sorting the edges respect to cost
71 Kruscal();
72 cout<<"Total Cast :"<<Cost<<endl;
73 for(int i = 0; i<Node-1; i++) // printing the path
74 cout<<Path[i].u<<" "<<Path[i].v<<" "<<Path[i].cost<<endl;
75 }
76
77 void main() {
78 int i;
79 while(cin>>Node>>edg) { // reading number of node and edge
80 In();
81 for(i = 0; i<edg; i++)  // reading each edate with cost
82 cin>>Edge[i].u>>Edge[i].v>>Edge[i].cost;
83 Cal();
84 }
85 }

Leave a Reply

Your email address will not be published. Required fields are marked *