Advanced Graphs
Connecting everything cheaply
Not a shortest path. The cheapest set of edges that leaves nothing isolated.
Key idea
A different question from shortest paths
Shortest paths minimize the cost from one node to each other node. A spanning tree minimizes the total cost of the edges chosen, subject to everything being connected.
These give different answers and it is worth being clear that they are different problems. The cheapest network connecting a set of towns is usually not the network of cheapest individual routes from one town.
A spanning tree of n nodes always has exactly n minus 1 edges, which is the same fact from U12's tree lesson.
Why it works
Grow one component, always taking the cheapest edge leaving it
Start from any node. Repeatedly take the cheapest edge connecting the grown set to something outside it, and absorb that node. Stop when everything is inside.
A heap holds the candidate edges leaving the current set, which is exactly the structure that hands back the smallest. The shape of the loop is nearly identical to the shortest-path one, and the difference is one expression: push the edge weight rather than the accumulated total.
Here is the very first step, with one node inside the set and every edge out of it offered to the heap.
Tip
One expression different from the shortest-path version
In the shortest-path algorithm, a neighbor is pushed with the accumulated cost from the start. Here it is pushed with just the edge weight.
That single change turns minimize the distance from the start into minimize the cost of joining. Seeing that these two famous algorithms differ by one expression is worth more than remembering both separately.
Key idea
The other standard approach
Sort every edge by weight and add them cheapest first, skipping any edge whose two ends are already connected. Stop after n minus 1 edges have been added.
The connectivity test is union-find from U12, and its return value is exactly the skip condition. This is where that structure pays off a second time.
The two approaches suit different inputs. Growing from a node is better on dense graphs where edges are implied rather than listed; sorting edges is better when the edge list is given and sparse.
Tip
When every pair is an edge
For points on a plane, every pair can be connected, so there are about n squared edges and none of them are handed to you. Sorting them all costs O(n squared log n), while growing from a node and generating candidates on demand costs O(n squared log n) too but never materializes the list.
For this shape the growing version is the natural choice, which is why the example above uses it. Saying why you picked one is more valuable than the pick itself.
Cost
Cost
The growing version with a binary heap is O(E log V). The sorting version is O(E log E) for the sort plus effectively linear for the union-find checks, which is the same thing.
On a dense graph where E is about V squared, both come out around O(V squared log V). There are better bounds using more elaborate heaps and they are not worth raising unless asked.
What changes between the two algorithms?
You have working code for weighted shortest paths from a start node. What single change turns it into a minimum spanning tree algorithm?
Min Cost To Connect All Points
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.