Hopcroft-Tarjan: Difference between revisions
(→Step 1) |
No edit summary |
||
| Line 22: | Line 22: | ||
'''Abstract view:''' | '''Abstract view:''' | ||
A repeated application of [[Depth-first search|DFS]], where the start nodes of the individual DFS runs are exactly those nodes <math>v\in V</math> for which the lowpoint of <math>v</math> is not smaller than the depth of <math>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>G</math> before the next DFS run commences. The node sets visited in the individual DFS runs are the biconnected components. | A repeated application of [[Depth-first search|DFS]], where the start nodes of the individual DFS runs are exactly those nodes <math>v\in V</math> for which the lowpoint of <math>v</math> is not smaller than the depth of <math>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>G</math> before the next DFS run commences. The node sets visited in the individual DFS runs are the biconnected components. | ||
== Correctness == | |||
== Complexity == | |||
'''Statement:''' | |||
The asymptotic complexity is linear. | |||
'''Proof:''' | |||
Follows immediately from the linear asymptotic complexity of DFS. | |||
Revision as of 13:10, 30 October 2014
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:
- The 'depth of [math]\displaystyle{ v }[/math] in the arborescence created by the DFS procedure.
- 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:
- 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.
- 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.
Correctness
Complexity
Statement: The asymptotic complexity is linear.
Proof: Follows immediately from the linear asymptotic complexity of DFS.