...
/Solution: Find the Minimum Spanning Tree - Kruskal’s Solution
Solution: Find the Minimum Spanning Tree - Kruskal’s Solution
In this review, we give a detailed analysis on finding the minimum spanning tree of the given graph using Kruskal's solution.
We'll cover the following...
Solution: Kruskal’s Algorithm
Kruskal’s algorithm is a minimum-spanning-tree algorithm that finds an edge of the least possible weight.
It is a greedy algorithm, as it finds a minimum spanning tree for a connected weighted graph—adding increasing cost arcs at each step.
Press + to interact
main.cpp
Graph.cpp
DisjointSets.cpp
DisjointSets.h
Graph.h
#include "Graph.h"#include "DisjointSets.h"typedef pair <int, int> myPair;int Graph::kruskalMST() {int weightOfMST = 0;// lets first sort all the edges.sort(edgesArray.begin(), edgesArray.end());DisjointSets mySetDataStructure(this -> vertices);vector <pair <int, myPair>> ::iterator iterator;for (iterator = edgesArray.begin(); iterator != edgesArray.end(); iterator++) {int u = iterator -> second.first;int v = iterator -> second.second;int set_u = mySetDataStructure.find(u);int set_v = mySetDataStructure.find(v);if (set_u != set_v) {cout << u << " -- " << v << endl;weightOfMST += iterator -> first;mySetDataStructure.merge(set_u, set_v);}}return weightOfMST;}int main() {int V = 4, E = 5;Graph g(V, E);g.addEdge(0, 1, 10);g.addEdge(0, 2, 6);g.addEdge(0, 3, 5);g.addEdge(1, 3, 15);g.addEdge(2, 3, 4);cout << "Minimum Spanning Tree of Graph 1" << endl;g.kruskalMST();cout << endl <<endl;//////////////////V = 6;E = 15;Graph g2(V, E);g2.addEdge(0, 1, 4);g2.addEdge(0, 2, 4);g2.addEdge(1, 2, 2);g2.addEdge(1, 0, 4);g2.addEdge(2, 0, 4);g2.addEdge(2, 1, 2);g2.addEdge(2, 3, 3);g2.addEdge(2, 5, 2);g2.addEdge(2, 4, 4);g2.addEdge(3, 2, 3);g2.addEdge(3, 4, 3);g2.addEdge(4, 2, 4);g2.addEdge(4, 3, 3);g2.addEdge(5, 2, 2);g2.addEdge(5, 4, 3);cout << "Minimum Spanning Tree of Graph 2" << endl;g2.kruskalMST();return 0;}
Pseudocode
KruskalMST(G):
A = ∅
for each v ∈ G.V:
MAKE-SET(v)
for each (u, v) in G.E ordered by weight(u, v), increasing:
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A
Animation
The animation below gives a demo of how Kruskal’s algorithm is applied to a graph to find its minimum spanning tree.
