1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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!
$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Luke Mathieson Feb 20 '14 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.