Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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 &quot;always choose the left node to proceed&quot;: an implementation detail (though important, as it changes the outcome).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-05T10:13:42.210Z
Answers.Text: You could mention [_graph search_](https://ai.stackexchange.com/a/9554/2444), which is the term that Norvig and Russell (and most AI people) use to refer to the general state-space search that keeps track of what has already been visited.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-27T08:10:09.557Z
Answers.LastActivityDate: 2022-05-27T08:10:09.557Z
Answers.UserDisplayName: Oliver Mason
Body: <p><a href="https://i.sstatic.net/mwRYd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mwRYd.png" alt="enter image description here" /></a></p>
  <p>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.</p>
  <p>So according to DFS algorithm, I would add <strong>{A,B,C}</strong> in stack.
  <strong>{D,E,B,C} -&gt; {K,E,B,C} -&gt; {M,E,B,C} -&gt; {O,E,B,C} -&gt; {F,G,E,B,C}.</strong>
  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 <strong>S -&gt; B -&gt; G</strong> or else <strong>S -&gt; A -&gt; D -&gt; K -&gt; M -&gt; O -&gt; G</strong>.</p>
  <p>How to decide what way to go?</p>
  
Tags: <search><path-finding><depth-first-search>
Title: How to find the order in which DFS algorithm will inspect the nodes?
UserDisplayName: astraltrinity
ThreadText: # How to find the order in which DFS algorithm will inspect the nodes?
  
  (Asked by: username_0 on 2022-05-26)
  
  [![enter image description here](https://i.sstatic.net/mwRYd.png)](https://i.sstatic.net/mwRYd.png)
  
  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?
  
  **Tags:** search, path-finding, depth-first-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-05-27. Score: 0 | Accepted answer
  
  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).
  
  > **Comments:**
  > **username_2**: You could mention [_graph search_](https://ai.stackexchange.com/a/9554/2444), which is the term that Norvig and Russell (and most AI people) use to refer to the general state-space search that keeps track of what has already been visited.  
  
  ---
  
  