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?
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!
Tarjan linear time algorithm for articulation vertex (cut vertex). See http://en.wikipedia.org/wiki/Biconnected_component