8758
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!
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 Traveling Salesman Problem 4: Spanning Tree Heuristic
Jaime Rangel-Mondragon
The Vehicle Routing Problem
Stan Wagon and Yu Zhao
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
The Traveling Salesman Problem 2: 2-opt Removal of Intersections
Jaime Rangel-Mondragon
The Traveling Salesman Problem 1: Optimal Paths
Jaime Rangel-Mondragon
The Traveling Salesman Problem 3: Nearest Neighbor Heuristic
Jaime Rangel-Mondragon
Iterations of Some Algorithms for Nonlinear Fitting
Heikki Ruskeepää
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+
![[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
