Loading learning content...
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.\n\nKruskal'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?"\n\nThis 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.
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.
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.\n\nThe Vertex-Centric View (Prim's approach):\n\nIn Prim's algorithm, we maintain a single connected component that grows one vertex at a time. At each step, we:\n1. Examine all edges crossing from our tree into unexplored territory\n2. Select the minimum-weight such edge\n3. Add the new vertex to our tree\n4. Repeat until all vertices are included\n\nThe invariant is clear: we always maintain exactly one connected component, which grows until it encompasses all vertices.\n\nThe Edge-Centric View (Kruskal's approach):\n\nKruskal'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:\n1. Initially, every vertex is its own trivial tree (a forest of V isolated vertices)\n2. Process edges in order of increasing weight\n3. For each edge, add it if it connects two different trees (doesn't create a cycle)\n4. The forest coalesces until only one tree remains—the MST
| 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) |
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 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.\n\nInitial State: A Forest of Singletons\n\nWhen Kruskal's algorithm begins, we conceptualize the graph as follows:\n- Every vertex starts as its own tree (a tree containing exactly one vertex)\n- There are V trees, each with 0 edges\n- This collection of trees forms a forest—a disjoint collection of trees\n\nMathematically, if our vertex set is V = {v₀, v₁, v₂, ..., vₙ₋₁}, then our initial forest is:\n\nF₀ = {{v₀}, {v₁}, {v₂}, ..., {vₙ₋₁}}\n\nEach singleton set represents a trivial tree. The goal is to merge these trees until the forest contains exactly one tree—the MST.
12345678910111213
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: 6Edges in MST so far: 0Status: Forest of 6 singleton treesThe Merging Process\n\nAs Kruskal's algorithm processes edges, two things can happen:\n\n1. 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.\n\n2. Edge Rejection: If an edge connects vertices in the same tree, adding it would create a cycle. We reject this edge and move on.\n\nKey Insight: Every Safe Edge Reduces the Forest Size\n\nWhen 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.\n\nThis leads to a beautiful invariant:\n\nAfter adding k safe edges, our forest contains exactly (V - k) trees.\n\nSince 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.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
Example Graph: 1 4 2A───────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: 6MST edges: [] ═══════════════════════════════════════════════════════════════════Step 1: Process edge AB (weight 1)═══════════════════════════════════════════════════════════════════A and B are in DIFFERENT trees → ADD edgeTrees: {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 edgeTrees: {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 edgeTrees: {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 edgeTrees: {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: 2MST 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: 2MST 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 edgeTrees: {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 = 14Edges selected: 5 = V - 1 ✓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.
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.\n\nThe Cut Property (Why Adding Cheap Edges is Safe)\n\nA 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.\n\nCut 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).\n\nHow Kruskal's Uses the Cut Property:\n\nWhen 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.\n\nMoreover, 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.
12345678910111213141516171819202122232425262728
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 MSTThe Cycle Property (Why Rejecting Edges is Correct)\n\nThe Cycle Property provides the complementary guarantee—that we're not missing MST edges when we reject them:\n\nCycle 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).\n\nHow Kruskal's Uses the Cycle Property:\n\nWhen 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).\n\nBy 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 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).
1234567891011121314151617181920212223242526272829303132333435363738394041
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 → AEdge 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).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).\n\nBenefits of the Edge-Centric Global View:\n\n1. No Starting Point Dependency\n\nPrim'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.\n\n2. Natural Parallelism Potential\n\nBecause 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.\n\n3. Works on Disconnected Graphs\n\nIf 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.\n\n4. Intuitive for Sparse Graphs\n\nWhen 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².
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.
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).\n\nFormal Algorithm Description:\n\nInput: A connected, weighted, undirected graph G = (V, E) with weight function w: E → ℝ\nOutput: A set of edges T forming a minimum spanning tree of G\n\nProcedure:\n1. Initialize T = ∅ (empty set of MST edges)\n2. Sort all edges E in non-decreasing order by weight\n3. Initialize a data structure DS to track connected components (each vertex starts in its own component)\n4. For each edge (u, v) in sorted order:\n - If DS.Find(u) ≠ DS.Find(v):\n - Add (u, v) to T\n - DS.Union(u, v)\n - If |T| = |V| - 1, terminate early\n5. Return T
123456789101112131415161718192021222324252627282930313233343536373839
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_edgesAlgorithm Walkthrough:\n\nPhase 1: Edge Sorting\n\nThe 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.\n\nPhase 2: Component Initialization\n\nWe need a data structure that can efficiently:\n- Determine which component a vertex belongs to (Find)\n- Merge two components when we add an edge (Union)\n\nThe 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.\n\nPhase 3: Greedy Edge Selection\n\nWe 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).\n\nEarly Termination:\n\nOnce we've added (V - 1) edges, we've constructed a spanning tree. Any additional edges would necessarily create cycles, so we can stop immediately.
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.
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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
═══════════════════════════════════════════════════════════════════════════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 │ │ 5Notice 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.
Understanding how Kruskal's algorithm behaves in edge cases is crucial for robust implementation and correct application.\n\nCase 1: Disconnected Graphs\n\nIf 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.\n\nDetection: After processing all edges, if we've added fewer than (V - 1) edges, the graph was disconnected.\n\nCase 2: Graphs with Equal Weight Edges\n\nWhen 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.\n\nCase 3: Single Vertex Graph\n\nA 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.\n\nCase 4: Already a Tree\n\nIf 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.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
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 graphdisconnected = 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"| 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 |
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:
What's Next:\n\nIn the next page, we'll dive deep into the sorting phase of Kruskal's algorithm. We'll explore:\n- Why edge sorting dominates the algorithm's complexity\n- How different sorting algorithms affect overall performance\n- Practical considerations for handling large edge sets\n- Alternative approaches when edges come pre-sorted or in special order
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.