# Applications of Depth-First Spanning Tree

I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that make use of the depth-first spanning tree?

## 2 Answers

You can find bridges, i.e. edges whose removal causes the graph to separate into disconnected components.

Assuming connected, undirected graphs, the key insight is that a tree edge $e = (v,w)$ ($v$ being the father of $w$ in the tree) is a bridge if and only if there is no backwards edge¹ connecting $w$ or a successor of $w$ with an ancestor of $w$ (in the search tree). If there were such an edge, $e$ could not be a bridge as it's part of a cycle.

By augmenting the depth-first search algorithm in a suitable way, we can do these checks along the road and thus get an $O(n + m)$ algorithm.

1. There can be no forward and cross edges!

Tarjan linear time algorithm for articulation vertex (cut vertex). See http://en.wikipedia.org/wiki/Biconnected_component

• Could you add some more detail about how the DFST is used in Tarjan's algorithm, and/or some reference material to make this answer stand on its own a bit better? – Luke Mathieson Feb 20 '14 at 13:53