610
Graph Algorithms
the Algorithm itself
The key to the algorithm, as we may guess from the foregoing discussion, is keeping
track of the destinations of the back arcs. We will assign a tree number to each node
that corresponds to the order in which that node is visited in the depth-first search.
Thus the starting node in a depth-first search has tree number 1, the next node visited
has tree number 2, and so on. In addition, we will maintain a “back number” for each
node x. The back number will be the minimum tree number of a node (the farthest
back node) reachable from x using either back arcs from x or from descendants of x in
the subtree. To incorporate information about back arcs of descendants of x, the back
number of x is adjusted when the depth-first search backs up to node x from farther
down in the tree. Node n is an articulation point whenever a subtree of n has no back
arc to an ancestor of n, and this circumstance is detected when the search backs up to
n from the subtree. Suppose the search is backing up from x to n. If the back number
of x at this point is not smaller than the tree number of n, then n is an articulation point.
The following algorithm carries out the depth-first search and builds the
depth-first search tree. It correctly handles both leaves and nonstarting-node nonleaves of the depth-first search tree, leaving only the starting node as a special
case. It also assumes that the graph structure itself contains the tree number and
back number for each node.
algoRitHm artPoint
ArtPoint(graph G; node n; integer TreeNumber)
//detects articulation points in G by depth-first search from n; graph G
//also maintains a tree number TN and back number BN value for each
//node;TreeNumber = 0 when first invoked.
Local variable:
node x
//temporary node
mark n visited
//first encountering n, assign its numbers
TreeNumber = TreeNumber + 1
TN3n4 = TreeNumber
BN3n 4 = TN3n 4
for each node x adjacent to n by a nontree edge do
if x not visited then
make n–x a tree edge
ArtPoint(G, x, TreeNumber)
//depth-first search now backing up to n from x
if BN3x 4 >= TN3n 4then
//line 1
write(“n is an articulation point”)
else
//adjust back number of n
BN3n 4 = min(BN3n 4, BN3x 4)
//line 2
end if
else
//arc n–x is a back edge, adjust BN 3n4
BN3n4 = min(BN3n 4, TN3x 4)
//line 3
end if
end for
end ArtPoint
Graph Algorithms
the Algorithm itself
The key to the algorithm, as we may guess from the foregoing discussion, is keeping
track of the destinations of the back arcs. We will assign a tree number to each node
that corresponds to the order in which that node is visited in the depth-first search.
Thus the starting node in a depth-first search has tree number 1, the next node visited
has tree number 2, and so on. In addition, we will maintain a “back number” for each
node x. The back number will be the minimum tree number of a node (the farthest
back node) reachable from x using either back arcs from x or from descendants of x in
the subtree. To incorporate information about back arcs of descendants of x, the back
number of x is adjusted when the depth-first search backs up to node x from farther
down in the tree. Node n is an articulation point whenever a subtree of n has no back
arc to an ancestor of n, and this circumstance is detected when the search backs up to
n from the subtree. Suppose the search is backing up from x to n. If the back number
of x at this point is not smaller than the tree number of n, then n is an articulation point.
The following algorithm carries out the depth-first search and builds the
depth-first search tree. It correctly handles both leaves and nonstarting-node nonleaves of the depth-first search tree, leaving only the starting node as a special
case. It also assumes that the graph structure itself contains the tree number and
back number for each node.
algoRitHm artPoint
ArtPoint(graph G; node n; integer TreeNumber)
//detects articulation points in G by depth-first search from n; graph G
//also maintains a tree number TN and back number BN value for each
//node;TreeNumber = 0 when first invoked.
Local variable:
node x
//temporary node
mark n visited
//first encountering n, assign its numbers
TreeNumber = TreeNumber + 1
TN3n4 = TreeNumber
BN3n 4 = TN3n 4
for each node x adjacent to n by a nontree edge do
if x not visited then
make n–x a tree edge
ArtPoint(G, x, TreeNumber)
//depth-first search now backing up to n from x
if BN3x 4 >= TN3n 4then
//line 1
write(“n is an articulation point”)
else
//adjust back number of n
BN3n 4 = min(BN3n 4, BN3x 4)
//line 2
end if
else
//arc n–x is a back edge, adjust BN 3n4
BN3n4 = min(BN3n 4, TN3x 4)
//line 3
end if
end for
end ArtPoint