Greedy Algorithms for a Minimum Spanning Tree

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.