This animation gives a step-by-step visual presentation of Prim’s MST Algorithm, as well as a feature showing the key step in the proof of the algorithm’s correctness.
First, draw a graph as in the Graph Explorer, then press [W] to assign random edge weights to the graph (if you don’t like the edge weights you get, you can press [W] until you get ones that you like).
Optional step: when you’re ready to discuss the correctness of the algorithm, press [O] to highlight another minimum spanning tree (if one exists, you will get a green flash; if not, a red flash, and you can press [W] to reassign edge weights and try again).
Pressing [A] brings up an outline of the algorithm at the left; [Space] steps through the algorithm, illustrating each step on the graph and with variables indicated above. If you’re showing correctness, wait until the first red edge is added to the tree that was not included in the highlighted MST; the argument about replacing an edge of the highlighted MST with your edge is now easy to point at.
