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.


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

These animations were produced using Combinatorica -- see and our book Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica for more information.

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