DFS Graph Recording Path (Pathfinding)

c++, graph, path-finding

Solution

If I understand your algorithm correctly (and it is a DFS), from the starting point you are taking a step to the direction of the first non-visited node. If there is no route to your target from that node, you step back and try to go to the next non-visited node, in the mean time carefully administrating which nodes were visited.

All you need to add is a stack to which you always push the node you are taking a step to, and pop it from the stack if you had to step back. This stack will store your route from the start_node to the target. It also helps you to determine where to step back.

Here is your code, finally it grew a bit lengthier than I've thought but here it is:

// I call fromNode: start_node, toNode: target_node.

std::stack<CNavigationGraphNode*> DFS(CNavigationGraph *pNavGraph, CNavigationGraphNode* start_node, CNavigationGraphNode* target_node)
{
    using namespace std;

    stack<CNavigationGraphNode*> route; // route to target
    unordered_set<CNavigationGraphNode*> visited_nodes;  // hash set on who is visited
    vector<CNavigationGraphNode*> adjacent_nodes;

    CNavigationGraphNode* current_node = start_node;
    while(current_node!=target_node)
    {
      pNavGraph->GetAdjacentNodes(current_node->GetNodeName(), adjacent_nodes); 

      // "for each"; you can use any form of looping through the neighbors of current_node.
      bool found_non_visited = false;
      for(auto node : adjacent_nodes) 
      {
        if(visited_nodes.find(node) == visited_nodes.end())
        {
          route.push(current_node);
          visited_nodes.insert(node);
          current_node = node;
          found_non_visited = true;
          break;
        }
      }
      if(found_non_visited) 
        continue;

      if(route.empty())
        return route; // empty route means no route found
      current_node = route.pop();
    }
    route.push(target);
    return route;
}

And now you can `pop_back` your way from start to target or `pop` your way from target to start. If the route is empty, that corresponds to returning false from your original function.

Reference on unordered_set and stack, both in STL. It is implemented with a bucket has so it is much faster than set or map, which are usually implemented with red-black trees.

Remark: `std::unordered_set` is a C++11 extension, feel free to replace it with the slower `std::set` if you use C++03.

Problem

i have implemented a simple DFS (non recursive) that 'tests' if a Path between StartNode and EndNode exists. It works as expected ( handling bidirectional/directional graphs ) - but i just can't figure out how to store the Path for later usage. Currently i am debug-printing Visited nodes, but it's not what is should be storing. 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 ? Here is the example Graph: Here is the DFS traversing function: ``` bool DFS(CNavigationGraph *pNavGraph, CNavigationGraphNode* pFromNode, CNavigationGraphNode* pToNode) { assert(pNavGraph); assert(pFromNode); assert(pToNode); std::vector<CNavigationGraphNode*> vpVisitedNodes; std::vector<CNavigationGraphNode*> 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 < vpVisitedNodes.size(); a++) { CLogger::Instance()->Write(XLOGEVENT_LOCATION, "{VISITED} %s",vpVisitedNodes[a]->GetNodeName().data()); } return true; } // Add to visited list vpVisitedNodes.push_back(pTop); // Look for adjacent Nodes for pTop std::vector<CNavigationGraphNode*> vpAdjacentNodes; pNavGraph->GetAdjacentNodes(pTop->GetNodeName(), vpAdjacentNodes); for(int x = 0; x < 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; } ``` Here is the Debug Output: Find Path Between Node1 and Node3 ``` <main> [] DFS TRAVERSE TEST (DIRECTIONAL) <DFS> [] {VISITED} Node1 <DFS> [] {VISITED} Node4 <DFS> [] {VISITED} Node5 <main> [] Path from Node1 to Node3 - YES ``` Find Path Between Node3 and Node1 ``` <main> [] DFS TRAVERSE TEST (DIRECTIONAL) <main> [] Path from Node3 to Node1 - NO ```

Original source

Related problems