11348
EXPLORE
LATEST
ABOUT
AUTHORING AREA
PARTICIPATE
Your browser does not support JavaScript or it may be disabled!
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.
Contributed by:
Frederick Wu
THINGS TO TRY
Rotate and Zoom in 3D
Automatic Animation
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.
RELATED LINKS
Connecting Towns Using Kruskal's Algorithm
(
Wolfram Demonstrations Project
)
Kruskal's Algorithm
(
Wolfram
MathWorld
)
Minimum Spanning Tree
(
Wolfram
MathWorld
)
Reconstruction of the Great Wall
(
Wolfram Demonstrations Project
)
PERMANENT CITATION
Frederick Wu
"
Greedy Algorithms for a Minimum Spanning Tree
"
http://demonstrations.wolfram.com/GreedyAlgorithmsForAMinimumSpanningTree/
Wolfram Demonstrations Project
Published: May 14, 2009
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 »
Download Demonstration as CDF »
Download Author Code »
(preview »)
Files require
Wolfram
CDF Player
or
Mathematica
.
Related Demonstrations
More by Author
The Geometry of the Steiner Tree Problem for up to Five Points
Ferenc Beleznay
The Traveling Salesman Problem 4: Spanning Tree Heuristic
Jaime Rangel-Mondragon
The Vehicle Routing Problem
Stan Wagon and Yu Zhao
Global Minimum of a Surface
Daniel de Souza Carvalho
Huffman Tree Encoding
Piril Nergis
Reconstruction of the Great Wall
Frederick Wu
Connecting Towns Using Kruskal's Algorithm
Ed Pegg Jr
Constructing a Steiner Tree for Five Points
Ferenc Beleznay
The Blossom Algorithm for Weighted Graphs
Stan Wagon
The Floyd-Warshall Algorithm on Adjacency Matrices and Directed Graphs
Adithya Vekatesan and Ankit Goyal
Related Topics
Algorithms
Approximation Methods
Graph Theory
Optimization
Browse all topics
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to
Mathematica Player 7EX
I already have
Mathematica Player
or
Mathematica 7+