170 GRAPH ALGORITHMS
To accomplish this algorithm, we will keep a count of how many nodes of the
graph we have visited. Each node will be assigned an index number indicating
when is it visited. In other words, the first node visited will be numbered 1, the
second will be numbered 2, and so on. When we reach a dead end, we will look
at all of the adjacent nodes (except for the node we just came from) and will use
the smallest index number as our back index. If there is just one adjacent node
(the one we just came from), we will return the dead end node’s index as our
back index. When we return to a node that is not the root of the search tree, we
will compare the back index value that was returned. If that value is greater than
or equal to the current node’s index value, the subtree just visited (minus any
previously found biconnected components) is a biconnected component. Each
internal node of the depth-first search tree will return the smallest value from
among the indices of adjacent nodes and any back indices returned to it.
How would this process work in our graph of Fig. 6.9? If we begin at node
F, it would be assigned an index of 1. We move to node D (index 2), then
nodes B (index 3), A (index 4), and C (index 5). Node C is a dead end, and we
have back edges to nodes A, B, and D. The index on node D is smallest, so a
value of 2 would be returned to node A as the back index. At node A, because
the value of 2 is less than node A’s index, it is not an articulation point. The
value of 2 is the smallest so far, and it is also returned to node B. This continues
until we get back to node D, where we find that the back index returned is the
same as node D’s index, and so the nodes A, B, C, and D make up a bicon-
nected component. We return to the root of the search tree at node F and then
move off to node E (index 6), followed by node G (index 7), and node H
(index 8). We next traverse down to node I (index 9), and because it is a dead
end with no adjacent nodes other than H, we return its index as the back
index. When node H receives a value of 9 from node I, which is greater than
the index of node H, we find another biconnected component with nodes H
and I. Node H now considers the values of 1 (the back edge to F), 9 (returned
from node I), and 8 (node H’s index), returning the smallest of these to node G
and then to node E. This value is then returned by node E to the root node,
and because all nodes have been visited, those that remain (nodes D, E, F, G,
and H) comprise the final biconnected component. In Fig. 6.10 we see the
result of this process, and from this we can see that the articulation points in
the original graph are nodes D and H, which are the only nodes that appear in
two separate components.