3

我已经实现了一个简单的 DFS（非递归），它“测试” StartNode和EndNode之间的路径是否存在。它按预期工作（处理双向/定向图）-但我只是不知道如何存储路径以供以后使用。

目前我正在调试打印访问的节点，但这不是应该存储的内容。

有人可以帮我/解释一下 - 我到底应该存储什么以及在什么时候将节点列表从 NodeStart 返回到 NodeEnd ？

这是示例图表：

图形

这是DFS遍历函数：

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;
}

这是调试输出：

查找 Node1 和 Node3 之间的路径

<main> [] DFS TRAVERSE TEST (DIRECTIONAL)
<DFS> [] {VISITED} Node1
<DFS> [] {VISITED} Node4
<DFS> [] {VISITED} Node5
<main> [] Path from Node1 to Node3 - YES

查找 Node3 和 Node1 之间的路径

<main> [] DFS TRAVERSE TEST (DIRECTIONAL)
<main> [] Path from Node3 to Node1 - NO
4

2 回答 2

4

如果我正确理解了您的算法（并且它是 DFS），
那么您将从起点向第一个未访问节点的方向迈出一步。如果没有从该节点到您的目标的路线，则您退后一步并尝试转到下一个未访问的节点，同时仔细管理访问了哪些节点。

您需要添加的只是一个堆栈，您始终将要执行的节点推送到该堆栈，如果必须后退，则将其从堆栈中弹出。此堆栈将存储您从 start_node 到目标的路线。它还可以帮助您确定退后的位置。

这是您的代码，最后它比我想象的要长一些，但它是：

// 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;
}

现在，您可以pop_back按照自己的方式从开始到目标或pop从目标到开始。如果路由为空，则对应于从原始函数返回 false。

在 STL 中对 unordered_set和stack的引用。它是用一个桶实现的，所以它比通常用红黑树实现的 set 或 map 快得多。

备注：是一个 C++11 扩展，如果你使用 C++03 ，请std::unordered_set随意替换为较慢的。std::set

于 2012-12-09T13:52:32.363 回答
3

好吧，你可以有一个地图（地图：顶点->顶点） ，而不是一个visited 集合。parent

在遍历图表时修改地图，如果您v从 node发现 node u，请添加parent[v] = u。初始化parent[source] = NULL。

现在，您所要做的就是迭代（伪代码）：

current <- dest
while current != NULL:
   print current
   current <- parent[current]

它将以相反的顺序为您提供路径。如果要实现路径的原始顺序，您可以存储到堆栈（而不是 print 语句）并迭代堆栈。

这与线程中为 BFS 解释的想法非常相似：如何找到 BFS 找到的实际路径？

于 2012-12-09T13:50:47.277 回答