| 61 | } |
| 62 | |
| 63 | void kruskals_mst() |
| 64 | { |
| 65 | // 1. Sort all edges |
| 66 | sort(edgelist.begin(), edgelist.end()); |
| 67 | |
| 68 | // Initialize the DSU |
| 69 | DSU s(V); |
| 70 | int ans = 0; |
| 71 | cout << "Following are the edges in the " |
| 72 | "constructed MST" |
| 73 | << endl; |
| 74 | for (auto edge : edgelist) { |
| 75 | int w = edge[0]; |
| 76 | int x = edge[1]; |
| 77 | int y = edge[2]; |
| 78 | |
| 79 | // Take this edge in MST if it does |
| 80 | // not forms a cycle |
| 81 | if (s.find(x) != s.find(y)) { |
| 82 | s.unite(x, y); |
| 83 | ans += w; |
| 84 | cout << x << " -- " << y << " == " << w |
| 85 | << endl; |
| 86 | } |
| 87 | } |
| 88 | |
| 89 | cout << "Minimum Cost Spanning Tree: " << ans; |
| 90 | } |
| 91 | }; |
| 92 | |
| 93 | // Driver's code |