CmSc 250 Intro to Algorithms
Applications of Depth-first Search: Connectivity
Definition: An undirected graph is said to be connected if for any pair of nodes of the graph, the two nodes are reachable from one another (i.e. there is a path between them).
If starting from any vertex we can visit all other vertices, then the graph is connected.
We can do the same with breadth-first search, however the depth-first recursive implementation is straight-forward, while the breadth-first search requires a queue.
A graph is biconnected, if there are no vertices whose removal will disconnect the graph.
We can remove any vertex and the rest of the graph will still be connected.
The next graph is not biconnected:
If we remove C, the graph will become disconnected. Such vertices are called articulation points or cut-vertices.
There is a related concept for edges:
Any edge in a graph, that does not lie on a cycle, is a bridge.
Obviously, a bridge has at least one articulation point at its end, however an articulation point is not necessarily linked in a bridge. For example, none of the edges ending in C in the above graph, is a bridge
Example of bridges:
Here (C,D) and (D,E) are bridges, C and D are articulation points, while E is not an articulation point.
We can compute articulation points using depth-first search and a special numbering of the vertices in the order of their visiting.
Here are some more examples of articulation points, bridges, and biconnected graphs:
Example 1: C is an articulation point, there are no bridges
Example 2: C is an articulation point, CB is a bridge
Example 3: B and C are articulation points, BC is a bridge
Example 4: B and C are articulation points. All edges are bridges
Example 5: Biconnected graph - no articulation points and no bridges
Definition: A directed graph is said to be strongly connected if for any pair of nodes there is a path from each one to the other.
Definition: A directed graph is said to be unilaterally connected if for any pair of nodes at least one of the nodes is reachable from the other.
Definition: A directed graph is said to be weakly connected if the underlying undirected graph is connected.
Strongly connected graph:
Unilaterally connected graph:
Weakly connected graph:
Back to Contents page
Created by Lydia Sinapova