Minimum Spanning Tree Animation

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.

These animations were produced using Combinatorica -- see www.combinatorica.com 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!