One of our readers sent us the following feedback:
In DFS you are showing visiting order of nodes as 01342 but when I run your code output is 02143.
Hi,
This is Fatimah Abdullah from Educative. Thank you for reaching out to us!
In response to your feedback, both the mentioned solutions: 02143 and 01342 are correct. Let me explain why. In theory, the below-mentioned graphs are totally identical:
But, the DFS traversal on these will give different output. This is because it depends upon the implementation. And each implementation is correct if it follows the definition of DFS traversal. The lesson, Graph Traversal Algorithms, states that:
The DFS algorithm is the opposite of BFS in the sense that it grows depth-wise.
Starting from any node, we keep moving to an adjacent node until we reach the farthest level. Then we move back to the starting point and pick another adjacent node. Once again, we probe till the farthest level and move back. This process continues until all nodes are visited.
Therefore, if we start DFS from the node (a), it does not matter if we visit node © or node (d) first, because they are at the same level. What matters is that in DFS we must first traverse all children of one node and then move on to the adjacent nodes.
You can also observe in the test case that both of these solutions are valid:
I hope this answers your question. However, if you have any follow-up questions, please feel free to get in touch.
Best Regards,
Fatimah Abdullah | Developer Advocate
Educative
1 Like