Minimum Spanning Trees: Step-by-Step Algorithms and Optimization

Verified Sources

May 26, 2026

In graph theory, finding the most efficient way to connect a set of locations or nodes is a fundamental optimization problem. This is formally solved using a Spanning Tree, which connects all vertices of a graph with the minimum possible number of edges.

When the graph's edges have weights (representing distances, costs, or latencies), we seek the Minimum Spanning Tree (MST) . Formally, given a connected, undirected graph $G = (V, E)$ with a weight function $w: E \to \mathbb{R}$ , an MST is a subset of edges $T \subseteq E$ that spans all vertices $V$ without any cycles, such that the total weight is minimized:

$w(T) = \sum_{e \in T} w(e)$

The construction of an MST relies heavily on the Cut Property . This mathematical property guarantees that greedy choices lead to a globally optimal solution.

Visualizing a Graph and its MST

Consider the following undirected weighted graph:

By applying an MST algorithm, we extract the optimal cycle-free backbone of the graph with a total cost of 8:

Introduction to Algorithms (Wikipedia) - Comprehensive overview of Minimum Spanning Trees, mathematical properties, and basic algorithms. ↩ ↩²

Greedy Algorithms: Prim's and Kruskal's Algorithms

Kruskal's Algorithm

Kruskal's algorithm is an edge-centric Greedy Algorithm . It builds the MST by sorting all edges from lowest weight to highest weight and adding them one by one, provided that the edge does not create a cycle.

To perform cycle detection efficiently, Kruskal's algorithm utilizes a Disjoint-Set Data Structure (also known as Union-Find) . Each vertex starts in its own set. For each edge $(u, v)$ , we check if $u$ and $v$ belong to the same set:

If they do, adding the edge would form a cycle; hence, we discard it.
If they do not, we add the edge to the MST and merge (union) the two sets.

The total time complexity of Kruskal's algorithm is:

$O(E \log E) \quad \text{or} \quad O(E \log V)$

This is because sorting the edges dominates the computational cost, while the subsequent Union-Find operations run in near-linear time $O(E \cdot \alpha(V))$ , where $\alpha$ is the extremely slow-growing inverse Ackermann function .

Kruskal's Algorithm (Wikipedia) - Detailed explanation of Kruskal's greedy approach, cycle detection, and Disjoint-Set Union complexity. ↩ ↩² ↩³

Kruskal's Algorithm Step-by-Step Walkthrough

1
Step 1
Begin by listing all edges in the graph and sorting them in non-decreasing order of their weights. At the start, each vertex is placed in its own individual disjoint set:

$(A, B)$ with weight 1

$(B, D)$ with weight 2

$(D, E)$ with weight 2

$(B, C)$ with weight 3

$(A, D)$ with weight 4

$(C, E)$ with weight 5

Initial sets: $\{A\}, \{B\}, \{C\}, \{D\}, \{E\}$ .
2
Step 2
Select the edge with the smallest weight, which is $(A, B)$ with weight 1. Check if vertices $A$ and $B$ belong to the same disjoint set. Since they do not, adding this edge will not form a cycle. We union the sets containing $A$ and $B$ , and add $(A, B)$ to our MST.

MST Edges: $\{(A, B)\}$ Active sets: $\{A, B\}, \{C\}, \{D\}, \{E\}$ Total weight: 1.
3
Step 3
Select the next smallest edge, $(B, D)$ with weight 2. Check if $B$ and $D$ are in the same disjoint set. Since $B \in \{A, B\}$ and $D \in \{D\}$ , they are in different sets. Add $(B, D)$ to the MST and union their sets.

MST Edges: $\{(A, B), (B, D)\}$ Active sets: $\{A, B, D\}, \{C\}, \{E\}$ Total weight: 1 + 2 = 3.
4
Step 4
Select the next smallest edge, $(D, E)$ with weight 2. Check if $D$ and $E$ are in the same disjoint set. Since $D \in \{A, B, D\}$ and $E \in \{E\}$ , they are in different sets. Add $(D, E)$ to the MST and union their sets.

MST Edges: $\{(A, B), (B, D), (D, E)\}$ Active sets: $\{A, B, D, E\}, \{C\}$ Total weight: 3 + 2 = 5.
5
Step 5
Select the next smallest edge, $(B, C)$ with weight 3. Check if $B$ and $C$ are in the same disjoint set. Since $B \in \{A, B, D, E\}$ and $C \in \{C\}$ , they are in different sets. Add $(B, C)$ to the MST and union their sets.

MST Edges: $\{(A, B), (B, D), (D, E), (B, C)\}$ Active sets: $\{A, B, C, D, E\}$ Total weight: 5 + 3 = 8.
6
Step 6
The MST now contains $V - 1 = 4$ edges. All vertices are fully connected in a single set. Any further edge evaluations (like $(A, D)$ or $(C, E)$ ) will be rejected because both vertices of those edges already belong to the same set $\{A, B, C, D, E\}$ , meaning their addition would form a cycle. The final Minimum Spanning Tree is complete with a total cost of 8.

Handling Disconnected Graphs

If the input graph is not fully connected, Kruskal's algorithm will not yield a single Minimum Spanning Tree. Instead, it will output a Minimum Spanning Forest, which is a collection of MSTs for each individual connected component .

Kruskal's Algorithm (Wikipedia) - Detailed explanation of Kruskal's greedy approach, cycle detection, and Disjoint-Set Union complexity. ↩

Prim's Algorithm

Prim's algorithm is a node-centric greedy algorithm . Instead of sorting all edges upfront, it starts with a single arbitrary root vertex and grows the spanning tree one vertex at a time.

At each step, the algorithm chooses the minimum-weight edge that connects a vertex already inside the growing tree to a vertex outside the tree. To do this efficiently, Prim's algorithm maintains a Priority Queue to keep track of the minimum connection costs of all unvisited vertices .

In terms of data representation, the graph is typically modeled using an Adjacency Matrix or an adjacency list.

The time complexity depends on the implementation:

Adjacency Matrix & linear scan: $O(V^2)$ (optimal for dense graphs) .
Adjacency List & Binary Heap: $O((E + V) \log V)$ .
Adjacency List & Fibonacci Heap: $O(E + V \log V)$ .

Prim's Algorithm (Wikipedia) - In-depth look at Prim's node-growing strategy, priority queue optimization, and complexity. ↩ ↩² ↩³ ↩⁴
Introduction to Algorithms (Wikipedia) - Comprehensive overview of Minimum Spanning Trees, mathematical properties, and basic algorithms. ↩

Prim's Algorithm Step-by-Step Walkthrough

1
Step 1
Choose an arbitrary vertex to begin. Let's select vertex $A$ . Initialize the set of visited vertices inside the MST as $T = \{A\}$ . The set of non-visited vertices is $\{B, C, D, E\}$ . Track the minimum weight to connect each unvisited vertex to the tree:

$B$ : weight 1 (via $A$ )

$D$ : weight 4 (via $A$ )

$C, E$ : $\infty$ (no direct edge from $A$ ).
2
Step 2
Examine the active cut edges crossing from $T$ to the unvisited set: $(A, B)$ with weight 1 and $(A, D)$ with weight 4. The minimum is $(A, B)$ . Add $(A, B)$ to the MST. Update $T = \{A, B\}$ .

Update connection weights for unvisited vertices adjacent to $B$ :

$D$ : updated from 4 to 2 (via $B$ , which is cheaper)

$C$ : updated from $\infty$ to 3 (via $B$ )

$E$ : remains $\infty$ .
3
Step 3
Examine the active cut edges crossing from $T = \{A, B\}$ to the unvisited set: $(A, D)$ with weight 4, $(B, D)$ with weight 2, and $(B, C)$ with weight 3. The minimum is $(B, D)$ with weight 2. Add $(B, D)$ to the MST. Update $T = \{A, B, D\}$ .

Update connection weights for unvisited vertices adjacent to $D$ :

$E$ : updated from $\infty$ to 2 (via $D$ )

$C$ : remains 3.
4
Step 4
Examine the active cut edges crossing from $T = \{A, B, D\}$ to the unvisited set: $(B, C)$ with weight 3, $(D, E)$ with weight 2. The minimum is $(D, E)$ with weight 2. Add $(D, E)$ to the MST. Update $T = \{A, B, D, E\}$ .

Update connection weights for unvisited vertices adjacent to $E$ :

$C$ : remains 3 (since edge $(C, E)$ has weight 5, which is worse than the existing weight of 3 from $B$ ).
5
Step 5
Examine the active cut edges crossing from $T = \{A, B, D, E\}$ to the unvisited set $\{C\}$ : $(B, C)$ with weight 3, $(E, C)$ with weight 5. The minimum is $(B, C)$ with weight 3. Add $(B, C)$ to the MST. Update $T = \{A, B, C, D, E\}$ .

All vertices are now included in the tree. The algorithm terminates with a final MST weight of 1 + 2 + 2 + 3 = 8.

Choosing the Right Tool: Prim's vs. Kruskal's

Use Prim's Algorithm (with an adjacency matrix implementation) for dense graphs where $E \approx V^2$ because it avoids sorting all edges. Use Kruskal's Algorithm for sparse graphs where $E \approx V$ because sorting the small number of edges is highly efficient and DSU operations are extremely fast 2.

Introduction to Algorithms (Wikipedia) - Comprehensive overview of Minimum Spanning Trees, mathematical properties, and basic algorithms. ↩
Kruskal's Algorithm (Wikipedia) - Detailed explanation of Kruskal's greedy approach, cycle detection, and Disjoint-Set Union complexity. ↩

1class DSU:
2    def __init__(self, n):
3        self.parent = list(range(n))
4        self.rank = [0] * n
5
6    def find(self, i):
7        if self.parent[i] == i:
8            return i
9        self.parent[i] = self.find(self.parent[i])  # Path compression
10        return self.parent[i]
11
12    def union(self, i, j):
13        root_i = self.find(i)
14        root_j = self.find(j)
15        if root_i != root_j:
16            if self.rank[root_i] < self.rank[root_j]:
17                self.parent[root_i] = root_j
18            elif self.rank[root_i] > self.rank[root_j]:
19                self.parent[root_j] = root_i
20            else:
21                self.parent[root_j] = root_i
22                self.rank[root_i] += 1
23            return True
24        return False
25
26def kruskal(n, edges):
27    # edges: list of tuples (weight, u, v)
28    edges.sort()
29    dsu = DSU(n)
30    mst = []
31    mst_weight = 0
32    for weight, u, v in edges:
33        if dsu.union(u, v):
34            mst.append((u, v, weight))
35            mst_weight += weight
36            if len(mst) == n - 1:
37                break
38    return mst, mst_weight

Algorithm Performance Comparison (Estimated Operations)

Comparison of theoretical operations for Sparse (E = 2V) vs Dense (E = V^2/2) graphs with V = 100

Historical Evolution of MST Algorithms

Borůvka's Algorithm

1926

Otakar Borůvka designed the first known MST algorithm to find an efficient electrical coverage grid for Moravia . It remains highly parallelizable."

Introduction to Algorithms (Wikipedia) - Comprehensive overview of Minimum Spanning Trees, mathematical properties, and basic algorithms. ↩

Jarník's Discovery

1930

Vojtěch Jarník independently discovered what is now known as Prim's algorithm, focusing on the node-centric growing approach ."

Prim's Algorithm (Wikipedia) - In-depth look at Prim's node-growing strategy, priority queue optimization, and complexity. ↩

Kruskal's Algorithm

1956

Joseph Kruskal published his edge-centric greedy algorithm, utilizing sorting and disjoint sets to find the minimum spanning forest ."

Kruskal's Algorithm (Wikipedia) - Detailed explanation of Kruskal's greedy approach, cycle detection, and Disjoint-Set Union complexity. ↩

Prim's Rediscovery

1957

Robert C. Prim independently rediscovered and popularized Jarník's algorithm, establishing its mathematical properties in computer networks ."

Prim's Algorithm (Wikipedia) - In-depth look at Prim's node-growing strategy, priority queue optimization, and complexity. ↩

Frequently Asked Questions & Edge Cases

Knowledge Check

Question 1 of 3

Q1Single choice

Which data structure is most critical for optimizing the cycle-detection step in Kruskal's algorithm?

Fibonacci Heap

Disjoint-Set Union (DSU)

Red-Black Tree

Adjacency Matrix

Explore Related Topics

Algorithms

Algorithms are finite, well-defined procedures that transform inputs into outputs, requiring correctness, efficiency, and formal properties such as definiteness and finiteness.

Valid algorithms must be definite, finite, have clear input/output, and be effective; correctness and efficiency are essential.
Analyzing an algorithm involves problem specification, pseudocode, correctness proof, and measuring time ( $O(\cdot)$ , $\Theta(\cdot)$ , $\Omega(\cdot)$ ) and space complexity.
Common growth rates range from $O(1)$ to $O(2^n)$ , with divide‑and‑conquer recurrences like $T(n)=aT(n/b)+f(n)$ .
Key design paradigms include divide‑and‑conquer, dynamic programming, greedy, backtracking, and branch‑and‑bound.
Choosing an algorithm depends on input characteristics, worst‑case vs. average performance, memory limits, stability, and preprocessing needs.

Graph Traversals: Breadth-First Search (BFS) vs. Depth-First Search (DFS)

This content contrasts Breadth‑First Search (BFS) and Depth‑First Search (DFS), outlining their traversal order, complexity, and typical use cases.

BFS uses a FIFO queue, visits nodes level by level (A→B→C→D→E→F); DFS uses a LIFO stack, dives deep (A→B→D→E→C→F).
Both run in $O(V+E)$ time; BFS may need $O(V)$ (or $O(b^d)$ ) space, while DFS typically uses $O(d)$ stack depth.
BFS guarantees the shortest path in unweighted graphs, suited for routing, web crawling, and level‑order serialization.
DFS excels in memory‑limited, wide graphs and in tasks like topological sort and cycle detection, but deep recursion can cause stack overflow.

The Minimum Number of Colors for a Graph with $n>3$ Vertices and 2 Edges

A graph with more than three vertices that contains exactly two edges always has chromatic number  $2$ .

Because an edge exists, at least two colors are required: $\chi(G)\ge 2$ .
With only two edges the graph is bipartite (either two disjoint $K_2$ or a $P_3$ plus isolated vertices), so two colors are sufficient: $\chi(G)\le 2$ .
No triangle $K_3$ or odd cycle can appear, eliminating the need for three or more colors.
Isolated vertices are adjacent to none and can reuse any existing color, leaving the chromatic number unchanged.
Consequently $\chi(G)=2$ , making option (i) the correct answer.

Browse all research articles

Minimum Spanning Trees: Step-by-Step Algorithms and Optimization

Visualizing a Graph and its MST

Footnotes

Greedy Algorithms: Prim's and Kruskal's Algorithms

Kruskal's Algorithm

Footnotes

Kruskal's Algorithm Step-by-Step Walkthrough

Handling Disconnected Graphs

Footnotes

Prim's Algorithm

Footnotes

Prim's Algorithm Step-by-Step Walkthrough

Choosing the Right Tool: Prim's vs. Kruskal's

Footnotes

Algorithm Performance Comparison (Estimated Operations)

Historical Evolution of MST Algorithms

Borůvka's Algorithm

Footnotes

Jarník's Discovery

Footnotes

Kruskal's Algorithm

Footnotes

Prim's Rediscovery

Footnotes

Frequently Asked Questions & Edge Cases

Knowledge Check

Explore Related Topics