5.3 Depth First Spanning Trees
Any edge that leads to the discovery of an unvisited vertex during a depth-first search is referred to as a tree edge of . Collectively, the tree edges of form a depth-first spanning tree of . Tree edges are detected as follows:
If 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 is neither an ancestor nor descendant of , then is called a cross edge.
If 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.