Edge-Based MST Construction - Kruskal's Algorithm — Edge-Centric MST Construction | OneNoughtOne

0/361

Data Structures & AlgorithmsKruskal's Algorithm

Kruskal's Algorithm — Edge-Centric MST Construction

LevelAdvanced

Duration75 mins

TopicKruskal's Algorithm

1 / 4

Edge-Based MST Construction

A Different Perspective on Spanning Trees

When faced with the challenge of connecting a network at minimum cost, two fundamentally different strategies emerge. Prim's algorithm asks: "Starting from one vertex, which is the cheapest edge that extends my growing tree?" But there's an alternative perspective that's equally powerful and, in many ways, more elegant.

Kruskal's algorithm poses a different question: "Among all the edges in the graph, which is the globally cheapest edge that I can safely add without creating a cycle?"

This distinction—between vertex-centric and edge-centric thinking—represents one of the most important paradigm shifts in algorithm design. Where Prim builds outward from a seed, Kruskal assembles a forest that gradually coalesces into a single tree. Both approaches yield optimal minimum spanning trees, but they embody different philosophies about how to decompose complex optimization problems.

What You Will Learn

By the end of this page, you will understand the edge-centric philosophy underlying Kruskal's algorithm, grasp why processing edges globally (rather than locally from a vertex) correctly produces an MST, and develop intuition for the forest-to-tree construction paradigm that distinguishes Kruskal's approach.

The Paradigm Shift: From Vertices to Edges

To appreciate Kruskal's algorithm, we must first understand how fundamentally it differs from vertex-centric approaches. This isn't merely a difference in implementation—it's a difference in how we conceptualize the problem.

The Vertex-Centric View (Prim's approach):

In Prim's algorithm, we maintain a single connected component that grows one vertex at a time. At each step, we:

Examine all edges crossing from our tree into unexplored territory
Select the minimum-weight such edge
Add the new vertex to our tree
Repeat until all vertices are included

The invariant is clear: we always maintain exactly one connected component, which grows until it encompasses all vertices.

The Edge-Centric View (Kruskal's approach):

Kruskal's algorithm takes a radically different stance. We don't maintain a single growing tree—instead, we maintain a forest of trees that gradually merge:

Initially, every vertex is its own trivial tree (a forest of V isolated vertices)
Process edges in order of increasing weight
For each edge, add it if it connects two different trees (doesn't create a cycle)
The forest coalesces until only one tree remains—the MST

Vertex-Centric vs Edge-Centric MST Construction
Aspect	Prim's (Vertex-Centric)	Kruskal's (Edge-Centric)
Primary entity	Vertices adjacent to tree	All edges in graph
Selection criterion	Local: cheapest edge from tree	Global: cheapest unused edge
Data structure state	One growing tree	Forest of merging trees
Processing order	Determined by tree frontier	Predetermined by edge weights
Starting point	Arbitrary root vertex	No explicit starting point
Key invariant	Single connected component	No cycles in forest
Graph traversal pattern	Expanding wavefront	Edge-list iteration
Termination condition	All vertices in tree	V-1 edges added (or all processed)

Two Valid Greedy Strategies

Both Prim's and Kruskal's algorithms are greedy, but they're greedy in different ways. Prim is locally greedy: at each step, it makes the best decision relative to the current tree. Kruskal is globally greedy: it processes globally-cheapest edges first, regardless of any particular vertex. The remarkable fact that both produce optimal MSTs is guaranteed by the Cut Property of minimum spanning trees.

The Forest-to-Tree Construction Model

The most distinctive feature of Kruskal's algorithm is its forest-to-tree construction model. Understanding this model is crucial for grasping why the algorithm works and how to implement it correctly.

Initial State: A Forest of Singletons

When Kruskal's algorithm begins, we conceptualize the graph as follows:

Every vertex starts as its own tree (a tree containing exactly one vertex)
There are V trees, each with 0 edges
This collection of trees forms a forest—a disjoint collection of trees

Mathematically, if our vertex set is V = {v₀, v₁, v₂, ..., vₙ₋₁}, then our initial forest is:

F₀ = {{v₀}, {v₁}, {v₂}, ..., {vₙ₋₁}}

Each singleton set represents a trivial tree. The goal is to merge these trees until the forest contains exactly one tree—the MST.

initial-forest.txt

Graph with 6 vertices: A, B, C, D, E, F
 
Initial Forest (iteration 0):
┌─────────────────────────────────────────────────┐
│                                                 │
│     (A)      (B)      (C)      (D)      (E)      (F)     │
│    Tree₁   Tree₂   Tree₃   Tree₄   Tree₅   Tree₆  │
│                                                 │
└─────────────────────────────────────────────────┘
 
Number of trees: 6
Edges in MST so far: 0
Status: Forest of 6 singleton trees

The Merging Process

As Kruskal's algorithm processes edges, two things can happen:

Tree Merger: If an edge connects vertices in different trees, adding this edge merges those two trees into one. The number of trees in our forest decreases by 1.
Edge Rejection: If an edge connects vertices in the same tree, adding it would create a cycle. We reject this edge and move on.

Key Insight: Every Safe Edge Reduces the Forest Size

When we find an edge (u, v) where u and v belong to different trees, adding this edge is always safe (doesn't create a cycle) and must reduce our forest size by exactly one. Before adding the edge, u's tree and v's tree were separate; after adding it, they're united.

This leads to a beautiful invariant:

After adding k safe edges, our forest contains exactly (V - k) trees.

Since an MST of V vertices has exactly (V - 1) edges, we're done when we've added (V - 1) edges, at which point our forest contains exactly 1 tree—the MST.

forest-evolution.txt

Example Graph:
    1       4       2
A───────B───────C───────D
│       │               │
│ 5     │ 3             │ 6
│       │               │
E───────F───────────────+
    2
 
Edges sorted by weight: AB(1), CF(2), EF(2), BF(3), BC(4), AE(5), DF(6)
 
═══════════════════════════════════════════════════════════════════
Step 0: Initial forest
═══════════════════════════════════════════════════════════════════
Trees: {A}, {B}, {C}, {D}, {E}, {F}
Number of trees: 6
MST edges: []
 
═══════════════════════════════════════════════════════════════════
Step 1: Process edge AB (weight 1)
═══════════════════════════════════════════════════════════════════
A and B are in DIFFERENT trees → ADD edge
Trees: {A,B}, {C}, {D}, {E}, {F}
Number of trees: 5  (decreased by 1)
MST edges: [AB(1)]
 
═══════════════════════════════════════════════════════════════════
Step 2: Process edge CF (weight 2)
═══════════════════════════════════════════════════════════════════
C and F are in DIFFERENT trees → ADD edge
Trees: {A,B}, {C,F}, {D}, {E}
Number of trees: 4  (decreased by 1)
MST edges: [AB(1), CF(2)]
 
═══════════════════════════════════════════════════════════════════
Step 3: Process edge EF (weight 2)
═══════════════════════════════════════════════════════════════════
E and F are in DIFFERENT trees → ADD edge
Trees: {A,B}, {C,E,F}, {D}
Number of trees: 3  (decreased by 1)
MST edges: [AB(1), CF(2), EF(2)]
 
═══════════════════════════════════════════════════════════════════
Step 4: Process edge BF (weight 3)
═══════════════════════════════════════════════════════════════════
B and F are in DIFFERENT trees → ADD edge
Trees: {A,B,C,E,F}, {D}
Number of trees: 2  (decreased by 1)
MST edges: [AB(1), CF(2), EF(2), BF(3)]
 
═══════════════════════════════════════════════════════════════════
Step 5: Process edge BC (weight 4)
═══════════════════════════════════════════════════════════════════
B and C are in SAME tree {A,B,C,E,F} → REJECT (would create cycle)
Trees unchanged: {A,B,C,E,F}, {D}
Number of trees: 2
MST edges unchanged: [AB(1), CF(2), EF(2), BF(3)]
 
═══════════════════════════════════════════════════════════════════
Step 6: Process edge AE (weight 5)
═══════════════════════════════════════════════════════════════════
A and E are in SAME tree {A,B,C,E,F} → REJECT (would create cycle)
Trees unchanged: {A,B,C,E,F}, {D}
Number of trees: 2
MST edges unchanged: [AB(1), CF(2), EF(2), BF(3)]
 
═══════════════════════════════════════════════════════════════════
Step 7: Process edge DF (weight 6)
═══════════════════════════════════════════════════════════════════
D and F are in DIFFERENT trees → ADD edge
Trees: {A,B,C,D,E,F}
Number of trees: 1  (DONE! Only one tree)
MST edges: [AB(1), CF(2), EF(2), BF(3), DF(6)]
 
═══════════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════════
MST Edges: AB(1) + CF(2) + EF(2) + BF(3) + DF(6)
Total Weight: 1 + 2 + 2 + 3 + 6 = 14
Edges selected: 5 = V - 1 ✓

The Forest Count Invariant

At every step of Kruskal's algorithm, the number of trees equals V minus the number of edges added to the MST. This invariant provides both a correctness check during implementation and an alternative termination condition: stop when forest size equals 1, or equivalently, when (V - 1) edges have been added.

Why Edge-Centric Greedy Works

The correctness of Kruskal's algorithm hinges on two fundamental properties of minimum spanning trees: the Cut Property and the Cycle Property. Understanding these properties reveals why the seemingly simple strategy of "take the cheapest safe edge" produces optimal results.

The Cut Property (Why Adding Cheap Edges is Safe)

A cut in a graph is a partition of vertices into two non-empty sets S and V\S. A cut edge (or crossing edge) is an edge with one endpoint in S and one in V\S.

Cut Property: For any cut of a graph, the minimum-weight crossing edge belongs to every MST of the graph (assuming unique edge weights; with ties, at least one minimum-weight crossing edge is in some MST).

How Kruskal's Uses the Cut Property:

When Kruskal considers an edge (u, v) connecting two different trees T₁ and T₂, it's implicitly looking at the cut that separates T₁ from the rest of the graph. If (u, v) is the minimum-weight edge crossing this cut (which it is, because we process edges in sorted order and haven't used any smaller edge connecting these trees), then by the Cut Property, (u, v) belongs to some MST.

Moreover, since we process edges in ascending weight order, the first edge we find connecting any two components is guaranteed to be the smallest such edge—exactly what the Cut Property demands.

cut-property.txt

The Cut Property in Action:
 
         Tree T₁                    Tree T₂
    ┌───────────────┐          ┌───────────────┐
    │               │          │               │
    │   (A)───(B)   │   e₁=7   │   (D)───(E)   │
    │     \       ←─┼──────────┼→     │        │
    │      \        │          │      │        │
    │       (C)   ←─┼───e₂=3───┼→    (F)       │
    │               │    ↑     │               │
    └───────────────┘    │     └───────────────┘
                         │
                    Minimum weight
                    crossing edge
 
The cut separates T₁ = {A,B,C} from T₂ = {D,E,F}
 
Crossing edges:
  - e₁ (B→D): weight 7
  - e₂ (C→F): weight 3  ← Minimum!
 
By Cut Property: e₂ with weight 3 belongs to the MST.
 
In Kruskal's: When we process edge e₂ (weight 3):
  - It's the first edge we encounter connecting T₁ and T₂
  - (Because all smaller edges were either rejected or connected 
     vertices within the same tree)
  - Therefore, it's the minimum crossing edge → belongs to MST

The Cycle Property (Why Rejecting Edges is Correct)

The Cycle Property provides the complementary guarantee—that we're not missing MST edges when we reject them:

Cycle Property: For any cycle in a graph, the maximum-weight edge in the cycle does not belong to any MST (assuming unique weights; with ties, at least one maximum-weight edge is not in any MST).

How Kruskal's Uses the Cycle Property:

When Kruskal considers an edge (u, v) where u and v are already in the same tree, adding this edge would create a cycle. But here's the key insight: because we process edges in ascending weight order, any edge we consider that would create a cycle is the heaviest edge in that cycle (all other edges in the cycle were added earlier, hence have smaller weights).

By the Cycle Property, the heaviest edge in any cycle cannot be in the MST. Therefore, rejecting this edge is not just safe—it's necessary.

The Critical Insight

The combination of processing edges in sorted order and the Cut/Cycle Properties means that Kruskal's algorithm never makes a wrong decision. Every edge it adds must be in the MST (Cut Property applied to the current forest), and every edge it rejects cannot be in the MST (Cycle Property applied to the cycle that would form).

cycle-property.txt

The Cycle Property in Action:
 
Suppose we've already added edges to form this partial tree:
 
            1                 3
    (A)─────────(B)─────────(C)
      \                     /
       \                   /
     2  \                 / 4
         \               /
          \             /
           (D)────────(E)
                 2
 
Edges in current tree: A-B(1), A-D(2), B-C(3), D-E(2), C-E(4)
Wait, that's 5 edges for 5 vertices - already a spanning tree!
 
Now we encounter edge B-D with weight 5:
 
            1                 3
    (A)─────────(B)─────────(C)
      \         ╎           /
       \        ╎5         /
     2  \       ╎         / 4
         \      ╎        /
          \     ╎       /
           (D)──╫──────(E)
                ╎  2
                ╎
        Edge being considered
 
If we add B-D, we create cycle: A → B → D → A
Edge weights in cycle: A-B(1), B-D(5), A-D(2)
 
The new edge B-D (weight 5) is the MAXIMUM weight in this cycle.
By Cycle Property: Maximum weight edge doesn't belong to MST.
Therefore: CORRECTLY REJECT B-D.
 
Note: We're guaranteed B-D is the maximum because we process 
edges in ascending order - all other edges in the cycle were 
already added (so they have smaller weights).

The Global Perspective Advantage

One of the most elegant aspects of Kruskal's algorithm is its global perspective. Rather than being tied to any particular vertex or growing tree, Kruskal examines all edges from a bird's-eye view and processes them in order of attractiveness (weight).

Benefits of the Edge-Centric Global View:

1. No Starting Point Dependency

Prim's algorithm requires choosing a starting vertex. While the final MST is the same regardless of starting point (assuming a unique MST), the construction order differs. Kruskal has no such dependency—the algorithm doesn't care about any particular vertex. This conceptual simplicity often translates to cleaner implementations.

2. Natural Parallelism Potential

Because Kruskal processes edges globally rather than expanding from a frontier, the sorted edge list can be determined independently. In parallel computing contexts, this preprocessing step (sorting) is highly amenable to parallel algorithms. The merging phase, while having dependencies, is still more parallelizable than Prim's expanding frontier.

3. Works on Disconnected Graphs

If your graph isn't connected, Prim's algorithm (starting from one vertex) will only find a spanning tree of the connected component containing the start vertex. Kruskal naturally handles disconnected graphs—it will find a minimum spanning forest, with one tree per connected component. This is often exactly what you want.

4. Intuitive for Sparse Graphs

When the graph has few edges relative to vertices (sparse), processing all edges is quite fast. Kruskal's O(E log E) complexity is particularly attractive when E is much smaller than V².

Prim's: Local, Vertex-Centric

•Requires a starting vertex
•Maintains one connected component
•Frontier-based expansion
•Locality of reference (good cache behavior)
•Natural fit for dense graphs (adjacency matrix)
•Doesn't naturally handle disconnected graphs
•Priority queue keyed on vertices

Kruskal's: Global, Edge-Centric

•No starting point needed
•Maintains a forest of components
•Sorted edge list iteration
•Requires random access to components
•Natural fit for sparse graphs (edge list)
•Produces minimum spanning forest
•Union-Find on vertex sets

When Edge-Centric Shines

Choose Kruskal's edge-centric approach when: (1) the graph is sparse, (2) edges are already sorted or easy to sort, (3) you need a minimum spanning forest rather than tree, or (4) the graph is given as an edge list rather than adjacency structure. The global perspective makes Kruskal's particularly elegant for these scenarios.

Formalizing the Algorithm

With the conceptual foundation established, let's formalize Kruskal's algorithm precisely. The algorithm has two main phases: preparation (sorting edges) and construction (iterating and filtering).

Formal Algorithm Description:

Input: A connected, weighted, undirected graph G = (V, E) with weight function w: E → ℝ Output: A set of edges T forming a minimum spanning tree of G

Procedure:

Initialize T = ∅ (empty set of MST edges)
Sort all edges E in non-decreasing order by weight
Initialize a data structure DS to track connected components (each vertex starts in its own component)
For each edge (u, v) in sorted order:
- If DS.Find(u) ≠ DS.Find(v):
  - Add (u, v) to T
  - DS.Union(u, v)
- If |T| = |V| - 1, terminate early
Return T

kruskal-pseudocode.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def kruskal_mst(graph):
    """
    Compute the Minimum Spanning Tree using Kruskal's algorithm.
    
    Args:
        graph: Object with 'vertices' (set) and 'edges' (list of (u, v, weight))
    
    Returns:
        List of edges forming the MST, or None if graph is disconnected
    """
    V = graph.vertices
    E = graph.edges
    n = len(V)
    
    # Phase 1: Preparation - Sort edges by weight
    sorted_edges = sorted(E, key=lambda edge: edge[2])  # Sort by weight
    
    # Phase 2: Initialize Union-Find (each vertex is its own component)
    uf = UnionFind(V)
    
    # Phase 3: Construction - Greedily select edges
    mst_edges = []
    
    for u, v, weight in sorted_edges:
        # Check if u and v are in different components
        if uf.find(u) != uf.find(v):
            # Safe to add this edge (won't create cycle)
            mst_edges.append((u, v, weight))
            uf.union(u, v)
            
            # Early termination: MST found when we have n-1 edges
            if len(mst_edges) == n - 1:
                break
    
    # Verify MST was found (graph was connected)
    if len(mst_edges) != n - 1:
        return None  # Graph was disconnected
    
    return mst_edges

Algorithm Walkthrough:

Phase 1: Edge Sorting

The first critical step is sorting all edges by weight. This preprocessing step determines the greedy order in which we'll consider edges. The sorting typically takes O(E log E) time, which as we'll see later, dominates the algorithm's complexity.

Phase 2: Component Initialization

We need a data structure that can efficiently:

Determine which component a vertex belongs to (Find)
Merge two components when we add an edge (Union)

The Union-Find (Disjoint Set Union) data structure is perfect for this, providing near-constant time operations. We'll explore Union-Find in detail in a later page.

Phase 3: Greedy Edge Selection

We iterate through sorted edges, using Union-Find to check if an edge connects different components. If it does, we add it to our MST and merge the components. If not, we skip it (it would create a cycle).

Early Termination:

Once we've added (V - 1) edges, we've constructed a spanning tree. Any additional edges would necessarily create cycles, so we can stop immediately.

The Union-Find Dependency

Kruskal's algorithm's efficiency critically depends on Union-Find. With a naive 'search all vertices' approach for component detection, the algorithm would be O(E × V). With Union-Find using path compression and union by rank, component operations are nearly O(1), making the total algorithm O(E log E) dominated by sorting.

Tracing Through a Complete Example

Let's trace through Kruskal's algorithm on a complete example to solidify understanding. We'll track every decision, showing how the forest evolves and why each edge is accepted or rejected.

kruskal-trace.txt

═══════════════════════════════════════════════════════════════════════════
GRAPH DEFINITION
═══════════════════════════════════════════════════════════════════════════
 
Vertices: {0, 1, 2, 3, 4, 5}
 
Edges (unsorted):
  0--1: weight 4
  0--2: weight 3
  1--2: weight 1
  1--3: weight 2
  2--3: weight 4
  3--4: weight 2
  4--5: weight 6
  2--5: weight 5
  1--4: weight 2
 
Visual representation:
         4
    0─────────1
    │\       /│\
    │ \3   1/ │ \2
    │  \   /  │2 \
    │   \ /   │   \
    3    2────3────4
         │    │   /
       5 │  2 │  /6
         │    │ /
         └────5
 
═══════════════════════════════════════════════════════════════════════════
PHASE 1: SORT EDGES
═══════════════════════════════════════════════════════════════════════════
 
Sorted edges by weight:
  Index 0: (1,2) weight 1
  Index 1: (1,3) weight 2
  Index 2: (3,4) weight 2
  Index 3: (1,4) weight 2
  Index 4: (0,2) weight 3
  Index 5: (0,1) weight 4
  Index 6: (2,3) weight 4
  Index 7: (2,5) weight 5
  Index 8: (4,5) weight 6
 
═══════════════════════════════════════════════════════════════════════════
PHASE 2: INITIALIZE UNION-FIND
═══════════════════════════════════════════════════════════════════════════
 
Initial state - each vertex is its own component:
  Component(0) = {0}
  Component(1) = {1}
  Component(2) = {2}
  Component(3) = {3}
  Component(4) = {4}
  Component(5) = {5}
 
Forest: 6 trees, 0 edges in MST
 
═══════════════════════════════════════════════════════════════════════════
PHASE 3: PROCESS EDGES IN SORTED ORDER
═══════════════════════════════════════════════════════════════════════════
 
───────────────────────────────────────────────────────────────────────────
Edge 0: (1,2) weight 1
───────────────────────────────────────────────────────────────────────────
  Find(1) = 1
  Find(2) = 2
  1 ≠ 2 → Different components → ADD EDGE ✓
  
  Union(1, 2) - merge components
  
  Updated components:
    {0}, {1,2}, {3}, {4}, {5}
  
  MST edges so far: [(1,2, w=1)]
  MST weight so far: 1
  Forest: 5 trees
 
───────────────────────────────────────────────────────────────────────────
Edge 1: (1,3) weight 2
───────────────────────────────────────────────────────────────────────────
  Find(1) = representative of {1,2}
  Find(3) = 3
  Different components → ADD EDGE ✓
  
  Union(1, 3) - merge {1,2} with {3}
  
  Updated components:
    {0}, {1,2,3}, {4}, {5}
  
  MST edges so far: [(1,2, w=1), (1,3, w=2)]
  MST weight so far: 3
  Forest: 4 trees
 
───────────────────────────────────────────────────────────────────────────
Edge 2: (3,4) weight 2
───────────────────────────────────────────────────────────────────────────
  Find(3) = representative of {1,2,3}
  Find(4) = 4
  Different components → ADD EDGE ✓
  
  Union(3, 4)
  
  Updated components:
    {0}, {1,2,3,4}, {5}
  
  MST edges so far: [(1,2, w=1), (1,3, w=2), (3,4, w=2)]
  MST weight so far: 5
  Forest: 3 trees
 
───────────────────────────────────────────────────────────────────────────
Edge 3: (1,4) weight 2
───────────────────────────────────────────────────────────────────────────
  Find(1) = representative of {1,2,3,4}
  Find(4) = representative of {1,2,3,4}
  SAME component → REJECT EDGE ✗ (would create cycle)
  
  Components unchanged:
    {0}, {1,2,3,4}, {5}
  
  MST edges unchanged
  Forest: 3 trees
 
───────────────────────────────────────────────────────────────────────────
Edge 4: (0,2) weight 3
───────────────────────────────────────────────────────────────────────────
  Find(0) = 0
  Find(2) = representative of {1,2,3,4}
  Different components → ADD EDGE ✓
  
  Union(0, 2)
  
  Updated components:
    {0,1,2,3,4}, {5}
  
  MST edges so far: [(1,2), (1,3), (3,4), (0,2)]
  MST weight so far: 8
  Forest: 2 trees
 
───────────────────────────────────────────────────────────────────────────
Edge 5: (0,1) weight 4
───────────────────────────────────────────────────────────────────────────
  Find(0) = representative of {0,1,2,3,4}
  Find(1) = representative of {0,1,2,3,4}
  SAME component → REJECT EDGE ✗
  
  Forest: 2 trees
 
───────────────────────────────────────────────────────────────────────────
Edge 6: (2,3) weight 4
───────────────────────────────────────────────────────────────────────────
  Find(2) = representative of {0,1,2,3,4}
  Find(3) = representative of {0,1,2,3,4}
  SAME component → REJECT EDGE ✗
  
  Forest: 2 trees
 
───────────────────────────────────────────────────────────────────────────
Edge 7: (2,5) weight 5
───────────────────────────────────────────────────────────────────────────
  Find(2) = representative of {0,1,2,3,4}
  Find(5) = 5
  Different components → ADD EDGE ✓
  
  Union(2, 5)
  
  Updated components:
    {0,1,2,3,4,5} - ALL VERTICES IN ONE COMPONENT!
  
  MST edges: [(1,2), (1,3), (3,4), (0,2), (2,5)]
  Total: 5 edges = V - 1 = 6 - 1 ✓
  
  ALGORITHM TERMINATES! (We have V-1 edges)
 
═══════════════════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════════════════
 
Minimum Spanning Tree edges:
  (1,2) weight 1
  (1,3) weight 2
  (3,4) weight 2
  (0,2) weight 3
  (2,5) weight 5
  ─────────────────
  Total MST weight: 13
 
MST visualization:
         
    0           1
    │          /│
    │3       1/ │2
    │        /  │
    │       /   │
         2      3────4
         │          
       5 │          
         │          
         5

Key Observations from the Trace

Notice how the algorithm processed 8 edges total but added only 5 to the MST. Three edges were rejected because they would have created cycles. The algorithm terminated early after adding the 5th edge (before processing edge 8) because we had V-1 = 5 edges, forming a complete spanning tree.

Edge Cases and Special Scenarios

Understanding how Kruskal's algorithm behaves in edge cases is crucial for robust implementation and correct application.

Case 1: Disconnected Graphs

If the input graph is not connected, Kruskal's algorithm cannot produce a spanning tree (no spanning tree exists). However, it will produce a minimum spanning forest—a collection of MSTs, one for each connected component.

Detection: After processing all edges, if we've added fewer than (V - 1) edges, the graph was disconnected.

Case 2: Graphs with Equal Weight Edges

When multiple edges have the same weight, the MST may not be unique. Kruskal's algorithm will produce one valid MST, but different tie-breaking strategies (or different sort algorithms with different stability properties) may produce different valid MSTs.

Case 3: Single Vertex Graph

A graph with one vertex and no edges has a trivial MST: the empty edge set. V - 1 = 0 edges are needed. The algorithm handles this correctly by immediately terminating.

Case 4: Already a Tree

If the input graph is already a tree (connected, V vertices, V-1 edges, no cycles), Kruskal's algorithm will accept all V-1 edges. Every edge connects vertices in different components until the final edge unifies everything.

edge-cases.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def kruskal_mst_robust(graph):
    """
    Robust Kruskal's implementation handling all edge cases.
    """
    n = len(graph.vertices)
    
    # Edge case: Empty graph or single vertex
    if n == 0:
        return [], 0, "Empty graph"
    if n == 1:
        return [], 0, "Single vertex - trivial MST"
    
    # Sort edges
    sorted_edges = sorted(graph.edges, key=lambda e: e[2])
    
    # Initialize Union-Find
    uf = UnionFind(graph.vertices)
    
    mst_edges = []
    total_weight = 0
    
    for u, v, weight in sorted_edges:
        if uf.find(u) != uf.find(v):
            mst_edges.append((u, v, weight))
            total_weight += weight
            uf.union(u, v)
            
            if len(mst_edges) == n - 1:
                break
    
    # Determine result type
    if len(mst_edges) == n - 1:
        # Connected graph - complete MST found
        return mst_edges, total_weight, "MST found"
    else:
        # Disconnected graph - this is a minimum spanning forest
        num_components = n - len(mst_edges)
        return mst_edges, total_weight, f"MSF with {num_components} components"
 
 
# Example: Disconnected graph
disconnected = Graph(
    vertices={0, 1, 2, 3, 4},
    edges=[
        (0, 1, 1),  # Component 1: {0, 1, 2}
        (1, 2, 2),
        (3, 4, 3),  # Component 2: {3, 4}
    ]
)
 
edges, weight, status = kruskal_mst_robust(disconnected)
# Result: 3 edges, weight 6, "MSF with 2 components"

Edge Case Handling Summary
Scenario	Input	Kruskal's Output	Notes
Empty graph	V=0, E=0	Empty MST, weight 0	Trivial case
Single vertex	V=1, E=0	Empty MST, weight 0	No edges needed
Disconnected	V=n, graph not connected	MSF with k < n-1 edges	One MST per component
Already a tree	V=n, E=n-1, connected	All n-1 edges selected	No rejections occur
Complete graph	V=n, E=n(n-1)/2	n-1 edges, many rejected	Most edges form cycles
Equal weights	Multiple edges same weight	One valid MST (not unique)	Tie-breaking arbitrary

Summary: The Edge-Centric Philosophy

We've explored the foundational concepts of Kruskal's algorithm—an elegant, edge-centric approach to constructing minimum spanning trees. Let's consolidate the key insights:

Key Takeaways

•Edge-Centric vs Vertex-Centric: Kruskal's algorithm processes edges globally (sorted by weight) rather than expanding from a vertex. This paradigm shift leads to different algorithmic patterns and implementation strategies.
•Forest-to-Tree Model: The algorithm starts with V singleton trees and progressively merges them. Each safe edge reduces the forest size by one until only the MST remains.
•Cut Property Guarantees Correctness: Every edge Kruskal adds is the minimum-weight edge crossing some cut, ensuring it belongs to the MST.
•Cycle Property Justifies Rejections: Every edge Kruskal rejects would be the maximum-weight edge in some cycle, so it cannot be in the MST.
•Global Perspective Benefits: No starting point, natural handling of disconnected graphs, and suitability for sparse graphs with edge-list representations.
•Union-Find is Essential: Efficient component tracking via Union-Find is what makes Kruskal's algorithm practical. Without it, cycle detection would be prohibitively slow.

What's Next:

In the next page, we'll dive deep into the sorting phase of Kruskal's algorithm. We'll explore:

Why edge sorting dominates the algorithm's complexity
How different sorting algorithms affect overall performance
Practical considerations for handling large edge sets
Alternative approaches when edges come pre-sorted or in special order

Page Complete

You now understand the edge-centric philosophy underlying Kruskal's algorithm. The forest-to-tree construction model, backed by the Cut and Cycle Properties, provides a rigorous foundation for understanding why this elegant algorithm correctly produces minimum spanning trees.