Greedy Algorithms for a Minimum Spanning Tree

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send