1.4.1 Connected Components

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A directed or undirected graph G . A start vertex .

Problem: Traverse each edge and vertex of the connected component containing .

Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 8)
  • The Stanford GraphBase (C) (rating 4)
  • GraphEd -- Graph Editor and Layout Program (C) (rating 4)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 4)
  • Combinatorica (Mathematica) (rating 3)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 2)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 2)

    Related Problems

  • Edge and Vertex Connectivity
  • Shortest Path
  • Transitive Closure and Reduction

    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 .