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).

  1. Algorithm

  2. 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.

  3. Biconnectivity

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

    An edge in a graph is called a bridge, if its removal disconnects the graph.
    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

  5. Connectivity in directed graphs

  6. 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.

    Examples:

    Strongly connected graph:

    Unilaterally connected graph:

    Weakly connected graph:


Exam-like questions

  1. Draw a biconnected graph.
  2. Draw a graph with one articulation point and no bridges.
  3. Draw a graph with two articulation points and a bridge.
  4. Draw a graph with two bridges. How many articulation points are there in your graph?

Back to Contents page
Created by Lydia Sinapova