title: DFS Graph Recording Path (Pathfinding)
body: <p>i have implemented a simple DFS (non recursive) that 'tests' if a Path between <strong>StartNode</strong> and <strong>EndNode</strong> exists. It works as expected ( handling bidirectional/directional graphs ) - but i just can't figure out <em>how to store the Path</em> for later usage.</p>
  
  <p>Currently i am debug-printing Visited nodes, but it's not what is should be storing.</p>
  
  <p>Can somebody please help me out / shed a bit of light on - what exactly should i store and at what point to return a list of nodes from NodeStart to NodeEnd ?</p>
  
  <p>Here is the example Graph:</p>
  
  <p><img src="https://i.stack.imgur.com/hmBOz.jpg" alt="Graph"></p>
  
  <p>Here is the DFS traversing function:</p>
  
  <pre><code>bool DFS(CNavigationGraph *pNavGraph, CNavigationGraphNode* pFromNode, CNavigationGraphNode* pToNode)
  {
      assert(pNavGraph);
      assert(pFromNode);
      assert(pToNode);
  
      std::vector&lt;CNavigationGraphNode*&gt; vpVisitedNodes;
      std::vector&lt;CNavigationGraphNode*&gt; stack;
  
      stack.push_back(pFromNode);
  
      while(!stack.empty())
      {
          CNavigationGraphNode     *pTop = stack.back();
          stack.pop_back();
  
          // Ok We've reached pToNode - means, path pFromNode to pToNode available
          if(pTop == pToNode)
          {
              for(int a = 0; a &lt; vpVisitedNodes.size(); a++)
              {
                  CLogger::Instance()-&gt;Write(XLOGEVENT_LOCATION, "{VISITED} %s",vpVisitedNodes[a]-&gt;GetNodeName().data());
              }
              return true;
          }
  
          // Add to visited list
          vpVisitedNodes.push_back(pTop);
  
          // Look for adjacent Nodes for pTop
          std::vector&lt;CNavigationGraphNode*&gt; vpAdjacentNodes;
          pNavGraph-&gt;GetAdjacentNodes(pTop-&gt;GetNodeName(), vpAdjacentNodes);
          for(int x = 0; x &lt; vpAdjacentNodes.size(); x++)
          {
              // Add to stack if not visited
              if(IsVisited(vpVisitedNodes, vpAdjacentNodes[x]) == false)
                  stack.push_back(vpAdjacentNodes[x]);
          }
      }
  
      // Path not found
      return false;
  }
  </code></pre>
  
  <p>Here is the Debug Output:</p>
  
  <p>Find Path Between Node1 and Node3</p>
  
  <pre><code>&lt;main&gt; [] DFS TRAVERSE TEST (DIRECTIONAL)
  &lt;DFS&gt; [] {VISITED} Node1
  &lt;DFS&gt; [] {VISITED} Node4
  &lt;DFS&gt; [] {VISITED} Node5
  &lt;main&gt; [] Path from Node1 to Node3 - YES
  </code></pre>
  
  <p>Find Path Between Node3 and Node1</p>
  
  <pre><code>&lt;main&gt; [] DFS TRAVERSE TEST (DIRECTIONAL)
  &lt;main&gt; [] Path from Node3 to Node1 - NO
  </code></pre>