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?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Yeah, you use it for instance in finding the strongly connected components with Micha Sharir's algorithm. en.wikipedia.org/wiki/Strongly_connected_component $\endgroup$– AturSamsCommented Feb 20, 2014 at 9:39
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
- There can be no forward and cross edges!
$\begingroup$
$\endgroup$
1
Tarjan linear time algorithm for articulation vertex (cut vertex). See http://en.wikipedia.org/wiki/Biconnected_component
-
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$ Commented Feb 20, 2014 at 13:53