Trace Prim's Algorithm Growing One Tree

Prim's algorithm builds a minimum spanning tree by growing one tree from a start vertex, each time adding the lightest edge that joins the tree to a vertex outside it. This card traces it on the topic's graph from A, keeping for every vertex outside the tree the lightest edge that reaches it from inside, and shows that it adds edges in a different order from Kruskal's algorithm.

For each vertex outside the tree, its best edge is the lightest edge from it to any vertex already in the tree, or none if no edge reaches the tree yet. Each step adds the vertex with the lightest best edge, then lowers the best edges of its neighbours where it now offers a lighter one.

The topic's graph has the undirected edges A-B 4, A-C 1, B-C 2, B-D 5, C-D 8, C-E 9, D-E 3, D-F 7 and E-F 6.

Every step is the cut property with one particular cut: the tree on one side, every other vertex on the other. The lightest best edge is the lightest edge crossing that cut, so it is safe. The third step is the cut drawn on Minimum Spanning Trees and the Cut Property, and B-D 5 is its lightest crossing edge.

Prim's algorithm took B-D 5 before D-E 3, the reverse of Kruskal's order, because D-E touched no vertex of the tree until D joined. Kruskal's algorithm keeps several trees and joins them; Prim's keeps one and grows it, so every edge it adds touches the tree. Both finished with the same five edges and the same total, 17, as they must when no two weights are equal.

The trace looks like Dijkstra's algorithm, and the difference is one number. Dijkstra's algorithm ranks a vertex by its whole distance from the source; Prim's ranks it by the weight of one edge into the tree. E's best edge here is D-E 3, while its distance from A along the tree is 11.

Reach for Prim's algorithm when the graph is dense or stored as lists of neighbours, since it only ever looks at the edges of the vertex just added.