我已经实现了一个简单的 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;
}
这是调试输出:
找到节点1和节点3之间的路径
<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
最佳答案
如果我正确理解你的算法(并且它是 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。
Reference on unordered_set和 stack , 都在 STL 中。它是用桶 has 实现的,因此比通常用红黑树实现的 set 或 map 快得多。
备注:std::unordered_set
是 C++11 扩展,如果您使用 C++03,请随意将其替换为较慢的 std::set
.
关于c++ - DFS图记录路径(Pathfinding),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13787877/