6.6 BICONNECTED COMPONENT ALGORITHM 169Determining the biconnected components of a network indicates how sta-
ble the network can be under degraded conditions. So, if all computers on a
network are part of the biconnected component of the related graph, we know
that the network will continue to function even if one of the computers is
down. In airline scheduling, the biconnected component of the graph for the
flight schedule indicates if passengers can be rerouted when an airport is closed
because of weather problems.
An articulation point in a connected graph is a node that, when it is
removed, causes the graph to no longer be connected. Articulation points of a
graph are nodes that are shared between two biconnected components. Nodes
D and H in Fig. 6.9 are articulation points. The identification of articulation
points and the determination of biconnected components are related.
We could identify the articulation points in a brute force manner by remov-
ing one node at a time and using one of our traversal methods to see if the
remaining nodes are still connected. If they are, the node we removed is not an
articulation point, but if they are not, it is an articulation point. This means
that we would have to do N traversals of a graph with N nodes. This process
would be O(N^2 ). By keeping a little additional information while we are tra-
versing, we can identify the articulation points and the biconnected compo-
nents on one traversal.
Think about paths in the graph in Fig. 6.9 that begin at node F. You should
see that no matter what order the nodes are visited in, the paths from node F to
nodes A, B, and C must go through node D. This means that node D is an
articulation point and the subgraph containing nodes A, B, C, and D is a
biconnected component.
We base our algorithm on depth-first search. You will recall from Section
6.3.1 that we said a depth-first search will follow edges into a graph until a
dead end is reached where there are no unvisited nodes adjacent to the cur-
rent node. When we reach a dead end, we will back up, but now our algo-
rithm will return information about how high up in the depth-first search
tree we could have gone at the dead end. These back edges in the search tree
indicate a cycle back in the graph. All the nodes in a cycle must be part of
the same biconnected component. The back edge location indicates how far
we have to back up in our tree before worrying about finding an articulation
point.