## Minimum Spanning Tree Animation |
||

The minimum spanning tree (MST) of a weighted graph is a spanning tree whose sum of edge
weights is minimal.
The minimum spanning tree describes the cheapest network to connect all of a given set
of vertices.
Kruskal's algorithm for minimum spanning tree works by inserting edges in order of increasing cost, adding as edges to the tree those which connect two previously disjoint components. Here we see Kruskal's algorithm at work on a graph of distances between 128 North American cities. Almost imperceptively at first, short edges get added all around the continent, slowly building larger components until the tree is completed. |
||

Download:
mst.gif - The Animation. mst.nb - Notebook file. usa.txt - Graph of United States. |
||

These animations were produced using
Check out our dfs/bfs, connected components, Hamiltonian cycle, Eulerian cycle, shortest path, transitive closure, and minimum spanning tree animations! |