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.1 Connected Components

Problem Input | Problem Output

INPUT                    OUTPUT


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

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

Excerpt from The Algorithm Design Manual: The connected components of a graph represent, in grossest terms, the pieces of the graph. Two vertices are in the same component of G if and only if there is some path between them.

Finding connected components is at the heart of many graph applications. For example, consider the problem of identifying clusters in a set of items. We can represent each item by a vertex and add an edge between each pair of items that are deemed ``similar.'' The connected components of this graph correspond to different classes of items.

Testing whether a graph is connected is an essential preprocessing step for every graph algorithm. Such tests can be performed so quickly and easily that you should always verify that your input graph is connected, even when you know it has to be. Subtle, difficult-to-detect bugs often result when your algorithm is run only on one component of a disconnected graph.


Implementations

  • Boost: C++ Libraries (C++) (rating 10)
  • JUNG: Java graph data structure (Java) (rating 9)
  • JGraphT: Java graph library (Java) (rating 9)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 9)
  • JDSL: Java Data Structures Libary (Java) (rating 8)
  • Algorithm and Data Structure Repository (C) (rating 5)

  • Recommended Books

    Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein Introduction to Algorithms by U. Manber Computer Algorithms by S. Baase
    Data Structures and Algorithms by A. Aho and J. Hopcroft and J. Ullman Graph Algorithms by S. Even Recreations Mathematiques by E. Lucas

    Related Problems


      
    Edge and Vertex Connectivity
      
    Shortest Path
      
    Transitive Closure and Reduction



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