How Kruskal's Algorithm Finds the Minimum Spanning Tree
This article provides a comprehensive breakdown of how Kruskal's algorithm operates within discrete mathematics to find the minimum spanning tree (MST) of a connected, weighted graph. It covers the fundamental definitions of spanning trees, the step-by-step greedy mechanics of the algorithm, the method used for cycle detection, and a practical example demonstrating the process from start to finish.
Understanding the Minimum Spanning Tree
In discrete mathematics, a graph is a collection of vertices (nodes) and edges (lines connecting the nodes). In a connected, undirected, and weighted graph, every vertex can reach every other vertex, the connections go both ways, and each edge has a numerical value (weight) representing cost, distance, or capacity.
A spanning tree is a subgraph that connects all the vertices together without creating any cycles (closed loops). If a graph has \(V\) vertices, a spanning tree will always have exactly \(V - 1\) edges. A Minimum Spanning Tree (MST) is the specific spanning tree where the sum of all the edge weights is the absolute minimum possible.
The Core Logic: A Greedy Approach
Kruskal's algorithm is classified as a "greedy" algorithm. This means it makes the locally optimal choice at each step with the goal of finding the global optimum.
Instead of starting at a specific vertex and exploring outwards, Kruskal's algorithm looks at the entire graph globally. It focuses entirely on the edges, prioritizing the lowest weights first. It builds the MST as a collection of separate trees (a forest) that gradually merge into a single tree.
Step-by-Step Execution
To find the MST of a graph with \(V\) vertices, Kruskal's algorithm follows these sequential steps:
- Initialize: Remove all edges so that every vertex in the graph is isolated. Each vertex currently acts as its own separate tree.
- Sort the Edges: Create a list of all the edges in the graph and sort them in non-decreasing order based on their weights (from smallest to largest).
- Select the Smallest Edge: Pull the first edge from the sorted list (the one with the lowest weight).
- Check for Cycles: Determine if adding this edge to
your growing MST will create a cycle.
- If it does not create a cycle, add the edge to the MST. This effectively merges two separate trees into one.
- If it does create a cycle, discard the edge and move on.
- Repeat: Continue iterating through the sorted list of edges, repeating steps 3 and 4, until your MST contains exactly \(V - 1\) edges. Once you hit this number, all vertices are connected, and the algorithm stops.
Preventing Cycles with Disjoint-Set
The most critical rule in Kruskal's algorithm is avoiding cycles. While a human can easily spot a loop in a small drawing, a computer relies on a specific data structure called a Disjoint-Set (or Union-Find) to do this mathematically.
The Disjoint-Set keeps track of which vertices are connected in the same tree using two main operations:
- Find: Checks which tree a specific vertex belongs
to. When evaluating an edge, the algorithm runs the
Findoperation on both of the edge's vertices. If they belong to the same tree, they are already connected by a path, meaning this new edge would create a cycle. - Union: If the
Findoperation shows the two vertices are in different trees, the edge is safe to add. TheUnionoperation then merges the two trees into a single set.
Practical Walkthrough
Imagine a graph with 4 vertices (A, B, C, D) and 5 weighted edges:
- Edge A-B (Weight: 1)
- Edge B-C (Weight: 4)
- Edge A-D (Weight: 3)
- Edge B-D (Weight: 2)
- Edge C-D (Weight: 5)
Here is how Kruskal's algorithm finds the MST:
Step 1: Sort the edges by weight.
- A-B (1)
- B-D (2)
- A-D (3)
- B-C (4)
- C-D (5)
Step 2: Process the edges.
- Evaluate A-B (1): Vertices A and B are in different sets. Add A-B to the MST. (Connected: {A, B}, {C}, {D})
- Evaluate B-D (2): Vertex B is in set {A, B} and D is in {D}. They are in different sets. Add B-D to the MST. (Connected: {A, B, D}, {C})
- Evaluate A-D (3): Both A and D are already in the same set {A, B, D}. Adding this edge would create the cycle A-B-D-A. Discard A-D.
- Evaluate B-C (4): Vertex B is in {A, B, D} and C is in {C}. They are in different sets. Add B-C to the MST. (Connected: {A, B, C, D})
Step 3: Terminate. The graph has 4 vertices (\(V = 4\)). We have successfully added 3 edges (\(V - 1 = 3\)). The algorithm stops immediately without needing to evaluate the final edge (C-D).
The Minimum Spanning Tree consists of edges A-B, B-D, and B-C, with a minimum total weight of 7 (\(1 + 2 + 4\)).