Menu
Given the above graph, the DFS traversal with a stack gives me the folowing path...
1-2-3-4-5-6
Is the above path valid? Does there exists another path? (my textbook gives me 1-2-3-6-4-5)
I don't have enough rep to post images over at computer science stack so I had to resort to asking here, not sure if it fits; if it doesn't I am happy to delete it afterwards.
Thanks,
567
Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
Depth-first search (DFS) is an algorithm for searching a graph or tree data structure. The algorithm starts at the root (top) node of a tree and goes as far as it can down a given branch (path), then backtracks until it finds an unexplored path, and then explores it.
Example of DFS algorithm Step 1 - First, push H onto the stack. Step 2 - POP the top element from the stack, i.e., H, and print it. Now, PUSH all the neighbors of H onto the stack that are in ready state. Step 3 - POP the top element from the stack, i.e., A, and print it.
You have listed a perfectly valid DFS traversal of the graph, and the textbook is giving you another totally legal DFS traversal of the graph. There can be many depth-first traversals of the same graph (in fact, there's often exponentially many of them), so if you don't get the same one as your textbook that's not an immediate cause for 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 nodes ought to be visited (for example, always visiting connected nodes in ascending or descending order), then a DFS search will always produce the same output.
Hope this helps!
158
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
