5.2 Minimum spanning trees: Prim and Kruskal

Motivation

Suppose several locations must be connected by cables. Paying separately for a short route from one chosen location to every other location is not necessarily the right objective. If the requirement is only that every location can reach every other location, shared links may reduce the total construction cost. This is the minimum-spanning-tree problem.

The distinction between local and global cost is the central difficulty. A cheap edge may be useful, but adding every cheap edge can create a cycle. A cycle contains redundancy: removing one edge from it leaves its vertices connected. Prim's and Kruskal's algorithms are greedy, yet they do not merely say “take the cheapest edge.” Each algorithm specifies which edges are currently eligible and rejects edges that would destroy the tree structure.

Throughout this note, let G=(V,E) be a finite, nonempty, connected, undirected graph with a real weight w(e) on each edge. Connectivity is essential: a disconnected graph has no tree spanning all vertices. The weights need not be distinct and need not be nonnegative. Equal weights can produce several different MSTs with the same minimum total weight.

Definitions

Definition

Tree and spanning tree

A tree is a connected undirected graph with no cycle. A spanning tree of G=(V,E) is a subgraph T=(V,E_T) that uses every vertex of G and is a tree. Thus E_T is a subset of E, but the vertex set is unchanged.

For a one-vertex graph, the empty edge set is its spanning tree. If G is disconnected, no spanning tree exists; one can instead discuss a spanning forest, with one tree for each connected component.

Definition

Minimum spanning tree

The weight of a spanning tree T is

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

A minimum spanning tree (MST) is a spanning tree whose total weight is no larger than that of any other spanning tree of G. “Minimum” refers to the sum of the selected edge weights, not to the number of edges: every spanning tree already has the same number of edges.

Definition

Cut, crossing edge, and safe edge

A cut partitions V into two nonempty sets S and V\setminus S. An edge crosses the cut if one endpoint is in S and the other is outside S. A cut respects a currently chosen forest F if no edge of F crosses it.

An edge is safe for F if adding it keeps open the possibility that the chosen edges are contained in some MST. Safety is stronger than merely “does not make a cycle”: it connects cycle avoidance to global optimality.

An MST is also different from a shortest-path tree. After choosing a source s, a shortest-path tree preserves a shortest route from s to every reachable vertex. An MST has no distinguished source and minimizes the sum of tree edges. Consequently, paths inside an MST need not be shortest paths in the original graph.

Theorem / proposition

Theorem

Edge count of a tree

Every tree with vertex set V has exactly |V|-1 edges. Therefore a spanning tree is complete as soon as it is connected, acyclic, and has |V|-1 selected edges. Conversely, a connected undirected graph with |V|-1 edges is a tree.

This fact gives both algorithms a precise stopping condition. Before |V|-1 accepted edges, the construction is still a forest. Accepting more than |V|-1 edges would force a cycle.

Theorem

Light crossing-edge safety principle

Let F be a forest contained in some MST, and let a cut respect F. If e is a minimum-weight edge among all edges crossing that cut, then e is safe for F: there is an MST containing F together with e.

Prim applies the principle to the cut between the vertices already in its one growing tree and all remaining vertices. Kruskal applies it to a cut around one component of its current forest. This is why their different eligibility rules lead to the same kind of optimum.

Proof sketch or proof idea

For the edge-count statement, use induction on the number of vertices. A one-vertex tree has zero edges. Every finite tree with at least two vertices has a leaf. Remove a leaf and its unique incident edge. The remaining graph is still a tree, now on one fewer vertex, so by induction it has |V|-2 edges. Restoring the removed edge gives |V|-1.

For the safe-edge principle, assume an MST M contains F. If M already contains e, nothing must be changed. Otherwise add e to M. Because M is a tree, this creates exactly one cycle. The cycle enters and leaves the two sides of the cut, so it contains another crossing edge f. The cut respects F, hence f is not an edge of F. Since e is a lightest crossing edge, w(e) ≤ w(f). Replace f by e. The result is again a spanning tree, it still contains F, and its weight did not increase. Because M was already minimum, the replacement is also an MST. This exchange argument proves that the greedy choice can be extended to an optimum.

For Prim, every accepted edge has exactly one endpoint in the current tree, so it crosses the relevant cut and cannot create a cycle. For Kruskal, consider a candidate (u,v) whose endpoints lie in different forest components. The cut around u's component respects the forest. Processing edges in nondecreasing weight order makes the candidate a lightest still-relevant crossing edge, so the exchange argument applies.

Worked examples

Worked example

MST is not a shortest-path tree

Consider the triangle with edges s-a of weight 2, s-b of weight 2, and a-b of weight 1. An MST chooses a-b and either s-a or s-b, for total weight 3.

If the source is s, however, a shortest-path tree must use both weight-2 edges. The direct distances to a and b are both 2, whereas going through the other non-source vertex costs 3. That shortest-path tree has edge-weight sum 4. It solves the source-distance objective, while the MST solves the total-connection objective.

Prim's algorithm

Prim maintains a set S of vertices already in the tree. It repeatedly accepts the cheapest edge with exactly one endpoint in S. The Tutorial 9 presentation uses an edge priority queue, so the following version matches that model:

PRIM_WITH_EDGE_QUEUE(G, start):
    inTree[v] ← false for every vertex v
    T ← empty edge set
    pq ← empty min-priority queue of (weight, from, to)

    inTree[start] ← true
    push every edge (start, x) with x not inTree into pq

    while pq is not empty and |T| ≠ |V| - 1:
        (weight, u, v) ← pq.popMin()
        if inTree[v]:
            continue                 // stale edge; both endpoints are in S
        add (u, v) to T
        inTree[v] ← true
        for each edge (v, x):
            if not inTree[x]:
                pq.push(weight(v,x), v, x)

    if |T| != |V| - 1: report "disconnected"
    otherwise return T

Worked example

Complete Prim trace from Tutorial 9

The tutorial graph has vertices A,B,C,D,E and weighted edges

AB=1, BD=2, BC=3, AD=5, DE=6, DC=7, CE=8.

Start at A. The states below show the accepted tree edges and the useful priority-queue information.

Step	Current vertices S	Queue action and decision	Accepted edges
0	{A}	insert AB(1), AD(5)	none
1	{A,B}	pop AB(1); insert BD(2), BC(3)	AB
2	{A,B,D}	pop BD(2); insert DE(6), DC(7)	AB, BD
3	{A,B,C,D}	pop BC(3); insert CE(8)	AB, BD, BC
4a	unchanged	pop AD(5) and reject it: both endpoints are already in S	unchanged
4b	all five vertices	pop DE(6) and accept it	AB, BD, BC, DE

The selected tree has four edges, as required for five vertices, and total weight 1+2+3+6=12. The rejection of AD is not optional housekeeping. It is the cycle-avoidance step for an edge-priority-queue implementation: accepting AD would close the cycle A-B-D-A.

With an adjacency list, each edge is inspected when one endpoint joins the tree and at most O(E) queue entries are pushed and popped. A binary heap with up to O(E) entries therefore gives O(E log E) time and O(V+E) space. For a simple graph, log E=O(log V), so the same bound is often written O(E log V). This analysis belongs specifically to the edge-queue version above; an adjacency-matrix implementation that repeatedly scans all vertices instead has O(V^2) time.

Kruskal's algorithm

Kruskal does not grow from a start vertex. It begins with every vertex as a separate component, sorts all edges by nondecreasing weight, and accepts an edge exactly when its endpoints are currently in different components.

The course-level implementation below checks that condition by searching the current forest. It deliberately assumes no additional component data structure.

KRUSKAL_WITH_FOREST_SEARCH(G):
    edges ← all edges sorted by nondecreasing weight
    F ← graph with all vertices and no edges
    if F already has |V| - 1 edges:
        return F                    // handles the one-vertex graph

    for each (u, v) in edges:
        if HAS_PATH_BY_DFS_OR_BFS(F, u, v):
            continue                 // adding (u,v) would form a cycle
        add (u, v) to F
        if F has |V| - 1 edges:
            return F

    report "disconnected"

Worked example

Complete Kruskal trace on the same source graph

The sorted order is

AB(1), BD(2), BC(3), AD(5), DE(6), DC(7), CE(8).

Edge considered	Endpoint state before decision	Decision	Forest after decision
AB(1)	A and B separate	accept	{AB}
BD(2)	B and D separate	accept	{AB,BD}
BC(3)	B and C separate	accept	{AB,BD,BC}
AD(5)	path A-B-D already exists	reject: it would form A-B-D-A	unchanged
DE(6)	E is separate from the other component	accept and stop	{AB,BD,BC,DE}

Again the total is 12. Edges DC(7) and CE(8) need not be processed once four edges have been accepted. Prim and Kruskal happen to return the same tree here because the edge weights impose an unambiguous sequence of useful choices; with ties, they may return different MSTs of equal weight.

Sorting costs O(E log E). In the implementation just described, the accepted edges always form a forest and therefore number fewer than V. A DFS or BFS in that forest costs O(V) in the worst case, and it may be performed for each of the E candidates. The resulting bound is O(E log E + EV) time and O(V+E) space, including the sorted edge list and forest. Quoting only O(E log E) would not match this implementation because it would ignore the explicit traversal-based cycle tests.

Common mistakes

Common mistake

Taking the globally cheapest remaining edge in Prim

Prim may choose only an edge crossing from its current tree to an outside vertex. A cheap edge joining two outside vertices does not extend the tree; an edge joining two inside vertices is stale and would create a cycle.

Common mistake

Stopping when every vertex has appeared in some Kruskal edge

Several disconnected components can collectively mention every vertex. Stop only after |V|-1 edges have been accepted; for a connected input, the forest is then one spanning tree.

Common mistake

Confusing MST paths with shortest paths

An MST minimizes one global sum. It does not promise that the path between a chosen pair, or from a chosen source, is cheapest in the original graph.

Common mistake

Assuming nonnegative weights are required

That restriction belongs to Dijkstra's greedy finalization argument, not to MST construction. Prim and Kruskal remain valid with negative edge weights; the cut/exchange reasoning compares weights but never assumes they are nonnegative.

Summary

• A spanning tree exists exactly when the undirected graph is connected, and it contains all vertices with exactly |V|-1 edges.
• An MST minimizes total selected-edge weight; it is not a shortest-path tree.
• Prim grows one connected tree by the lightest edge crossing its current cut.
• Kruskal grows a forest by considering edges in sorted order and rejecting an edge whenever its endpoints are already connected.
• The light crossing-edge exchange argument explains why both greedy choices are safe, while explicit cycle checks preserve the tree structure.
• Complexity must name the representation and data structures: the described Prim edge queue costs O(E log E), while sorted edges plus traversal-based Kruskal cycle checks cost O(E log E + EV).

Exercises

Checkpoint

Check 1. A connected graph has 9 vertices. How many edges must any spanning tree contain, and why can it contain no more?

Use both parts of the word “tree”: connected and acyclic.

Checkpoint

Check 2. In the Tutorial 9 graph, Prim has already accepted AB, BD, and BC. Which queued edge is examined next, what happens to it, and which edge is then accepted?

Inspect whether each endpoint is already in the current tree.

Checkpoint

Check 3. Why is O(E log E) alone not a valid complete bound for the traversal-based Kruskal implementation in this note?

Account for every HAS_PATH operation, not only sorting.

1. In the Tutorial 9 graph, remove edge BD(2) and run Kruskal on the remaining six edges. Record every acceptance or rejection and the final total weight.
2. Prove the cycle criterion used by Kruskal: adding (u,v) to a forest makes a cycle if and only if the forest already contains a path from u to v.
3. Construct a connected weighted graph with two different MSTs. Identify the weight tie that permits the two answers.
4. Explain why Prim reports failure on a disconnected graph even if its priority queue implementation is otherwise correct.

Solutions

Solution · Solution to Check 1

It contains 9-1=8 edges. A connected graph on nine vertices needs at least eight edges. A tree reaches that lower bound; adding any ninth edge to the tree would connect two vertices that already have a unique tree path and therefore create a cycle.

Solution · Solution to Check 2

The queue next exposes AD(5). Both A and D are already in the tree, so the entry is stale and is rejected; otherwise it would create A-B-D-A. Prim then accepts DE(6), bringing E into the tree and completing the four-edge MST.

Solution · Solution to Check 3

Sorting is O(E log E), but each candidate can trigger a DFS or BFS in a forest containing V vertices and fewer than V edges. That search costs O(V) and may occur E times, adding O(EV). The matched bound is therefore O(E log E + EV).

Solution · Guided solutions to the longer exercises

1. The new sorted order is AB(1), BC(3), AD(5), DE(6), DC(7), CE(8). Accept AB, accept BC, accept AD, and accept DE; four accepted edges already span all five vertices. The total is 1+3+5+6=15. No rejection is encountered before the stopping point.
2. If a path from u to v already exists, that path plus (u,v) is a cycle. Conversely, if adding (u,v) creates a cycle, delete the new edge from that cycle; what remains is an old path from u to v. Thus the conditions are equivalent.
3. A triangle whose three edges all have weight 1 works. Any two edges form a spanning tree of total 2, so there are three MSTs. The equal weights mean the safe light edge need not be unique.
4. Prim reaches only the component containing its start vertex. Eventually the queue becomes empty while fewer than |V|-1 edges have been accepted. No edge crosses from the reached component to the remaining vertices, which is exactly the certificate that no spanning tree of the whole graph exists.