next up previous contents index CD CD Algorithms
Next: Topological Sorting Up: Graph Problems: Polynomial-Time Previous: Graph Problems: Polynomial-Time

Connected Components



Input description: A directed or undirected graph G.

Problem description: Traverse each edge and vertex of all connected components of G.

Discussion: 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.

Testing the connectivity of any undirected graph is a job for either depth-first or breadth-first search, as discussed in Section gif.     Which one you choose doesn't really matter. Both traversals initialize a component-number field for each vertex to 0, and then start the search for component 1 from vertex tex2html_wrap_inline28563 . As each vertex is visited, the value of this field is set to the current component number. When the initial traversal ends, the component number is incremented, and the search begins again from the first vertex with component-number still 0. Properly implemented using adjacency lists, this runs in O(n+m), or time linear in the number of edges and vertices.

Other notions of connectivity also arise in practice:

Implementations:     LEDA (see Section gif) provides good implementations of breadth-first and depth-first search, connected components and strongly connected components, all in C++. XTango (see Section gif) is an algorithm animation system   for UNIX and X-windows, which includes an animation of depth-first search.

Pascal implementations of BFS, DFS,   and biconnected and strongly connected components appear in [MS91]. See Section gif for details. Combinatorica [Ski90] provides Mathematica implementations    of the same routines. See Section gif.

The Stanford GraphBase (see Section gif) contains routines to compute biconnected and strongly connected components.    An expository implementation of BFS and DFS in Fortran appears in [NW78] (see Section gif).

Notes:   Depth-first search was first used in algorithms for finding paths out of mazes, and dates back to the nineteenth century [Luc91, Tar95]. Breadth-first search was first reported to find the shortest path out of mazes by Moore in 1957 [Moo59].

Hopcroft and Tarjan [HT73b, Tar72] first established depth-first search as a fundamental technique for efficient graph algorithms. Expositions on depth-first and breadth-first search appear in every book discussing graph algorithms, with [CLR90] perhaps the most thorough description available.

The first linear-time algorithm for strongly connected components is due to Tarjan [Tar72], with expositions including [Baa88, Eve79a, Man89]. Another algorithm, simpler to program and slicker, to find strongly connected components is due to Sharir and Kosaraju. Good expositions of this algorithm appear in [AHU83, CLR90].

Related Problems: Edge-vertex connectivity (see page gif), shortest path (see page gif).    

next up previous contents index CD CD Algorithms
Next: Topological Sorting Up: Graph Problems: Polynomial-Time Previous: Graph Problems: Polynomial-Time

Mon Jun 2 23:33:50 EDT 1997