Minimum Spanning Trees — Kruskal and Prim
Connect every vertex in a weighted graph at minimum total cost using Kruskal and Prim.
Objectives: connect all vertices as cheaply as possible
A spanning tree reaches every vertex, has no cycles, and contains exactly V−1 edges. A minimum spanning tree has the smallest possible sum of edge weights among all spanning trees. An application might choose low-cost links between locations, but real network design must also account for capacity, reliability, and constraints beyond this model. Edge weights may be negative; the graph still needs to be undirected and connected for a spanning tree over all vertices to exist.
1. Greedy choice with a correctness argument
Both algorithms use a safe-edge principle: among the edges crossing a cut that separates already-connected work from the rest, a minimum-weight crossing edge can be included in some MST. Kruskal grows a forest by taking the globally lightest edge that connects two components. Prim grows one tree by choosing the lightest edge that leaves the current tree. The choices differ, but each maintains a partial forest that can be extended to an MST.
| Property | Kruskal | Prim |
|---|---|---|
| Growth model | Forest; merge components | One tree; expand its frontier |
| Main data structure | Sorted edges + DSU | Min-priority queue or array of keys |
| Typical sparse-graph cost | O(E log E) | O(E log V) with a binary heap |
| Disconnected graph | Returns a minimum spanning forest | One run covers only one component |
2. Kruskal: sort edges, accept safe connections
Sort all edges by nondecreasing weight. For each edge (u, v), use DSU to check whether u and v are already in the same component. If so, adding it would form a cycle, so skip it. Otherwise accept the edge and merge the components. Stop after selecting V−1 edges for a connected input. Sorting dominates the running time; DSU operations are near constant amortized time.
The comparator avoids subtracting weights, which could overflow. This teaching API sorts the caller’s edge array in place and uses variable-length local arrays for DSU; document those choices or copy edges and allocate storage dynamically in a larger application. Validate every endpoint is in 0…n−1 before indexing. For n = 1, zero selected edges is a valid tree of cost zero.
3. Prim: keep the cheapest edge to the tree
Prim maintains a key for each vertex outside the growing tree: the cheapest edge seen so far that connects it to a vertex already inside. Each step adds the outside vertex with minimum key and relaxes its neighbours. A heap makes this efficient on sparse graphs; a simple O(V²) implementation is easier to inspect for dense graphs or small teaching examples.
Initialize absent edges to INF, not zero: zero-weight edges are valid and must be considered. Because the graph is undirected, the matrix must be symmetric. The first chosen key is zero for the starting vertex; each later key is the edge that attaches that vertex. If a remaining vertex has INF, the graph is disconnected. Negative weights are okay for MSTs because Prim’s choice does not rely on non-negative shortest-path distances.
Both totals are 6 for this example. In a real test, assert not only that the totals agree, but also that the chosen edges connect every vertex without a cycle. Two algorithms returning the same total is a useful cross-check, not a proof by itself.
4. Understand the selected edges, not only the cost
For a connected graph, any valid output has V−1 selected edges and no cycle. If all edge weights are distinct, the MST is unique. With ties, multiple different trees can have the same minimum cost; tests should validate spanning and total cost rather than one exact edge list. If the graph is disconnected, Kruskal can still produce a minimum spanning forest, but there is no spanning tree covering all vertices. Prim must be restarted for each connected component to produce a forest.
5. Common mistakes
- Using shortest-path logic instead of MST logic: an MST minimizes total tree-edge cost, not each vertex’s route distance from a source.
- Accepting every sorted edge in Kruskal: DSU must reject edges whose endpoints already share a component, otherwise a cycle forms.
- Using zero as “no edge”: zero-weight connections are valid. Use a sentinel such as INF that cannot be confused with a real weight.
- Assuming a disconnected graph has an MST: detect that fewer than V−1 edges were selected or that Prim cannot reach every vertex.
6. Practice
- Run Kruskal by hand on a graph with one equal-weight tie. Show why two different selected edge sets can both be minimum.
- Return the chosen edges as well as total cost. Explain how your output changes when the graph is disconnected.
- Implement Prim with an adjacency list and min-heap. Record the complexity and how stale heap entries are handled.
- Compare Kruskal and Prim on a dense graph and a sparse graph. State representation and complexity assumptions.
- Test n = 1, disconnected components, negative weights, zero-weight edges, duplicate edges, and a graph with equal weights.
🎯 Key Takeaways
- ✓An MST connects every vertex without cycles using exactly V−1 edges for a connected graph.
- ✓Kruskal sorts edges and uses DSU to accept only component-joining edges.
- ✓Prim expands one tree by selecting the cheapest edge to an outside vertex.
- ✓Both algorithms rely on safe minimum edges but grow the solution differently.
- ✓Zero and negative edge weights can be valid; missing edges need a separate sentinel.
- ✓The Interview Problem-Solving Patterns lesson contains separate interview practice.
Next
Continue from graph optimization to a different way of reusing subproblem answers.
HELP US IMPROVE
How was this lesson?
Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.
Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.
Discussion
0Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.
