Hopcroft-Tarjan

Abstract view

Algorithmic problem: Biconnected components

Type of algorithm: two steps.

Step 1

Abstract view: A variation of DFS, where for each node [math]\displaystyle{ v\in v }[/math] two additional nonnegative integral numbers are computed:

1. The 'depth of [math]\displaystyle{ v }[/math] in the arborescence created by the DFS procedure.
2. The lowpoint, that is, the minimal depth of any node [math]\displaystyle{ w/in V }[/math] such that [math]\displaystyle{ (u,w)\in A }[/math] for some immediate or non-immediate successor of [math]\displaystyle{ v }[/math] in the DFS tree.

Implementation:

1. The DFS maintains a global integral number, the current depth. Whenever a node is seen for the first time, its depth attribute is set identical to the current depth. In each forward step, the current depth is increased by one, in each backward step, it is decreased by one.
2. Whenever a node [math]\displaystyle{ v\in V }[/math] is seen for the first time, its lowpoint is set identical to its depth. Whenever an arc [math]\displaystyle{ (v,w) }[/math] is examined such that [math]\displaystyle{ w }[/math] has already been seen and the depth of [math]\displaystyle{ w }[/math] is smaller than the lowpoint of [math]\displaystyle{ v }[/math], the lowpoint of [math]\displaystyle{ w }[/math] is set identical to the depth of [math]\displaystyle{ w }[/math].

Step 2

Abstract view: A repeated application of DFS, where the start nodes of the individual DFS runs are exactly those nodes [math]\displaystyle{ v\in V }[/math] for which the lowpoint of [math]\displaystyle{ v }[/math] is not smaller than the depth of [math]\displaystyle{ v }[/math]. These nodes are considered in ascending order of their finishing times as computed in step 1. The nodes hit in a DFS run are removed from [math]\displaystyle{ G }[/math] before the next DFS run commences. The node sets visited in the individual DFS runs are the biconnected components.

Complexity

Statement: The asymptotic complexity is linear.

Proof: Follows immediately from the linear asymptotic complexity of DFS.