Understanding Kruskal’s Algorithm
1 Introduction
Kruskal’s algorithm is another classic method for finding a Minimum Spanning Tree
(MST) in a connected, undirected, weighted graph. Whereas Prim’s algorithm grows the
MST by starting from a single vertex and repeatedly selecting the minimum-weight edge
connecting the tree to an external vertex, Kruskal’s algorithm takes an edge-centric ap-
proach:
• Sort all edges by their weights in non-decreasing order.
• Examine edges from lightest to heaviest, adding each edge to the MST if it does not
create a cycle.
This approach is often paired with a disjoint set (union–find) data structure to quickly
detect and prevent cycles.
2 Key Ideas
• Spanning Tree: For a connected, undirected graph G = (V, E), a spanning tree is a
subset of edges that connects all vertices together without any cycle.
• Minimum Spanning Tree (MST): Of all possible spanning trees, the MST has the
smallest total sum of edge weights.
• Kruskal’s Algorithm (Intuition):
– Sort all edges by weight (from smallest to largest).
– Keep adding edges to the MST in this sorted order only if the edge does not
introduce a cycle.
– Stop when you have (n − 1) edges in the MST (where n = |V |).
3 Step-by-Step Description
Let G = (V, E) be a connected, undirected, weighted graph with |V | = n. Each edge (u, v)
has a weight w(u, v).
1
1. Sort all edges: Sort the edge set E by weight in non-decreasing order. Let the sorted
list of edges be e1 , e2 , . . . , em where m = |E| and w(e1 ) ≤ w(e2 ) ≤ · · · ≤ w(em ).
2. Initialize: Let MST be initially empty (no edges). We will also maintain a disjoint
set (union–find) data structure, where each vertex v ∈ V is initially in its own set.
3. Process edges in ascending weight order: For each edge ei (from lightest to
heaviest):
(a) Let ei connect vertices u and v.
(b) Check if u and v are in the same set (i.e., check if they are already connected via
the edges in the MST).
• If they are in the same set, adding ei would form a cycle. Skip this edge.
• If they are in different sets, union the two sets and include ei in the MST.
4. Termination: Once we have added (n − 1) edges to the MST, or we have processed
all edges, the set of chosen edges forms a minimum spanning tree.
4 Why No Cycles Can Occur
4.1 Cycle Detection via Union–Find
Kruskal’s algorithm naturally checks for cycles using a disjoint set (union–find) structure:
• Each vertex is initially in its own component (set).
• When an edge connects two vertices in different components, the components are
merged. Because there was no existing path between them in the MST, this cannot
create a cycle.
• If an edge connects two vertices already in the same component, a cycle would form,
so the edge is skipped.
4.2 Alternative Cycle Checking
One could also keep track of edges in a separate graph structure and look for cycles (using,
for instance, a depth-first search). But union–find is much more efficient for the repeated
cycle checks required in Kruskal’s.
5 Example
Consider a graph with vertices {A, B, C, D, E} and the following edge weights:
A − B : 2, A − C : 3, B − D : 3, B − C : 5,
C − D : 6, C − E : 4, D − E : 2.
2
1. Sort edges by weight:
(A, B) : 2, (D, E) : 2, (A, C) : 3, (B, D) : 3, (C, E) : 4, (B, C) : 5, (C, D) : 6.
2. Initialize union–find: Each vertex is in its own set: {A}, {B}, {C}, {D}, {E}.
3. Process edges in ascending order:
• (A, B) : 2: Different sets. MST = {(A, B)}. Union sets of A and B.
• (D, E) : 2: Different sets. MST = {(A, B), (D, E)}. Union sets of D and E.
• (A, C) : 3: Check sets of A and C. They differ. MST = {(A, B), (D, E), (A, C)}.
Union sets of A (and B) with C.
• (B, D) : 3: Now check sets of B and D. If they are in different sets, add edge;
otherwise skip.
– After previous unions, A, B, and C are in one set, and D, E are in another set.
So B and D are in different sets. Add (B, D). MST = {(A, B), (D, E), (A, C), (B, D)}.
• At this point, we have 4 edges in a graph of 5 vertices, which is the number we
need: n − 1 = 4. The MST is complete. (We do not need to process the remaining
edges.)
Hence the selected edges form a spanning tree ({(A, B), (A, C), (B, D), (D, E)} or some
slight variation depending on ties). No cycles are formed because the union–find structure
prevents adding any edge that would connect vertices already within the same set.
6 Conclusion
• Kruskal’s Algorithm is an edge-based strategy for finding an MST. Sorting edges
by weight and then selectively adding them (if they do not create a cycle) will yield a
minimum spanning tree.
• Cycle Avoidance is handled naturally via the disjoint set (union–find) data structure.
• Time Complexity: Sorting the edges takes O(m log m), and each union–find opera-
tion can be made almost O(1) with path compression and union by rank. Hence, the
overall complexity is O(m log m), where m = |E|.
