next up previous contents index CD CD Algorithms
Next: Tree and Cycle Detection Up: Applications of Graph Traversal Previous: Applications of Graph Traversal

Connected Components

Either breadth-first or depth-first search can be used to identify the connected components of an undirected graph and label each vertex with the identifier of its components. In particular, we can modify the DFS-graph algorithm to increment a counter for the current component number and label each vertex accordingly as it is discovered in DFS.  

For directed graphs, there are two distinct notions of connectivity, leading to algorithms for finding both weakly connected and strongly connected components. Both of these can be found in O(n+m) time, as discussed in Section gif.

Mon Jun 2 23:33:50 EDT 1997