# Depth-first spanning tree?

I am going to identify tree edges and back edges in an undirected graph.

The graph consists of $5$ nodes, the edges between these nodes are as shown below:

Suppose starting with $v_1$, after a depth-first searching, what are tree edges and back edges?

My back edges are edge $(v_4,v_2)$ and edge $(v_5,v_2)$, but the textbook says edge $(v_3,v_2)$ and edge $(v_5,v_2)$ are back edges.

My traverse order is $v_1\to v_2\to v_3\to v_4\to v_5$; it seems the traversal order in the textbook is $v_1\to v_2\to v_4\to v_3\to v_5$?

I am confused with the textbook result, And I can not figure out where is the different result from?

I think your idea is exactly correct. You are right, the tree edges and back edges depend not only on the graph itself, but also on the particular depth-first traversal that one has. The traversal you gave has the back edges that you said. The traversal you think the book chose does have the back edges that the book says. Are you sure the book did not say that the traversal was $v_1\to v_2\to v_4\to v_3\to v_5$? –  MJD Jul 9 '12 at 20:26
Traversal order makes sense for any connected graph. Based on the recursive call, we see that once DFS reaches $v_3,$ it "backs up" to $v_2$ and then looks for remaining unexplored edges (the only one of which is $v_2v_5.)$ The order of traversal ultimately comes down to the organization of your data structure (typically the way vertices are sorted in adjacency lists.) –  user17794 Jul 9 '12 at 20:34