1.4.3 Minimum Spanning Tree

INPUT OUTPUT
Input Description:
A graph G = (V,E) with weighted edges.
Problem:
The subset of E of G of minimum weight which forms a
tree on V.
Excerpt from
The Algorithm Design Manual:
The minimum spanning tree (MST) of a graph defines the cheapest subset of edges that keeps the graph in one
connected component. Telephone companies are particularly interested in minimum spanning trees, because the minimum
spanning tree of a set of sites defines the wiring scheme that connects the sites using as little wire as possible.
It is the mother of all network design problems.
Minimum spanning trees prove important for several reasons:
- They can be computed quickly and easily, and they create a sparse subgraph that reflects a lot about the
original graph.
- They provide a way to identify clusters in sets of points.
Deleting the long edges from a minimum spanning tree leaves
connected components that define natural clusters in the data set,
as shown in the output figure above.
- They can be used to give approximate solutions to hard problems such
as Steiner tree and traveling salesman.
- As an educational tool, minimum spanning tree algorithms
provide graphic evidence that greedy algorithms
can give provably optimal solutions.
The best book available for this problem is
Network Flows : Theory, Algorithms, and Applications
by
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.
Implementations
LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 6)
Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 5)
Moret and Shapiro's Algorithms P to NP (Pascal) (rating 5)
Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
The Stanford GraphBase (C) (rating 4)
Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 3)
Discrete Optimization Methods (Pascal) (rating 3)
Algorithms in C++ -- Sedgewick (C++) (rating 3)
Combinatorica (Mathematica) (rating 3)
Related Problems
Set Data Structures
Steiner Tree
Traveling Salesman Problem
Previous Problem
Next Problem
View the graph for this
file
Bulletin Board
About ``The Algorithm Design Manual''.
Send us Mail
The Stony Brook Algorithm Repository -- go to front page
This page last modified on Wed Mar 07, 2001
.