5.3 Depth First Spanning Trees

Any edge $(v,w)$ that leads to the discovery of an unvisited vertex during a depth-first search is referred to as a tree edge of $G$. Collectively, the tree edges of $G$ form a depth-first spanning tree of $G$. Tree edges are detected as follows:

• In Algorithm 5, the recursive depth-first search of Section 5.1, only the tree edges will cause map($\rho,w,v$) to execute.

• In Algorithm 6, the non-recursive depth-first search of Section 5.2, only tree edges cause visit($w,v$) to execute.

If $G$ is a directed graph, an edge that connects a vertex to one of its ancestors in the spanning tree is referred to as a back edge. An edge that connects a vertex to one of its descendants in the spanning tree is referred to as a forward edge. If $w$ is neither an ancestor nor descendant of $v$, then $(v,w)$ is called a cross edge.

If $G$ is an undirected graph, the depth-first spanning tree simplifies as follows:

• Back edges and forward edges are not distinguished.

• Cross edges do not exist.

Therefore, only two types of edge are defined for undirected graphs. We will call them tree edges and back edges.