Answers.Body: <p>If you have looked through an entire branch, you only need to mark off the top node for that branch.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-12T10:20:40.047Z
Answers.Text: Thanks for your contribution! Would you be able to elaborate your answer a bit more? Without further explanation, I'm afraid that your answer wouldn't really help to clarify things for anyone who would ask the question in the first place.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-12T16:49:22.697Z
Answers.Text: But notice that the algorithm proposed in the book stores all the explored nodes, in order to avoid visiting them again. And notice that although my example is in a tree, we are interested in searching on graphs.
Answers.UserDisplayName: Zaratruta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-13T12:07:39.270Z
Answers.Text: To visit a node again, you have to visit the node's parent. If you're at the node's parent, you do need to mark off the node. But if not, you only need to mark off the parent. You can continue upwards: if you're not at the grandparent, you only have to mark off the grandparent. You end up only needing to mark off nodes adjacent to your path, which is $O(bm)$ in space. This works for any graph.
Answers.UserDisplayName: programjames
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-15T02:58:50.680Z
Answers.Text: @programjames
  This is not true if we are searching in a graph. In a graph, a given node can be a successor of several different nodes. I have included a novel image to represent the searching process on a graph.
  
  But, it is important to notice that the algorithm presented in the book that I have cited says explicitly that we need to store all the explored nodes.
Answers.UserDisplayName: Zaratruta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-15T13:48:19.603Z
Answers.Text: But you still only need to mark off a boundary, not every node in the area.
Answers.UserDisplayName: programjames
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-15T16:22:58.603Z
Answers.Text: But how can we avoid expanding again an already explored node without tracking (and storing in memory) the nodes that were already explored? We don't know in advance what are the nodes that were already explored and will be visited again. This is not clear for me.
  
  But, as I was said, the book says that the explored nodes are stored. So, let us assume that we really need to store them. In this case, my reasoning is ok?
Answers.UserDisplayName: Zaratruta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-12T01:48:44.480Z
Answers.LastActivityDate: 2024-01-12T01:48:44.480Z
Answers.UserDisplayName: programjames
Body: <p>In &quot;Artificial Intelligence: A Modern Approach&quot;, the authors say that the space complexity of depth-first search is proportional to O(bm), considering b as the branching factor and m the maximum depth of the graph. But it is not obvious why, for me.</p>
  <p>The algorithm for searching graphs involves storing the explored nodes in the explored set, and the nodes open, but not explored yet, are stored in the border set.</p>
  <p>Let us consider the following graph, with the start node in green and the end node (the goal) in red.
  <a href="https://i.sstatic.net/U9cZu.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/U9cZu.png" alt="enter image description here" /></a></p>
  <p>The solution is given by the red path.</p>
  <p>But, in my perspective, in this scenario, in the worst case, the algorithm would try every path from the root to each leaf, and store all the nodes in the explored set.</p>
  <p>Thus, if we consider this, the space complexity is, at least, proportional to <span class="math-container">$O(b^m)$</span>.</p>
  <p>Is there something wrong with this reasoning?</p>
  <p>I'm including another image to represent better the searching process on a graph.
  <a href="https://i.sstatic.net/1GrHs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1GrHs.png" alt="enter image description here" /></a></p>
  <p>Best regards.</p>
  
Tags: <state-spaces><computational-complexity><depth-first-search><space-complexity><uninformed-search>
Title: Why the space complexity of depth-first search is O(bm)?
UserDisplayName: Zaratruta
ThreadText: # Why the space complexity of depth-first search is O(bm)?
  
  (Asked by: username_0 on 2024-01-12)
  
  In "Artificial Intelligence: A Modern Approach", the authors say that the space complexity of depth-first search is proportional to O(bm), considering b as the branching factor and m the maximum depth of the graph. But it is not obvious why, for me.
  
  The algorithm for searching graphs involves storing the explored nodes in the explored set, and the nodes open, but not explored yet, are stored in the border set.
  
  Let us consider the following graph, with the start node in green and the end node (the goal) in red.
  [![enter image description here](https://i.sstatic.net/U9cZu.png)](https://i.sstatic.net/U9cZu.png)
  
  The solution is given by the red path.
  
  But, in my perspective, in this scenario, in the worst case, the algorithm would try every path from the root to each leaf, and store all the nodes in the explored set.
  
  Thus, if we consider this, the space complexity is, at least, proportional to $O(b^m)$.
  
  Is there something wrong with this reasoning?
  
  I'm including another image to represent better the searching process on a graph.
  [![enter image description here](https://i.sstatic.net/1GrHs.png)](https://i.sstatic.net/1GrHs.png)
  
  Best regards.
  
  **Tags:** state-spaces, computational-complexity, depth-first-search, space-complexity, uninformed-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-01-12. Score: 0
  
  If you have looked through an entire branch, you only need to mark off the top node for that branch.
  
  > **Comments:**
  > **username_2**: Thanks for your contribution! Would you be able to elaborate your answer a bit more? Without further explanation, I'm afraid that your answer wouldn't really help to clarify things for anyone who would ask the question in the first place.  
  > **username_0**: But notice that the algorithm proposed in the book stores all the explored nodes, in order to avoid visiting them again. And notice that although my example is in a tree, we are interested in searching on graphs.  
  > **username_1**: To visit a node again, you have to visit the node's parent. If you're at the node's parent, you do need to mark off the node. But if not, you only need to mark off the parent. You can continue upwards: if you're not at the grandparent, you only have to mark off the grandparent. You end up only needing to mark off nodes adjacent to your path, which is $O(bm)$ in space. This works for any graph.  
  > **username_0**: @programjames This is not true if we are searching in a graph. In a graph, a given node can be a successor of several different nodes. I have included a novel image to represent the searching process on a graph.  But, it is important to notice that the algorithm presented in the book that I have cited says explicitly that we need to store all the explored nodes.  
  > **username_1**: But you still only need to mark off a boundary, not every node in the area.  
  > **username_0**: But how can we avoid expanding again an already explored node without tracking (and storing in memory) the nodes that were already explored? We don't know in advance what are the nodes that were already explored and will be visited again. This is not clear for me.  But, as I was said, the book says that the explored nodes are stored. So, let us assume that we really need to store them. In this case, my reasoning is ok?  
  
  ---
  
  