Bridge-finding Algorithm
A 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
- Create a rooted forest from the spanning tree
- Traverse the forest in preorder and number the nodes. Parent nodes in the forest now have lower numbers than child nodes.
- For each node in preorder, do:
- Compute the number of forest descendants for this node, by adding one to the sum of its children's descendants.
- Compute, the lowest preorder label reachable from by a path for which all but the last edge stays within the subtree rooted at . This is the minimum of the set consisting of the values of at child nodes of and of the preorder labels of nodes reachable from by edges that do not belong to .
- Similarly, compute, the highest preorder label reachable by a path for which all but the last edge stays within the subtree rooted at . This is the maximum of the set consisting of the values of at child nodes of and of the preorder labels of nodes reachable from by edges that do not belong to .
- For each node with parent node, if and then the edge from to is a bridge.
Read more about this topic: Bridge (graph Theory)