7899
TOPICS
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!
Download Demonstration as CDF »
Download Source Code »
(preview »)
Files require
Wolfram
CDF Player
or
Mathematica
.
Related Demonstrations
More by Author
Reconstruction of the Great Wall
Frederick Wu
Connecting Towns Using Kruskal's Algorithm
Ed Pegg Jr
The Blossom Algorithm for Weighted Graphs
Stan Wagon
Optimal Bin Packing with Random Lengths
Yifan Hu and Stephen Wolfram
Iterations of Some Algorithms for Nonlinear Fitting
Heikki Ruskeepää
Iterations of Some Algorithms for Unconstrained Local Optimization
Heikki Ruskeepää
Ant Colony Optimization (ACO)
Rasmus Kamper
Hill-Climbing Algorithm
Ivan Zelinka
Evolutionary Multiobjective Optimization
Robin Gruna
Shortening the 29th Olympic Torch Tour
Frederick Wu
Related Topics
Algorithms
Approximation Methods
Graph Theory
Optimization
Browse all topics
Contribute
Make a new version of this Demonstration
Upload a new Demonstration
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+
![[Snapshot]](HTMLImages/index.en/thumbnail_1.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_2.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_3.gif)
Embed Interactive Demonstration 
Browse all topics
