Spanning trees
A spanning tree connects every vertex of a network using as few edges as possible. Choosing the cheapest one is a classic optimisation problem.
What a spanning tree is
A spanning tree of a connected graph is a subgraph that is a tree and includes every vertex. It keeps the graph connected with the minimum number of edges, \(n - 1\). A graph usually has many spanning trees; \(K_n\) has \(n^{n-2}\) of them by Cayley's formula.
Finding a spanning tree
Breadth-first or depth-first search from any vertex produces a spanning tree: record the edge used to reach each new vertex. These search trees are used to explore networks, find connected components, and route data.
Minimum spanning trees
In a weighted graph, a minimum spanning tree (MST) is a spanning tree with the smallest total weight. Laying cable to connect towns at the lowest cost, designing circuits, and clustering data all reduce to MSTs.
Kruskal's algorithm
Sort edges by weight. Add edges from cheapest upward, skipping any edge that would form a cycle, until \(n - 1\) edges are chosen. Kruskal's algorithm is greedy: it always takes the cheapest safe edge, and remarkably this local strategy produces a global optimum.
Prim's algorithm
Start from any vertex. Repeatedly add the cheapest edge connecting the current tree to a new vertex. Prim's algorithm grows a single tree outward and, like Kruskal's, always produces a minimum spanning tree. With a priority queue it runs in \(O(E\log V)\) time.
Worked example
Towns A, B, C, D have road costs AB = 4, AC = 1, BC = 2, BD = 5, CD = 8. Kruskal: take AC (1), then BC (2), skip AB (4) since A-C-B already connects them, then take BD (5). Total cost 8. Every vertex is connected with 3 edges, and no cheaper set exists.
Why greedy works here
The cut property explains it: for any division of the vertices into two groups, the cheapest edge crossing between them belongs to some minimum spanning tree. Both algorithms only ever add such edges, so they never make a choice that must later be undone.
Common mistakes
Adding an edge that forms a cycle in Kruskal's algorithm. Confusing a minimum spanning tree with a shortest path tree; they solve different problems. Forgetting that a spanning tree must include every vertex.
Key takeaways
Spanning trees connect all vertices with \(n - 1\) edges. BFS and DFS produce them. Minimum spanning trees minimise total weight and are found greedily by Kruskal's (cheapest edges, avoid cycles) or Prim's (grow one tree) algorithm. The cut property explains why greed succeeds.
Flashcard
A tree containing every vertex
Check your understanding
In Kruskal's algorithm, an edge is skipped when: