Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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: enter image description here

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?

Please teach me. Thanks!

share|cite|improve this question
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
Thanks a lot. I was thinking did I miss something. – user900168 Jul 10 '12 at 3:02
The textbook only gives a graph illustrating the result depth-first spanning tree. my result is the same as the result form the text book except the part that is posted here. Indeed, the graph is on the page 182 in the book<The Design and Analysis of Computer Algorithms>. I hope my result will not affect finding bi-connected components of the original graph. – user900168 Jul 10 '12 at 3:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.