Computer Science Wiki

Search

SearchSearch

MST - Kruskal's Algorithm

Sep 13, 20245 min read

Related data structure:

Related paradigm:

Related algorithm:

AlgorithmGraphGreedy_AlgorithmMinimum_Spanning_TreeMSTKruskal

Kruskal’s algorithm is a greedy algorithm finds a Minimum Spanning Tree (MST) of an undirected weighted graph. The algorithm iteratively adds lowest-weight edge to the resulting MST that will not form a cycle. The edges are sorted and ADT - Disjoint Set (AKA. Union-Find) data structure is used to detect cycles.

Implementation

The union find data structure is used in this algorithm to efficiently keep track of connected components and detect cycles in a graph.

  1. Sort all the edges of the graph by their weights in non-decreasing order. (makes it easier to find the minimum weighted edges)
  2. Iterate over the sorted edges, for each edge, check if adding this edge to the MST forms a cycle. This can be done by checking if the vertices of the edge belong to the same connected component of in the union find data structure. If adding the edge does not form a cycle, add it to the MST and merge the connected components of its vertices in the union find data structure.
  3. Continue the iteration until all vertices are connected (i.e. until the MST contains edges, where is the number of vertices in the graph) or until all edges have been considered.
  4. The list of edges accumulated during the algorithm forms the MST.
class Edge implements Comparable<Edge> {
	int src;
	int dest;
	int weight;
	
	public Edge(int src, int dest, int weight) {
		this.src = src;
		this.dest = dest;
		this.weight = weight;
	}
	
	@Override 
	public int compareTo(Edge other) {
		return this.weight - other.weight;
	}
}
 
class UnionFind {
	// represents the parent of each vertex
	// index(vertex) : parent
	private int[] parent;
	
	public UnionFind(int size) {
		// the size is the number of vertices in the graph
		parent = new int[size];
		// initalise the parent array that each vertex 
		// is its own parent initally
		for (int i=0; i<size; i++) {
			parent[i] = i;
		}
	}
	
	// find the representative (parent) of the set that contains the 
	// given vertex
	public int find(int vertex) {
		// if the parent is not the vertex itself,
		// find its parent
		if (parent[vertex] != vertex) {
			parent[vertex] = find(parent[vertex]);
		}
		return parent[vertex];
	}
	
	public void union(int vertex1, int vertex2) {
		// makes the two vertices to have same parent
		int parent1 = find(vertex1);
		int parent2 = find(vertex2);
		parent[parent2] = parent1;
	}
}
 
class class KruskalsAlgo{
	public static List<Edge> kruskalMST(List<Edge> edges, int numVertices) {
		List<Edge> MST = new ArrayList<>();
		// sort edges by weight
		Collections.sort(edges);
		// initalise union find data structure
		UnionFind uf = new UnionFind(numVertices);
		// iterate through stored edges
		// add edge to MST if they don't form a cycle
		for (Edge edge : edges) {
			// if the source and destination of the edge does not belong
			// to the same set, they won't form a cycle
			int srcParent = uf.find(edge.src);
			int destParent = uf.find(edge.dest);
			if (srcParent != destParent) {
				MST.add(edge);
				uf.union(edge.src, edge.dest);
			}
		}
		return MST;
	}
	
	public static void main(String[] args) {
		List<Edge> edges = new ArrayList<>();
		// Edge: src, dest, weight
		edges.add(new Edge(0, 1, 4));
		edges.add(new Edge(0, 2, 8));
		// 5 more ...
		
		// the MST list is the resulting MST 
		List<Edge> MST = kruskalMST(edges, 7);
	}
}

Time complexity

Optimise performance using rank

Union by rank is one of the way to optimise the performance of the union find data structure. In addition to maintain the parent array, each vertex in the union find data structure also maintains a rank attribute. When performing union find operation between two sets, represented by roots or parents parent1 and parent2, the union by rank heuristic considers the ranks of these parents. The set with lower rank is attached to the set with the higher rank (the set with higher rank’s parent becomes the set with the lower rank’s parent). The rank of a root roughly indicates the number of merges (or unions) that root has undergone. By attaching smaller set (tree) to larger set (tree), the depth of the tree is minimised. Improves the time complexity of the find() and union() operation to .

=== ORIGINAL IMPLEMENTATION ===

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
     2   3   
    /
   1
 /
0

Do Union(2, 3)
         3    
        /
      2
     /
   1
 /
0

=== UNION BY RANK ===

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
   1    3
 /  \
0    2

Do Union(2, 3)
    1    
 /  |  \
0   2   3

class UnionFind {
    private int[] parent;
    private int[] rank;
    
    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    public int find(int vertex) {
        if (parent[vertex] != vertex) {
            parent[vertex] = find(parent[vertex]);
        }
        return parent[vertex];
    }
    
    public void union(int vertex1, int vertex2) {
        int root1 = find(vertex1);
        int root2 = find(vertex2);
        
        if (root1 == root2) {
            return; // same set, no need to merge
        }
        
        if (rank[root1] < rank[root2]) {
            parent[root1] = root2;
        } else if (rank[root1] > rank[root2]) {
            parent[root2] = root1;
        } else {
            // if ranks are equal, arbitrarily choose one as parent and increment its rank
            parent[root2] = root1;
            rank[root1]++;
        }
    }
}

Back to parent page:

Reference:

Graph View

Backlinks