How to find the order in which DFS algorithm will inspect the nodes?

Question

I have been taking Artificial Intelligence course in College. I came upon this problem. Now here I have to find the order in which DFS algorithm inspects the nodes and what is the path from Start to Goal State. And wherever this contention between more than one nodes, left one is to be chosen.

So according to DFS algorithm, I would add {A,B,C} in stack. {D,E,B,C} -> {K,E,B,C} -> {M,E,B,C} -> {O,E,B,C} -> {F,G,E,B,C}. Now I cannot understand what to do further, should I go to B and then backtrack again with B already being in the stack or do something different. And the path would be S -> B -> G or else S -> A -> D -> K -> M -> O -> G.

How to decide what way to go?

Answer 1

You would keep track of a list of states that you have already visited. As you progress through the graph, you add the node you choose to that list.

By the time you are at F, B is not yet on the visited list (though it is on the stack), so you would go to B. From there you would got to S, which you have already visited, so then choose the next possibility, G, which is your goal.

There is an implementation detail that would change the behaviour: you could also put nodes from the stack into your list (because arguably you would visit B much earlier if you didn't take the detour via O), in which case you would backtrack from F to O, and then move on to G.

I don't think this is fixed in DFS; you're still following the principle of exploring the current path until the end. It's similar in status to "always choose the left node to proceed": an implementation detail (though important, as it changes the outcome).