The first linear time algorithm for finding the bridges in a graph was described by Robert Tarjan in 1974.
It performs the following steps:
* Find a spanning forest of G
* Create a rooted forest F from the spanning forest
* Traverse the forest F in preorder and number the nodes. Parent nodes in the forest now have lower numbers than child nodes.
* For each node v in preorder (denoting each node using its preorder number), do:
* Compute the number of forest descendants {\displaystyle ND(v)}ND(v) for this node, by adding one to the sum of its children's descendants.
* Compute {\displaystyle L(v)}L(v), the lowest preorder label reachable from {\displaystyle v}v by a path for which all but the last edge stays within the subtree rooted at {\displaystyle v}v. This is the minimum of the set consisting of the preorder label of {\displaystyle v}v, of the values of {\displaystyle L(w)}L(w) at child nodes of {\displaystyle v}v and of the preorder labels of nodes reachable from {\displaystyle v}v by edges that do not belong to {\displaystyle F}F.
* Similarly, compute {\displaystyle H(v)}H(v), the highest preorder label reachable by a path for which all but the last edge stays within the subtree rooted at {\displaystyle v}v. This is the maximum of the set consisting of the preorder label of {\displaystyle v}v, of the values of {\displaystyle H(w)}H(w) at child nodes of {\displaystyle v}v and of the preorder labels of nodes reachable from {\displaystyle v}v by edges that do not belong to {\displaystyle F}F.
* For each node {\displaystyle w}w with parent node {\displaystyle v}v, if {\displaystyle L(w)=w}L(w)=w and {\displaystyle H(w)<w+ND(w)}H(w)<w+ND(w) then the edge from {\displaystyle v}v to {\displaystyle w}w is a bridge.