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 .

Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 6)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 5)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 5)
  • The Stanford GraphBase (C) (rating 4)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
  • Combinatorica (Mathematica) (rating 3)
  • Algorithms in C++ -- Sedgewick (C++) (rating 3)
  • Discrete Optimization Methods (Pascal) (rating 3)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 3)

    Related Problems

  • Set Data Structures
  • Steiner Tree
  • Traveling Salesman Problem

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .