--- title: "Minimum Spanning Tree" description: "Prim & Kruskal compared" source: https://vizlearn.app/algorithms/graph/minimum-spanning-tree access: premium (interactive player requires Lifetime; this doc is free) --- # Minimum Spanning Tree A minimum spanning tree (MST) connects every vertex in an undirected, weighted graph with the smallest possible total edge weight. It contains no cycles and, for a graph with `V` vertices, uses exactly `V - 1` edges. That goal is easy to confuse with shortest paths. A shortest-path algorithm asks how cheaply one source can reach each destination. An MST asks for one cheap network that connects everyone. The route between two vertices inside the finished tree does not have to be their shortest route in the original graph. This lesson puts two classic greedy algorithms on the same graph: - **Prim** grows one connected tree. Its next choice must cross the cut between the vertices already in the tree and those still outside. - **Kruskal** starts with one component per vertex. It scans edges from lightest to heaviest and accepts an edge only when it joins two different components. They organize the work differently, but both rely on the same safety idea: take the lightest edge that can make useful progress without creating a cycle. ## How the algorithms work Prim keeps a set `S` of vertices already reached by the tree and a min-heap of frontier edges. A frontier edge has one endpoint in `S` and one outside it. Pop the lightest edge. If its outside endpoint is still outside, accept the edge and add that endpoint to `S`. If both endpoints have entered the tree since the edge was queued, the entry is stale and must be rejected. The left ledger in the animation draws the current cut directly: `S` on one side, `V - S` on the other. The cut property says that a lightest edge crossing a cut is safe for some MST. Prim applies that property again after every new vertex joins `S`. Kruskal sorts all edges once. It then needs a quick answer to one question: are the two endpoints already connected by accepted edges? A disjoint-set structure supplies that answer. Different roots mean the edge joins two components, so Kruskal accepts it and unions the roots. Equal roots mean an accepted path already connects the endpoints, so another edge would close a cycle. Neither algorithm needs nonnegative weights. A negative edge is simply very attractive, provided accepting it is safe. This differs from Dijkstra's algorithm, whose finalized-distance argument does require nonnegative weights. ## Step by Step The default **Bridge** graph has vertices A through F and these undirected edges: `B–C (1)`, `B–D (2)`, `C–D (3)`, `C–E (4)`, `D–F (5)`, `D–E (6)`, `A–C (7)`, `A–B (8)`, `E–F (9)`. Prim starts at A. 1. Put A in `S`. Expose `A–C (7)` and `A–B (8)`. 2. Pop `A–C (7)`. It crosses from A in `S` to C outside, so accept it. Total: **7**. Expose `C–B (1)`, `C–D (3)`, and `C–E (4)`. 3. Pop `C–B (1)`. Accept it and add B to `S`. Total: **8**. Expose `B–D (2)`. 4. Pop `B–D (2)`. Accept it and add D. Total: **10**. Expose `D–F (5)` and `D–E (6)`. 5. Pop `C–D (3)`. C and D are already connected through `C–B` and `B–D`. Rejecting `C–D` keeps the tree acyclic. 6. Pop `C–E (4)`. Accept it and add E. Total: **14**. Expose `E–F (9)`. 7. Pop `D–F (5)`. Accept it and add F. Total: **19**. 8. The tree now has `6 - 1 = 5` edges, so Prim stops. The remaining frontier entries cannot improve a spanning tree that is already complete. The accepted edge set is `A–C`, `B–C`, `B–D`, `C–E`, and `D–F`, with total weight **19**. Switch to Kruskal and the same answer appears in a different order. It accepts `B–C (1)` and `B–D (2)`, rejects `C–D (3)` because B, C, and D already share a component, then accepts `C–E (4)` and `D–F (5)`. `D–E (6)` is another cycle, so it is rejected. Finally `A–C (7)` joins A to the large component and completes the five-edge tree at weight **19**. The order of accepted edges differs because Prim is constrained by one growing cut while Kruskal can work anywhere in the graph. The finished MST is the same here because every edge weight is distinct. ## Complexity With adjacency lists and a binary min-heap, Prim runs in `O((V + E) log V)` time on the simple graphs this lesson uses, and the stored graph plus heap uses `O(V + E)` space. The lazy frontier heap can hold `O(E)` entries, so each heap operation is strictly `O(log E)`; on a simple graph `E < V²`, so that is also `O(log V)`. Kruskal spends `O(E log E)` time sorting the edges. Its disjoint-set operations add `O(E α(V))`, which is effectively linear for practical input sizes. The edge list and disjoint-set arrays use `O(V + E)` space. For a dense graph represented by an adjacency matrix, a simple `O(V²)` Prim implementation can be a sensible choice. For sparse graphs already stored as edge lists, Kruskal is often the most direct. ## Edge Cases - **One vertex.** The empty edge set is already a spanning tree, with total weight 0. - **Disconnected graph.** No spanning tree exists. Prim empties its frontier before reaching every vertex; Kruskal exhausts the edge list with multiple components left. The Disconnected preset reports this instead of presenting a partial forest as an MST. - **Equal weights.** Several different MSTs may have the same minimum total. This lesson keeps input order for equal-weight edges so replay remains deterministic; another valid tie order may produce a different but equally good tree. - **Negative weights.** They are valid. The Negative edge preset accepts the weight `-3` edge and finishes with total 3. - **Parallel edges.** Treat them as separate candidates. A heavier parallel edge becomes a cycle after the lighter one connects the same endpoints. - **Self-loops.** They can never help connect two components and should be ignored. ## Common Mistakes 1. **Choosing the globally lightest remaining edge in Prim.** Prim may choose only from the current cut. A cheap edge between two outside vertices does not grow its tree yet. 2. **Checking only whether an endpoint has appeared before.** Kruskal rejects an edge only when both endpoints already have the same disjoint-set root. A familiar endpoint can still connect two different components. 3. **Stopping after every vertex appears in some accepted edge.** The reliable stopping rule is exactly `V - 1` accepted edges in a connected graph. 4. **Treating the graph as directed.** MSTs are defined for undirected graphs. A directed analogue is a different problem, usually called a minimum arborescence. 5. **Assuming negative weights invalidate the algorithm.** That restriction belongs to Dijkstra, not to Prim or Kruskal. 6. **Returning a partial forest for a disconnected graph.** A minimum spanning forest can be useful, but it is not a spanning tree. Name and report the result honestly. ## A note on the animation Prim's frontier is drawn as a fully sorted row so the next minimum is readable. A real binary heap is only partially ordered: it guarantees access to the minimum without keeping every item in sorted left-to-right order. Kruskal's row really is sorted, because sorting the full edge list is part of that algorithm. The code panel shows the core algorithms and assumes the graph representation, binary heap, and disjoint-set implementation already exist. The animation expands heap insertions and component merges into separate teaching beats so each state change can be inspected.