Answers.Body: <h1>Defining Path</h1>
  
  <p>You are right to be confused if your professors did not clarify (see warning at end). The term "path" can mean a few things:</p>
  
  <p><strong>"Concrete" Path</strong>:
  Recall, a graph is a collection of vertices and edges. A path on the graph is then:</p>
  
  <p><span class="math-container">$$v_1\xrightarrow{e_1} v_2\xrightarrow{e_2} \cdots \xrightarrow{e_{n-1}} v_n$$</span></p>
  
  <p>Where <span class="math-container">$v_i$</span> are vertices on the graph and the arrows denote the direction traversed over the undirected edges <span class="math-container">$e_j$</span>. Observe, this definition explicitly defines some "chain" of vertices connected by specific edges. </p>
  
  <p><strong>"Abstract" Path</strong>: Say there is some task that involves a serious of repeated <em>actions</em> but does not depend on specific objects. We can define this as a chain of composed functions:</p>
  
  <p><span class="math-container">$$f_n\circ\cdots \circ f_1$$</span></p>
  
  <p>The idea, is that this definition is little more abstract. Though, there are many other ways one could define "path."</p>
  
  <h1>"Solution Path"</h1>
  
  <p><strong>A Subtlety</strong></p>
  
  <blockquote>
    <p>So, in this case, is the solution path A -> B -> C, i.e. the order in which the nodes are visited? Or is the solution path A -> B -> A -> C? Basically saying that we go from A to B, but to go from B to C, we must go through A again.</p>
  </blockquote>
  
  <p>BFS does not "go through A again." Considering you are using a queue based implementation, once A has been visited there will be no need to "visit" it again. That is, we have added all nodes we need to the queue and marked A as being seen. This leads into:</p>
  
  <blockquote>
    <p>How to report the solution path of a search algorithm on a graph?</p>
  </blockquote>
  
  <p>Since, these algorithms do not revisit nodes, what is <strong>most likely</strong> being asked of you is for you to report the order of the visits - this is what my professors wanted in my AI &amp; Algorithms courses.</p>
  
  <p><strong>A Warning</strong>: I can only answer what <em>my professors</em> wanted. Please clarify this with your instructors. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-09T20:04:10.183Z
Answers.LastActivityDate: 2020-02-09T20:12:36.630Z
Answers.LastEditDate: 2020-02-09T20:12:36.630Z
Answers.UserDisplayName: respectful
Body: <p>I'm working on a problem where we are given a graph and asked to perform various search algorithms (BFS, DFS, UCS, A*, etc.) and the goal state is to visit all nodes in the graph. After all nodes are visited, we need to print out the "solution path." However, I am a bit confused on what "path" means in AI. </p>
  
  <p>For simplicity, let's just consider a graph of 3 nodes: A, B and C with 2 undirected edges (A, B) (A, C). If we perform BFS on this graph starting at node A and traversing alphabetically, we'd visit A, then B, then C.  So, in this case, is the solution path <code>A -&gt; B -&gt; C</code>, i.e. the order in which the nodes are visited? Or is the solution path <code>A -&gt; B -&gt; A -&gt; C</code>? Basically saying that we go from A to B, but to go from B to C, we must go through A again. </p>
  
Tags: <search><path-planning><path-finding>
Title: How to report the solution path of a search algorithm on a graph?
UserDisplayName: anonuser01
ThreadText: # How to report the solution path of a search algorithm on a graph?
  
  (Asked by: username_0 on 2020-02-08)
  
  I'm working on a problem where we are given a graph and asked to perform various search algorithms (BFS, DFS, UCS, A\*, etc.) and the goal state is to visit all nodes in the graph. After all nodes are visited, we need to print out the "solution path." However, I am a bit confused on what "path" means in AI.
  
  For simplicity, let's just consider a graph of 3 nodes: A, B and C with 2 undirected edges (A, B) (A, C). If we perform BFS on this graph starting at node A and traversing alphabetically, we'd visit A, then B, then C. So, in this case, is the solution path `A -> B -> C`, i.e. the order in which the nodes are visited? Or is the solution path `A -> B -> A -> C`? Basically saying that we go from A to B, but to go from B to C, we must go through A again.
  
  **Tags:** search, path-planning, path-finding
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-02-09. Score: 1
  
  # Defining Path
  
  You are right to be confused if your professors did not clarify (see warning at end). The term "path" can mean a few things:
  
  **"Concrete" Path**:
  Recall, a graph is a collection of vertices and edges. A path on the graph is then:
  
  $$v\_1\xrightarrow{e\_1} v\_2\xrightarrow{e\_2} \cdots \xrightarrow{e\_{n-1}} v\_n$$
  
  Where $v\_i$ are vertices on the graph and the arrows denote the direction traversed over the undirected edges $e\_j$. Observe, this definition explicitly defines some "chain" of vertices connected by specific edges.
  
  **"Abstract" Path**: Say there is some task that involves a serious of repeated *actions* but does not depend on specific objects. We can define this as a chain of composed functions:
  
  $$f\_n\circ\cdots \circ f\_1$$
  
  The idea, is that this definition is little more abstract. Though, there are many other ways one could define "path."
  
  # "Solution Path"
  
  **A Subtlety**
  
  > So, in this case, is the solution path A -> B -> C, i.e. the order in which the nodes are visited? Or is the solution path A -> B -> A -> C? Basically saying that we go from A to B, but to go from B to C, we must go through A again.
  
  BFS does not "go through A again." Considering you are using a queue based implementation, once A has been visited there will be no need to "visit" it again. That is, we have added all nodes we need to the queue and marked A as being seen. This leads into:
  
  > How to report the solution path of a search algorithm on a graph?
  
  Since, these algorithms do not revisit nodes, what is **most likely** being asked of you is for you to report the order of the visits - this is what my professors wanted in my AI & Algorithms courses.
  
  **A Warning**: I can only answer what *my professors* wanted. Please clarify this with your instructors.
  
  
  ---
  
  