Minimum Spanning Trees: Concept, Prim’s vs Kruskal’s, and Complexity Analysis

A Minimum Spanning Tree (MST) is a fundamental structure in graph theory for a connected, weighted, undirected graph.2 A spanning tree includes all vertices of the graph, remains connected, and contains no cycles; therefore, for a graph with $V$ vertices, every spanning tree has exactly $V-1$ edges.2

The MST is the spanning tree whose total edge-weight sum is as small as possible.2 Intuitively, it gives the cheapest way to connect all vertices without redundancy. This makes MSTs central to problems such as network design, circuit layout, clustering, and infrastructure planning, where one seeks global connectivity with minimum cost.2

Two classical greedy algorithm methods for computing an MST are Prim’s algorithm and Kruskal’s algorithm.2 Both are correct, but they operate differently and have different performance profiles depending on graph representation and density.3

A useful structural view is:

If a graph is not connected, an MST does not exist for the whole graph; instead, one computes a minimum spanning forest.2

Footnotes

1. Minimum spanning trees - Academic overview defining trees, spanning trees, and MSTs in connected weighted graphs. ↩ ↩² ↩³

2. Minimum Spanning Trees - Princeton Algorithms text describing spanning-tree conditions, connectivity, and MST structure. ↩ ↩² ↩³

3. Minimum Spanning Trees - Princeton source discussing MST properties, cut-based reasoning, and Kruskal’s complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵

4. Prim's algorithm - Reference summary of Prim’s method and implementation-dependent complexities. ↩ ↩² ↩³

5. Investigating the time efficiencies of Prim's and Kruskal's algorithms - Research discussion on graph density and the practical comparison between Prim’s and Kruskal’s algorithms. ↩

(i) Concept of a Minimum Spanning Tree

To explain the concept precisely, begin with the notion of a tree. A tree is a connected graph with no cycles. A spanning tree of a connected graph $G=(V,E)$ is a subgraph that contains every vertex of $G$ and is itself a tree.2 Since many distinct spanning trees may exist, the MST selects the one with minimum total edge weight:

$$\text{MST}(G)=\arg\min_{T \subseteq E}\sum_{e \in T} w(e)$$

subject to:

1. $T$ spans all vertices,
2. $T$ is connected,
3. $T$ is acyclic.2

Important technical properties follow from this definition:

• An MST minimizes the sum of selected edge weights, not necessarily the length of every individual path between vertices.
• Edge weights may be arbitrary real values, including zero or negative values; the MST definition still applies as long as the graph is connected and undirected.
• An MST need not be unique: if multiple edges have equal weights, different spanning trees may share the same minimum total cost.

A conceptual example is shown below.

The correctness of MST algorithms is typically justified using cut and cycle ideas: the lightest edge crossing a valid cut is safe to include, while a heavier edge on a cycle can be excluded without losing optimality.2

For the graph above, one MST is $\{AB, BC, CD\}$ with total weight $1+2+3=6$, because it connects all four vertices without cycles and with minimum achievable cost.

Footnotes

1. Minimum spanning trees - Academic overview defining trees, spanning trees, and MSTs in connected weighted graphs. ↩ ↩² ↩³

2. Minimum Spanning Trees - Princeton source discussing MST properties, cut-based reasoning, and Kruskal’s complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. Prim's algorithm - Reference summary of Prim’s method and implementation-dependent complexities. ↩

(ii) Prim’s and Kruskal’s Algorithms: Comparison and Contrast

Although both are greedy methods for the same optimization problem, they build the MST in different ways.2

Prim’s Algorithm

Prim’s algorithm starts from an arbitrary vertex and grows a single tree outward. At each step, it selects the minimum-weight edge that connects a vertex already in the current tree to a vertex outside it.2 Thus, Prim’s maintains one connected partial solution throughout execution.

Key characteristics of Prim’s approach:

• Vertex-centered growth from one start point.
• Maintains one evolving tree, never a forest.
• Naturally implemented using an adjacency list plus a priority queue, or an adjacency matrix for dense graphs.2

Kruskal’s Algorithm

Kruskal’s algorithm instead sorts all edges globally in nondecreasing order of weight and repeatedly adds the next lightest edge that does not create a cycle.2 Initially, every vertex is its own component, so the algorithm starts with a forest and merges components over time until one spanning tree remains.2

Key characteristics of Kruskal’s approach:

• Edge-centered global ordering.2
• Builds a forest first, then merges it.2
• Uses a disjoint-set union / Union-Find structure to detect whether an edge connects different components.

The essential contrast is therefore growth strategy:

• Prim: expand one tree from inside to outside.
• Kruskal: connect many small trees from outside toward a final whole.3

Footnotes

1. Prim's algorithm - Reference summary of Prim’s method and implementation-dependent complexities. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

2. Minimum Spanning Trees - Princeton source discussing MST properties, cut-based reasoning, and Kruskal’s complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. Chapter 20 - Minimum Spanning Trees - Notes summarizing Prim’s matrix, binary heap, and Fibonacci heap implementations and when each is suitable. ↩ ↩²

4. DSA Kruskal's Algorithm - Explanation of Kruskal’s algorithm, edge sorting, Union-Find, and sparse-graph suitability. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

Detailed Comparison Table

A practical distinction is that Prim’s algorithm makes local frontier decisions, whereas Kruskal’s makes global edge-order decisions.2

Footnotes

1. Prim's algorithm - Reference summary of Prim’s method and implementation-dependent complexities. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

2. Minimum Spanning Trees - Princeton source discussing MST properties, cut-based reasoning, and Kruskal’s complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. DSA Kruskal's Algorithm - Explanation of Kruskal’s algorithm, edge sorting, Union-Find, and sparse-graph suitability. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

4. Chapter 20 - Minimum Spanning Trees - Notes summarizing Prim’s matrix, binary heap, and Fibonacci heap implementations and when each is suitable. ↩ ↩²

(iii) Time Complexity Analysis and When Each Algorithm Is Preferred

The running time of both algorithms depends strongly on the underlying data structures.3

Prim’s Algorithm Complexity

A straightforward adjacency-matrix implementation of Prim’s algorithm runs in:

$$O(V^2)$$

because the algorithm repeatedly scans candidate vertices or edges across the matrix to find the next minimum connection.2

With an adjacency list and a binary heap priority queue, Prim’s algorithm runs in:

$$O((V+E)\log V) = O(E\log V)$$

since there are up to $V$ extract-min operations and up to $E$ key decreases or updates.3

With a Fibonacci heap, Prim’s can be improved to:

$$O(E + V\log V)$$

which is asymptotically better than the binary-heap version in some settings, especially when decrease-key is frequent.2

Kruskal’s Algorithm Complexity

Kruskal’s algorithm first sorts the edges, which costs:

$$O(E\log E)$$

Then it processes each edge with near-constant or very small amortized Union-Find operations, so sorting dominates overall runtime in standard implementations.2 Since in simple undirected graphs $E \leq V^2$, one often writes:

$$O(E\log E) = O(E\log V)$$

up to asymptotic equivalence.

Comparative Interpretation

For dense graphs, where $E$ is close to $V^2$, the $O(V^2)$ matrix version of Prim’s can be especially attractive because it avoids explicit edge sorting and matches dense storage well.2 For sparse graphs, where $E$ is closer to $V$, Kruskal’s $O(E\log E)$ behavior is often very efficient and straightforward, especially when the graph is already available as an edge list.2

A nuanced point is that heap-based Prim’s and Kruskal’s have similar asymptotic performance on sparse graphs, but their practical constant factors and input representation differ.2 Prim’s may be preferable when:

• the graph is dense,2
• adjacency access is natural or already available,
• one wants to expand from a chosen starting vertex.

Kruskal’s may be preferable when:

• the graph is sparse,2
• edges are already collected as a list,
• a Union-Find implementation is convenient and simple.

One compact decision rule is:

• Use Prim’s for dense graphs and adjacency-based representations.
• Use Kruskal’s for sparse graphs and edge-list-based workflows.4

Footnotes

1. Prim's algorithm - Reference summary of Prim’s method and implementation-dependent complexities. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹

2. Chapter 20 - Minimum Spanning Trees - Notes summarizing Prim’s matrix, binary heap, and Fibonacci heap implementations and when each is suitable. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

3. DSA Kruskal's Algorithm - Explanation of Kruskal’s algorithm, edge sorting, Union-Find, and sparse-graph suitability. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

4. Intro to Algorithms: Chapter 24 - Minimum Spanning Trees - CLRS-based analysis of Prim’s algorithm using binary heaps and adjacency structures. ↩ ↩² ↩³

5. Minimum Spanning Trees - Princeton source discussing MST properties, cut-based reasoning, and Kruskal’s complexity. ↩ ↩² ↩³ ↩⁴

Synthesis

The MST is the minimum-cost acyclic structure that connects all vertices in a connected weighted undirected graph.2 Prim’s and Kruskal’s algorithms both exploit greedy-choice principles, but Prim’s grows a single connected tree, whereas Kruskal’s assembles the MST by safely merging components using globally sorted edges.3

From an algorithm-engineering perspective, the most important comparison is not merely the textbook procedure but the interaction between:

• graph density,
• graph representation,
• data-structure choice,
• and implementation overhead.4

Thus, the “better” algorithm is context-dependent rather than absolute.

Footnotes

1. Minimum spanning trees - Academic overview defining trees, spanning trees, and MSTs in connected weighted graphs. ↩

2. Minimum Spanning Trees - Princeton source discussing MST properties, cut-based reasoning, and Kruskal’s complexity. ↩ ↩²

3. Prim's algorithm - Reference summary of Prim’s method and implementation-dependent complexities. ↩ ↩²

4. DSA Kruskal's Algorithm - Explanation of Kruskal’s algorithm, edge sorting, Union-Find, and sparse-graph suitability. ↩ ↩²

5. Chapter 20 - Minimum Spanning Trees - Notes summarizing Prim’s matrix, binary heap, and Fibonacci heap implementations and when each is suitable. ↩

6. Intro to Algorithms: Chapter 24 - Minimum Spanning Trees - CLRS-based analysis of Prim’s algorithm using binary heaps and adjacency structures. ↩