Mathematica MathWorld Wolfram Science More »

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.

(16 lines omitted)

[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.

Contributed by: Frederick Wu

Report an issue »

	Source page:
	Email	Name (optional)
	Occupation (optional)	Organization (optional)
	I use Mathematica often occasionally never
	Country (optional) Remember me
	Note: Please do not include anything you consider confidential or proprietary. Your message and contact information may be shared with the author of any specific Demonstration for which you give feedback, but will not otherwise be published or distributed. Privacy Policy »

RSS

Atom