A minimum spanning tree(MST) is a subset of a weighted undirected graph, in which edges that forms a tree (no cycle graph) includes every vertex in a graph, where the sum of the weights of all the edges in the tree is minimized. Kruskal’s algorithm is an algorithm to find MST in a weighted undirected graph using union find.
Kruskal’s algorithm is a greedy algorithm. In the process, it always adds the next lowest weight edge. In order not to form a cycle, it uses find and union methods in the DisjointSet class. If two vertices of an edge don’t share the same root confirmed by find method, you add this edge to MST. After adding the edge, call union method to union this two vertices so that they will not be added again.
Table of Content
Define an Edge classe
MST is a weighted graph problem. You can define edge as a class, in which there are source vertex, target vertex, and weight.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
static class GraphEdge<E> { E src, dest; int weight; //Time O(1), Space O(1) public GraphEdge(E src, E dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } //Time O(1), Space O(1) @Override public String toString() { return "(" + src + ", " + dest + ", " + weight + ")"; } } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class GraphEdge { //Time O(1), Space O(1) constructor(src, dest, weight) { this.src = src; this.dest = dest; this.weight = weight; } //Time O(1), Space O(1) toString() { return "(" + this.src + ", " + this.dest + ", " + this.weight + ")"; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 |
class GraphEdge : #Time O(1), Space O(1) def __init__(self, src, dest, weight) : self.src = src self.dest = dest self.weight = weight #Time O(1), Space O(1) def __str__(self) : return "(" + str(self.src) + ", " + str(self.dest) + ", " + str(self.weight) + ")" |
Add edge
Next you construct a graph. A graph is often represented as adjacency list. Here a graph is simplified. You don’t need create hashmap to represent graph. Instead you define edges and vertices separately. edges is a list of GraphEdge objects. nodes is a set of individual vertices.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 |
import java.util.*; @SuppressWarnings({ "unchecked", "rawtypes" }) public class Kruskal<T> { List<GraphEdge<T>> edges = new ArrayList<>(); Set<T> nodes = new HashSet<>(); //nodes in graph //Add node and edges, Time O(1), Space O(1) public void addEdge(T u, T v, int w) { nodes.add(u); nodes.add(v); edges.add(new GraphEdge<T>(u,v,w)); } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
const DisjointSet = require('./DisjointSet.js') class Kruskal { constructor() { this.edges = new Array(); this.nodes = new Set(); //nodes in graph } //Add node and edges, Time O(1), Space O(1) addEdge(u, v, w) { this.nodes.add(u); this.nodes.add(v); this.edges.push(new GraphEdge(u,v,w)); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
import DisjointSet class Kruskal: # Time O(1), Space O(1) def __init__(self): self.edges = [] self.nodes = set() # Add node and edges, Time O(1), Space O(1) def addEdge(self, u, v, w) : self.nodes.add(u) self.nodes.add(v) self.edges.append(GraphEdge(u,v,w)) |
Kruskal’s algorithm
Now you can apply Kruskal’s algorithm. Since it uses Disjoint set data structure’s union and find method, you can create an object of DisjointSet class, which has been introduced in Disjoint set and union find post. Call makeSet method with nodes to establish a disjoint set. Sort the list of edges by their weights in ascending order. Start from the smallest-weight edge, if the source node and target node are not in the same subset of a disjoint set, they is no cycle when adding them. You can add this edge to MST. Then you union these two nodes so that they will not be selected again.
The time complexity of Kruskal’s algorithm is O(E*logE) due to sorting, E is number of edges in the graph. Since find uses recursion, the space is required for recursive function’s call stacks. The Space complexity is O(E*a(E+V)), where α(n) is the extremely slow-growing inverse Ackermann function due to optimization of path compression and union by rank in disjoint set implementation.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Time O(E*log(E) Space O(E*a(E+V)), a(n) is the inverse ackermann function, public List<GraphEdge<T>> weightedMST() { List<GraphEdge<T>> mst = new ArrayList<>(); Collections.sort(edges, Comparator.comparingInt(e -> e.weight)); DisjointSet<T> ds = new DisjointSet(); ds.makeSet(new ArrayList(nodes)); for(GraphEdge<T> edge: edges) { if (!ds.find(edge.src).equals(ds.find(edge.dest)) ) { mst.add(edge); ds.union(edge.src, edge.dest); } } return mst; } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Time O(E*log(E)) Space O(E*a(E+V)), a(n) is the inverse ackermann function, weightedMST() { var mst = new Array(); this.edges.sort((a,b) => a.weight-b.weight); var ds = new DisjointSet(); ds.makeSet(this.nodes); for (let edge of this.edges) { if (ds.find(edge.src) != (ds.find(edge.dest)) ) { mst.push(edge); ds.union(edge.src, edge.dest); } } return mst; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
# Time O(E*log(E) Space O(E*a(E+V)), a(n) is the inverse ackermann function, def kruskal(self): mst = [] ds = DisjointSet.DisjointSet() ds.make_set(list(self.nodes)) self.edges.sort(key = lambda x: x.weight) # sort edges by increasing weight for edge in self.edges: if ds.find(edge.src) != ds.find(edge.dest) : mst.append(edge) ds.union(edge.src, edge.dest) return mst |
Free download
Download Kruskal’s algorithm in Java, JavaScript
and Python
Minimum spanning tree (GitHub)