Hi Mosh, why the output is different in Recursive and Iterative method in Graph lectures
for the graph the solution for
DFS in Recursive is ABDC
DFS in Iterative is ACBD
please suggest which one is correct or why the output is different there.
IIRC, both were valid because DFS means you can visit nodes at the same depth in any order. If Mosh’s code visited something at a deeper depth before an earlier depth, it would be a bug in his code. If the order is just different, but within the same depth, both answers are valid.
For example, in a fully connected clique with four nodes A to D, all of the following traversals are valid starting at A:
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
This is because B, C, and D are all at depth 1. If we add a 5th node E which is one hop away from A, but is connected to at least one other node, then the valid traversals would be the same, just adding an E at the end. Everything within the depth 1 set can be in any order, they just have to be visited before anything at depth 2.
In contrast, binary trees have exact ordering depending on if you use preorder, postorder or inorder traversals. Graphs have much greater variety.