patternMinor
Can two neighbors in a graph be at the same depth in a DFS tree?
Viewed 0 times
depthcanthesamegraphdfstwotreeneighbors
Problem
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)
Solution
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.
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.
Context
StackExchange Computer Science Q#4707, answer score: 3
Revisions (0)
No revisions yet.