Kruskal’s Algorithm for finding Minimum Spanning Tree
Given a connected and weighted undirected graph, construct a minimum spanning tree out of it using Kruskal’s Algorithm.
A Minimum Spanning Tree is a spanning tree of a connected, undirected graph. It connects all the vertices with minimal total weighting for its edges.
For example, consider the above graph. Its minimum spanning tree will be the following tree with exactly n-1 edges where n is the total number of vertices in the graph, and the sum of weights of edges is as minimum as possible:
Prerequisite:
We can use Kruskal’s Minimum Spanning Tree algorithm, a greedy algorithm to find a minimum spanning tree for a connected weighted graph. Kruskal’s Algorithm works by finding a subset of the edges from the given graph covering every vertex present in the graph such that they form a tree (called MST), and the sum of weights of edges is as minimum as possible.
Let G = (V, E) be the given graph. Initially, our MST contains only vertices of the given graph with no edges. In other words, initially, MST has V connected components, with each vertex acting as one connected component. The goal is to add minimum weight edges to our MST such that we are left with a single connected component that comprises all the graph’s vertices. Following is the complete algorithm:
G in order of their increasing weights;repeat V-1 times // as MST contains
V-1 edges{
select the next edge with minimum weight from graph
G;if (no cycle is formed by adding the edge in MST, i.e., the edge connects two
different connected components in MST)
add the edge to MST;
}
Let’s illustrate this by taking the example of the above graph. Initially, our MST consists of only the vertices of the given graph with no edges. We start by considering the smallest weighted edge 0–3 having weight 5. As no cycle is formed, include it in our MST.
We next consider the smallest weighted edge 2–4 also having weight 5. As no cycle is formed, include it in our MST.
We next consider the smallest weighted edge 3–5 having weight 6. As no cycle is formed, include it in our MST.
We next consider the smallest weighted edge 0–1 having weight 7. As no cycle is formed, include it in our MST.
We next consider the smallest weighted edge 1–4 also having weight 7. As no cycle is formed, include it in our MST.
We next consider the smallest weighted edge 5–4 having weight 8. But including this edge in MST will result in a cycle 0—1—4—5—3—0, so we discard it.
We next consider the smallest weighted edge 1–2 also having weight 8. But including this edge in MST will result in a cycle 1—2—4—1, so we discard it.
We next consider the smallest weighted edge 3–1 also having weight 9. But including this edge in MST will result in a cycle 0—1—3—0, so we discard it.
Finally, consider the next smallest weighted edge, 4–6, also weighting 9. As no cycle is formed, include it in our MST.
MST is now connected (containing V-1 edges). So, we discard all remaining edges.
Following is the pseudocode of Kruskal’s Algorithm as per Wikipedia. It uses a disjoint–set data structure.
MST = {}
for each vertex
v belonging 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):
add {(u, v)} to set MST
UNION(u, v)
return MST
Please note that if the graph is not connected, Kruskal’s Algorithm finds a Minimum Spanning Forest, a minimum spanning tree for each connected component of the graph.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include <iostream> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; // Data structure to store a graph edge struct Edge { int src, dest, weight; }; // Comparison object to be used to order the edges struct compare { bool operator() (Edge const &a, Edge const &b) const { return a.weight > b.weight; } }; // A class to represent a disjoint set class DisjointSet { unordered_map<int, int> parent; public: // perform MakeSet operation void makeSet(int n) { // create `n` disjoint sets (one for each vertex) for (int i = 0; i < n; i++) { parent[i] = i; } } // Find the root of the set in which element `k` belongs int Find(int k) { // if `k` is root if (parent[k] == k) { return k; } // recur for the parent until we find the root return Find(parent[k]); } // Perform Union of two subsets void Union(int a, int b) { // find the root of the sets in which elements // `x` and `y` belongs int x = Find(a); int y = Find(b); parent[x] = y; } }; // Function to construct MST using Kruskal’s algorithm vector<Edge> runKruskalAlgorithm(vector<Edge> edges, int n) // no-ref, no-const { // stores the edges present in MST vector<Edge> MST; // initialize `DisjointSet` class DisjointSet ds; // create a singleton set for each element of the universe ds.makeSet(n); // sort edges by increasing weight sort(edges.begin(), edges.end(), compare()); // MST contains exactly `V-1` edges while (MST.size() != n - 1) { // consider the next edge with minimum weight from the graph Edge next_edge = edges.back(); edges.pop_back(); // find the root of the sets to which two endpoints // vertices of the next edge belongs int x = ds.Find(next_edge.src); int y = ds.Find(next_edge.dest); // if both endpoints have different parents, they belong to // different connected components and can be included in MST if (x != y) { MST.push_back(next_edge); ds.Union(x, y); } } return MST; } int main() { // vector of graph edges as per the above diagram. vector<Edge> edges = { // (u, v, w) triplet represent undirected edge from // vertex `u` to vertex `v` having weight `w` {0, 1, 7}, {1, 2, 8}, {0, 3, 5}, {1, 3, 9}, {1, 4, 7}, {2, 4, 5}, {3, 4, 15}, {3, 5, 6}, {4, 5, 8}, {4, 6, 9}, {5, 6, 11} }; // total number of nodes in the graph (labelled from 0 to 6) int n = 7; // construct graph vector<Edge> e = runKruskalAlgorithm(edges, n); for (Edge &edge: e) { cout << "(" << edge.src << ", " << edge.dest << ", " << edge.weight << ")" << endl; } return 0; } |
Output:
(2, 4, 5)
(0, 3, 5)
(3, 5, 6)
(1, 4, 7)
(0, 1, 7)
(4, 6, 9)
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
import java.util.*; // A class to store a graph edge class Edge { int src, dest, weight; public Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } @Override public String toString() { return "(" + src + ", " + dest + ", " + weight + ")"; } } // A class to represent a disjoint set class DisjointSet { Map<Integer, Integer> parent = new HashMap<>(); // perform MakeSet operation public void makeSet(int n) { // create `n` disjoint sets (one for each vertex) for (int i = 0; i < n; i++) { parent.put(i, i); } } // Find the root of the set in which element `k` belongs private int find(int k) { // if `k` is root if (parent.get(k) == k) { return k; } // recur for the parent until we find the root return find(parent.get(k)); } // Perform Union of two subsets private void union(int a, int b) { // find the root of the sets in which elements `x` and `y` belongs int x = find(a); int y = find(b); parent.put(x, y); } // Function to construct MST using Kruskal’s algorithm public static List<Edge> runKruskalAlgorithm(List<Edge> edges, int n) { // stores the edges present in MST List<Edge> MST = new ArrayList<>(); // Initialize `DisjointSet` class. // create a singleton set for each element of the universe. DisjointSet ds = new DisjointSet(); ds.makeSet(n); int index = 0; // sort edges by increasing weight Collections.sort(edges, Comparator.comparingInt(e -> e.weight)); // MST contains exactly `V-1` edges while (MST.size() != n - 1) { // consider the next edge with minimum weight from the graph Edge next_edge = edges.get(index++); // find the root of the sets to which two endpoints // vertices of the next edge belongs int x = ds.find(next_edge.src); int y = ds.find(next_edge.dest); // if both endpoints have different parents, they belong to // different connected components and can be included in MST if (x != y) { MST.add(next_edge); ds.union(x, y); } } return MST; } } class Main { public static void main(String[] args) { // (u, v, w) triplet represent undirected edge from // vertex `u` to vertex `v` having weight `w` List<Edge> edges = Arrays.asList( new Edge(0, 1, 7), new Edge(1, 2, 8), new Edge(0, 3, 5), new Edge(1, 3, 9), new Edge(1, 4, 7), new Edge(2, 4, 5), new Edge(3, 4, 15), new Edge(3, 5, 6), new Edge(4, 5, 8), new Edge(4, 6, 9), new Edge(5, 6, 11)); // total number of nodes in the graph (labelled from 0 to 6) int n = 7; // construct graph List<Edge> e = DisjointSet.runKruskalAlgorithm(edges, n); System.out.println(e); } } |
Output:
[(0, 3, 5), (2, 4, 5), (3, 5, 6), (0, 1, 7), (1, 4, 7), (4, 6, 9)]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
# A class to represent a disjoint set class DisjointSet: parent = {} # perform MakeSet operation def makeSet(self, n): # create `n` disjoint sets (one for each vertex) for i in range(n): self.parent[i] = i # Find the root of the set in which element `k` belongs def find(self, k): # if `k` is root if self.parent[k] == k: return k # recur for the parent until we find the root return self.find(self.parent[k]) # Perform Union of two subsets def union(self, a, b): # find the root of the sets in which elements `x` and `y` belongs x = self.find(a) y = self.find(b) self.parent[x] = y # Function to construct MST using Kruskal’s algorithm def runKruskalAlgorithm(edges, n): # stores the edges present in MST MST = [] # Initialize `DisjointSet` class. # Create a singleton set for each element of the universe. ds = DisjointSet() ds.makeSet(n) index = 0 # sort edges by increasing weight edges.sort(key=lambda x: x[2]) # MST contains exactly `V-1` edges while len(MST) != n - 1: # consider the next edge with minimum weight from the graph (src, dest, weight) = edges[index] index = index + 1 # find the root of the sets to which two endpoints # vertices of the next edge belongs x = ds.find(src) y = ds.find(dest) # if both endpoints have different parents, they belong to # different connected components and can be included in MST if x != y: MST.append((src, dest, weight)) ds.union(x, y) return MST if __name__ == '__main__': # (u, v, w) triplet represent undirected edge from # vertex `u` to vertex `v` having weight `w` edges = [ (0, 1, 7), (1, 2, 8), (0, 3, 5), (1, 3, 9), (1, 4, 7), (2, 4, 5), (3, 4, 15), (3, 5, 6), (4, 5, 8), (4, 6, 9), (5, 6, 11) ] # total number of nodes in the graph (labelled from 0 to 6) n = 7 # construct graph e = runKruskalAlgorithm(edges, n) print(e) |
Output:
[(0, 3, 5), (2, 4, 5), (3, 5, 6), (0, 1, 7), (1, 4, 7), (4, 6, 9)]
The time complexity of the above solution is O(n2), where n is the total number of vertices in the graph. The time complexity can be improved to O(n.log(n)) by using the optimized implementation of Union and Find operations.
References:
1. https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
2. http://lcm.csa.iisc.ernet.in/dsa/node184.html
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)