Schmidt's Bridge Finding Algorithm

While out looking for an algorithm to check for bridges in graphs, I found this paper by Jens Schmidt. It's very simple, and claims to be as fast as Tarjan's classic algorithm.

The basic idea is to make something he calls a 'chain decomposition' of the graph, where a 'chain' is either a cycle or a path. This is quite similar to the 'parts' of a graph I described here, except more formal than my slightly ad-hoc definitions.

Bridges, then are just those edges that are not in a chain. For example, take the graph from the paper:



Click for bigger, as always. First make a spanning tree from the graph, and store the back-edges (curved edges in the picture). Then go through the back-edges in order of the depth-first index, and make chains from them and the tree edges. A chain that ends up back at the start is a cycle, otherwise it is an edge. The chains A-E are shown in the middle, along with a bridge F.

The author also claims that the chain decomposition can be used in further algorithms, so it seems quite useful. My implementation is currently here, although it could probably be improved.

Comments