Answers.Body: <p>States are represented by nodes in the graph. In other words, a state is a node in the graph. So, I don't think there's any difference, but some authors maybe make a difference (e.g. because you don't need to store all information associated with some state while searching).</p>
  <p>BFS explores by level (hence the name <em>breadth</em>, in contrast to <em>depth-first search</em>, which goes deep and then backtracks), in the sense that it will first explore all nodes that are <span class="math-container">$w$</span> away from the start node before exploring all nodes that are <span class="math-container">$w + 1$</span> way, if you think of the edges of the (unweighted) graph as having a weight of 1, which you can do.</p>
  <p>BFS indeed needs to store a frontier in memory, which is a FIFO data structure (i.e. you first remove from the frontier the oldest node there in constant time) of nodes we can explore next.</p>
  <p>If you use BFS to find some path, you need some way to compute or keep track of it. If you apply BFS, you can generate a tree, where each node has a parent, which can be used to retrieve the path, i.e. you just backtrack from the goal.</p>
  <p>Note that graphs can have cycles and you can get to a node in different ways. So, you also need to mark a node as explored in some way, which may be with some variable you associate with the state/node (CLRS approach) or with an explored set (AIMA approach), which may thus contain all nodes, which makes BFS an instance of graph search (see also <a href="https://ai.stackexchange.com/a/9554/2444">this</a>).</p>
  <p>The running time also depends on how you represent the graph (e.g. adjacency list and adjacency matrix) or how you analyse the algorithm. See also the CLRS book for a different perspective on this topic.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-16T03:03:42.017Z
Answers.LastActivityDate: 2024-01-16T03:16:37.340Z
Answers.LastEditDate: 2024-01-16T03:16:37.340Z
Answers.UserDisplayName: nbro
Body: <p>I am reading <em>Artificial Intelligence: A Modern Approach</em> by Russel &amp; Norvig. As I understood it, a breadth-first graph search stores explored <strong>states</strong> instead of explored <strong>nodes</strong> (where &quot;nodes&quot; are the <em>actual</em> nodes generated by the search algorithm i.e. the &quot;nodes&quot; contain the state). However on pg. 82 the book states</p>
  <blockquote>
  <p>&quot;For breadth-first graph search in particular, every node generated remains in memory.&quot;</p>
  </blockquote>
  <p>But, by my understanding the only nodes we store in memory are the nodes in the frontier(as defined in the book). Instead it is the unique states that have been generated that we must store. Note that this is not a trivial difference since there are problems which can have finite states but infinite nodes.</p>
  
Tags: <search><norvig-russell><breadth-first-search>
Title: Does Breadth-First Graph Search need to store all all unique generated states?
UserDisplayName: ddk
ThreadText: # Does Breadth-First Graph Search need to store all all unique generated states?
  
  (Asked by: username_0 on 2024-01-15)
  
  I am reading *Artificial Intelligence: A Modern Approach* by Russel & Norvig. As I understood it, a breadth-first graph search stores explored **states** instead of explored **nodes** (where "nodes" are the *actual* nodes generated by the search algorithm i.e. the "nodes" contain the state). However on pg. 82 the book states
  
  > "For breadth-first graph search in particular, every node generated remains in memory."
  
  But, by my understanding the only nodes we store in memory are the nodes in the frontier(as defined in the book). Instead it is the unique states that have been generated that we must store. Note that this is not a trivial difference since there are problems which can have finite states but infinite nodes.
  
  **Tags:** search, norvig-russell, breadth-first-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-01-16. Score: 1
  
  States are represented by nodes in the graph. In other words, a state is a node in the graph. So, I don't think there's any difference, but some authors maybe make a difference (e.g. because you don't need to store all information associated with some state while searching).
  
  BFS explores by level (hence the name *breadth*, in contrast to *depth-first search*, which goes deep and then backtracks), in the sense that it will first explore all nodes that are $w$ away from the start node before exploring all nodes that are $w + 1$ way, if you think of the edges of the (unweighted) graph as having a weight of 1, which you can do.
  
  BFS indeed needs to store a frontier in memory, which is a FIFO data structure (i.e. you first remove from the frontier the oldest node there in constant time) of nodes we can explore next.
  
  If you use BFS to find some path, you need some way to compute or keep track of it. If you apply BFS, you can generate a tree, where each node has a parent, which can be used to retrieve the path, i.e. you just backtrack from the goal.
  
  Note that graphs can have cycles and you can get to a node in different ways. So, you also need to mark a node as explored in some way, which may be with some variable you associate with the state/node (CLRS approach) or with an explored set (AIMA approach), which may thus contain all nodes, which makes BFS an instance of graph search (see also [this](https://ai.stackexchange.com/a/9554/2444)).
  
  The running time also depends on how you represent the graph (e.g. adjacency list and adjacency matrix) or how you analyse the algorithm. See also the CLRS book for a different perspective on this topic.
  
  
  ---
  
  