Geek Answers Handbook

DFS Bypass

enter image description here

Given the above chart, bypassing DFS with the stack gives me the following path ...

1-2-3-4-5-6

Is the above path valid? Is there any other way? (my tutorial gives me 1-2-3-6-4-5)

I don't have enough reputation for posting images on the computer science stack, so I had to resort to a request here, not sure if this fits; if it is not, I am happy to delete it afterwards.

Thanks,

+6
source share
2 answers

You specified a completely correct bypass of the DFS graph, and the tutorial gives you another completely finished bypass of the DFS graph. There can be many transitions in depth of the same graph (in fact, there are often exponentially many), so if you do not get the same as your textbook, that is not the immediate cause of the alarm.

Here are some other orderings:

1 2 5 4 3 6 3 1 6 2 5 4 5 4 2 3 1 6 ...

However, if there are some other rules about how to visit nodes (for example, always visiting linked nodes in ascending or descending order), then a DFS search will always return the same result.

Hope this helps!

+6
source

You are not describing a path, but the order in which DFS visits nodes. A path is a list of nodes where each node is connected to the previous and next node.

The output of a DFS bypass can also be seen as a DFS bypass tree, which in your case corresponds to:

 1 - 2 - 3 - 4 - 5 | 6

Textbook tree

 1 - 2 - 3 - 6 | 4 - 5

You can get many different DFS trees, because at every moment when you have a choice, you can decide where to go first. In your examples, from node 3, you can switch to node 4 or node 6, and the different outputs are due to different options.

+1
source

More articles:


All Articles