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
    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