Kruskal's Algorithm

1. Introduction

Kruskal's algorithm, published by Joseph Kruskal in 1956, finds a minimum spanning tree (MST) for a connected, undirected, weighted graph. A minimum spanning tree is a subset of edges that connects all vertices together with the minimum possible total edge weight, without forming any cycles.

The algorithm takes a global, edge-centric approach: it sorts all edges by weight and greedily adds the cheapest edge that does not create a cycle. This contrasts with Prim's algorithm, which grows the MST from a single starting vertex. The correctness of Kruskal's algorithm is guaranteed by the cut property of MSTs: for any cut of the graph, the minimum weight edge crossing the cut must be in every MST.

"A minimum spanning tree connects all the vertices together with the least total weighting for its edges." -- Joseph Kruskal, On the Shortest Spanning Subtree of a Graph

2. How It Works

Kruskal's algorithm builds the MST by starting with a forest of isolated vertices and progressively merging trees by adding edges. The process follows these principles:

1. Sort all edges in the graph by their weight in non-decreasing order.
2. Initialize a forest where each vertex is its own separate tree (component).
3. Process edges in order: For each edge in sorted order, check if its two endpoints belong to different trees. If they do, add the edge to the MST and merge the two trees. If they belong to the same tree, skip the edge (it would create a cycle).
4. Terminate when exactly V - 1 edges have been added to the MST, or all edges have been processed.

3. Algorithm and Pseudocode

functionKruskal(Graph): MST = empty set let edges = Graph.edges sorted by weight (ascending) // Initialize Union-Findfor each vertex v in Graph.vertices: MakeSet(v) for each edge (u, v, w) in edges: ifFind(u) != Find(v): MST.add((u, v, w)) Union(u, v) if |MST| == |Graph.vertices| - 1: breakreturn MST

The algorithm terminates either when V - 1 edges have been selected (forming a spanning tree) or when all edges have been considered. If fewer than V - 1 edges are selected after processing all edges, the graph is not connected.

4. Union-Find Data Structure

The Union-Find (or Disjoint Set Union) data structure is critical to Kruskal's algorithm. It supports two operations efficiently:

• Find(x): Returns the representative (root) of the set containing element x.
• Union(x, y): Merges the sets containing elements x and y.

functionMakeSet(x): parent[x] = x rank[x] = 0functionFind(x): if parent[x] != x: parent[x] = Find(parent[x]) // Path compressionreturn parent[x]functionUnion(x, y): rootX = Find(x) rootY = Find(y) if rootX == rootY: return// Union by rankif rank[rootX] < rank[rootY]: parent[rootX] = rootY else if rank[rootX] > rank[rootY]: parent[rootY] = rootX else: parent[rootY] = rootX rank[rootX] += 1

With both path compression and union by rank, the amortized time per operation is O(alpha(n)), where alpha is the inverse Ackermann function -- effectively constant for all practical purposes.

5. Complexity Analysis

Since E <= V^2, we have log E <= 2 log V, so O(E log E) = O(E log V). The sorting step dominates the total running time.

6. Worked Example

Consider a connected undirected graph with 6 vertices (A-F) and the following edges:

Step 1: Sort edges by weight

Sorted order: C-F(1), A-F(2), D-E(2), C-D(3), A-B(4), B-F(5), B-C(6), D-F(7), E-F(8)

Step 2: Process edges

Result

MST edges: C-F(1), A-F(2), D-E(2), C-D(3), A-B(4)

Total MST weight: 1 + 2 + 2 + 3 + 4 = 12

The algorithm selected exactly V-1 = 5 edges, connecting all 6 vertices with minimum total weight.

7. Advantages and Disadvantages

Advantages

• Simple conceptually: The idea of sorting edges and picking the cheapest non-cycle-forming edge is intuitive.
• Efficient for sparse graphs: When E is much smaller than V^2, the O(E log E) time is very fast.
• Edge-list representation: Works naturally with an edge list, no adjacency list or matrix needed.
• Parallelizable: The sorting step and Union-Find operations can be parallelized for large-scale graphs.
• Minimum spanning forest: Naturally handles disconnected graphs, producing a minimum spanning forest.

Disadvantages

• Requires sorting: The initial sort of all edges can be expensive for very large edge sets.
• Not incremental: Adding a new edge or vertex requires re-running the algorithm (unlike some dynamic MST algorithms).
• Slower on dense graphs: For dense graphs, Prim's algorithm with a Fibonacci heap is asymptotically faster.

8. Comparison with Prim's Algorithm

9. Applications

• Network design: Laying out the minimum cost cable, pipeline, or road network connecting a set of locations.
• Cluster analysis: Single-linkage clustering can be performed by removing the heaviest edges from the MST.
• Approximation algorithms: The MST is used as a starting point for approximation algorithms for NP-hard problems like the Traveling Salesman Problem.
• Image segmentation: Graph-based image segmentation methods use variants of MST algorithms to partition pixel graphs.
• Circuit design: Minimizing the total wire length needed to connect components on a circuit board.

10. References

1. Kruskal, J. B. (1956). "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society, 7(1), 48-50.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 23.
3. Tarjan, R. E. (1975). "Efficiency of a Good But Not Linear Set Union Algorithm." Journal of the ACM, 22(2), 215-225.
4. Sedgewick, R. and Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Section 4.3.
5. Dasgupta, S., Papadimitriou, C., and Vazirani, U. (2006). Algorithms. McGraw-Hill. Chapter 5.