Greedy Algorithms for a Minimum Spanning Tree

Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
Two greedy algorithms (due to Prim [1] and Kruskal [2]) have been proved to find an optimal spanning tree. This Demostration lets you visualize the two algorithms in either 2D or 3D.
Contributed by: Frederick Wu (May 2009)
Open content licensed under CC BY-NC-SA
Snapshots
Details
[1] R. C. Prim, "Shortest Connection Networks and Some Generalizations," Bell System Tech. J., 36, 1957 pp. 1389–1401.
[2] J. B. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem," Proc. Amer. Math. Soc., 7, 1956 pp. 48–50.
[3] F. Wu, Chapter 6, Manipulate@Mathematica, Beijing: Tsinghua, 2010.
Permanent Citation
"Greedy Algorithms for a Minimum Spanning Tree"
http://demonstrations.wolfram.com/GreedyAlgorithmsForAMinimumSpanningTree/
Wolfram Demonstrations Project
Published: May 14 2009