0
$\begingroup$

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!

  • 0
    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$?2012-07-09
  • 0
    Traversal order makes sense for any connected graph. Based on the [recursive call](http://en.wikipedia.org/wiki/Depth-first_search#Pseudocode), 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.)2012-07-09
  • 0
    Thanks a lot. I was thinking did I miss something.2012-07-10
  • 0
    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. I hope my result will not affect finding bi-connected components of the original graph.2012-07-10

0 Answers 0