Editing Bridge (graph theory) (section)

==Tarjan's bridge-finding algorithm==
The first [[linear time]] algorithm (linear in the number of edges) for finding the bridges in a graph was described by [[Robert Tarjan]] in 1974.<ref>{{citation
 | last = Tarjan | first = R. Endre | author-link = Robert Tarjan
 | doi = 10.1016/0020-0190(74)90003-9
 | year = 1974
 | issue = 6
 | journal = Information Processing Letters
 | mr = 0349483
 | pages = 160–161
 | title = A note on finding the bridges of a graph
 | volume = 2}}.</ref> It performs the following steps:
* Find a [[spanning forest]] of <math>G</math>
* Create a [[Tree_(graph_theory)#Rooted_tree|Rooted forest]] <math>F</math> from the spanning forest
* Traverse the forest <math>F</math> in [[Tree traversal#Pre-order, NLR|preorder]] and number the nodes. Parent nodes in the forest now have lower numbers than child nodes.
* For each node <math>v</math> in preorder (denoting each node using its preorder number), do:
** Compute the number of forest descendants <math>ND(v)</math> for this node, by adding one to the sum of its children's descendants.
** Compute <math>L(v)</math>, the lowest preorder label reachable from <math>v</math> by a path for which all but the last edge stays within the subtree rooted at <math>v</math>. This is the minimum of the set consisting of the preorder label of <math>v</math>, of the values of <math>L(w)</math> at child nodes of <math>v</math> and of the preorder labels of nodes reachable from <math>v</math> by edges that do not belong to <math>F</math>.
** Similarly, compute <math>H(v)</math>, the highest preorder label reachable by a path for which all but the last edge stays within the subtree rooted at <math>v</math>. This is the maximum of the set consisting of the preorder label of <math>v</math>, of the values of <math>H(w)</math> at child nodes of <math>v</math> and of the preorder labels of nodes reachable from <math>v</math> by edges that do not belong to <math>F</math>.
** For each node <math>w</math> with parent node <math>v</math>, if <math>L(w) = w</math> and <math>H(w) <  w + ND(w)</math> then the edge from <math>v</math> to <math>w</math> is a bridge.