5.3 Depth First Spanning Trees

Any edge v,w(v,w) that leads to the discovery of an unvisited vertex during a depth-first search is referred to as a tree edge of GG. Collectively, the tree edges of GG form a depth-first spanning tree of GG. 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(ρ,w,v\rho,w,v) to execute.

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

If GG 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 ww is neither an ancestor nor descendant of vv, then v,w(v,w) is called a cross edge.

If GG 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.