我已经实现了一个简单的DFS(非递归),如果存在 StartNode 和 EndNode 之间的路径,则为'tests' . 它按预期工作(处理双向/方向图) - 但我无法弄清楚如何存储路径供以后使用 .
目前我正在调试打印访问节点,但它不是应该存储的内容 .
有人可以帮我解决一下 - 我究竟应该存储什么以及在什么时候返回从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
2 回答
如果我正确理解你的算法(它是一个DFS),
从起点开始,您将向第一个未访问节点的方向迈出一步 . 如果从该节点到目标没有路由,则退回并尝试转到下一个未访问的节点,同时仔细管理访问的节点 .
All you need to add is a stack 你总是按下你要迈出的节点,如果你不得不退后一步从堆栈中弹出它 . This stack will store your route 从start_node到目标 . 它还可以帮助您确定退回的位置 .
这是你的代码,最后它变得比我想象的更长,但现在它是:
而且现在你可以从开始到目标的方式
pop_back
或从目标开始的方式pop
. 如果路径为空,则对应于从原始函数返回false .Reference on unordered_set和stack,均为STL . 它是用一个桶实现的,所以它比set或map快得多,它通常用红黑树实现 .
备注:
std::unordered_set
是C 11扩展名,如果使用C 03,请随意用较慢的std::set
替换它 .好吧,而不是设置
visited
- 你可以有一个parent
Map ( Map :顶点 - >顶点) .遍历图形时修改 Map ,这样如果从节点
u
发现节点v
,则添加parent[v] = u
. Initparent[source] = NULL
.现在,您所要做的就是迭代(伪代码):
它将以相反的顺序为您提供路径 . 如果要实现路径的原始顺序,可以存储到堆栈(而不是print语句)并迭代堆栈 .
它与线程中为BFS解释的想法非常相似:How can I find the actual path found by BFS?