The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.4.3 Minimum Spanning Tree

Problem Input | Problem Output

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:


Implementations

  • Boost: C++ Libraries (C++) (rating 10)
  • JDSL: Java Data Structures Libary (Java) (rating 8)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 7)
  • The Stanford GraphBase (C) (rating 7)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 5)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 5)

  • Recommended Books

    Geometric Spanner Networks by G. Narasimhan and M. Smid Spanning Trees and Optimization Problems by B. Wu and K Chao Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky
    Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf Network Flows : Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica by S. Pemmaraju and S. Skiena
    Computational Geometry by F. Preparata and M. Shamos Combinatorial Optimization: Algorithms and Complexity by C. Papadimitriou and K. Steiglitz Combinatorial Optimization: Networks and Matroids by E. Lawler

    Related Problems


      
    Set Data Structures
      
    Steiner Tree
      
    Traveling Salesman Problem



    This page last modified on 2008-07-10 .
    www.algorist.com