6
$\begingroup$

In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)

$\endgroup$
0

3 Answers 3

3
$\begingroup$

I think you are correct:

All neighbors of a node will be of rank one less (the node we got here from) or one more (or two more, etc) because we will rank them before we back out of the node.

$\endgroup$
2
  • $\begingroup$ DFS and BFS visit edges in the same order under some constraints! In such cases neighbors in the tree are also neighbors in the graph. Correct me if I'm wrong. $\endgroup$
    – mrk
    Sep 24, 2012 at 16:54
  • $\begingroup$ @saadtaame You are wrong. $\endgroup$ Jan 1, 2016 at 5:19
3
$\begingroup$

The wikipedia article states that "it can be shown that if the graph is undirected then all of its edges are tree edges or back edges."

If you find out how this can be shown, you should be quite close to your solution.

$\endgroup$
1
  • $\begingroup$ If the edge is not a back edge (an edge you walk back in on) than it will be a tree edge b/c you will walk out it. $\endgroup$
    – BCS
    Jan 6, 2009 at 0:21
-1
$\begingroup$

Your question does not stipulate how the DFS tree is generated. Naive implementations simply list nodes in the order they are visited, but most practical implementations rebuild the output tree as the search progresses and the ranks of the nodes are adjusted.

Consider three nodes, A B C, connected to each other. A naive DFS will visit A B C, with ranks of 0 1 2, and the tree will have a back edge from C to A. A more useful implementation will backtrack from C to B to A, and then from A will travel to C again and assign it a rank of 1, then decline to travel to B at rank 2 because B is already rank 1, this tree will have both B and C at rank 1 below A, with a cross edge between B and C.

$\endgroup$
3
  • $\begingroup$ this is not correct $\endgroup$
    – Joe
    Sep 25, 2012 at 0:41
  • $\begingroup$ @Joe could you elaborate on that? In re-reading my example I see that it's not as clear as it might be, so I'd be happy to rewrite it if it is confusing to you. $\endgroup$
    – Sparr
    Sep 26, 2012 at 16:51
  • $\begingroup$ What you describe is more like a DFS followed by a BFS. Nodes that have already been visited are not re-visited in any standard DFS. $\endgroup$
    – Joe
    Sep 27, 2012 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.