我编写了一个递归DFS算法来遍历图:
void Graph<E, N>::DFS(Node n)
{
std::cout << ReadNode(n) << " ";
MarkVisited(n);
NodeList adjnodes = Adjacent(n);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
Node adj = adjnodes.ReadList(pos);
if(!IsMarked(adj))
DFS(adj);
pos = adjnodes.NextPosition(pos);
}
}
然后我用堆栈编写了迭代DFS算法:
template <typename E, typename N>
void Graph<E, N>::IterativeDFS(Node n)
{
Stack<Node> stack;
stack.Push(n);
while(!stack.IsEmpty())
{
Node u = stack.Read();
stack.Pop();
if(!IsMarked(u))
{
std::cout << ReadNode(u) << " ";
MarkVisited(u);
NodeList adjnodes = Adjacent(u);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
stack.Push(adjnodes.ReadList(pos));
pos = adjnodes.NextPosition(pos);
}
}
}
我的问题是在一个图表中,例如,我输入三个节点'a','b','c'带有弧('a','b')和('a','c')我的输出是:
带有递归DFS版本的'a','b','c',以及:
带有迭代DFS的'a','c','b' .
我怎么能得到同样的订单?难道我做错了什么?
谢谢!
3 回答
Both are valid DFS算法 . DFS不会指定您首先看到的节点 . 这并不重要,因为边缘之间的顺序没有定义[记住:边缘通常是一组] . 不同之处在于您处理每个节点的子节点的方式 .
在 iterative approach: You first insert all the elements 进入堆栈 - 然后处理堆栈的头部[这是插入的最后一个节点] - 因此 first node you handle is the last child .
在 recursive approach 中:您在看到它时处理每个节点 . 因此 first node you handle is the first child .
要使迭代DFS产生与递归DFS相同的结果 - 您需要 add elements to the stack in reverse order [对于每个节点,首先插入其最后一个子节点并将其最后一个子节点插入]
在这里,我以递归的方式离开我的解决方案,非常快速地实现 . 只需要针对需要使用此算法的任何问题进行调整 .
将当前状态标记为已访问,定义为
ok[u] = true
非常重要,即使拥有所有状态,因为它们尚未使用memset(ok, 0, sizeof ok)
进行访问下面是C#for Adjacency Matrix中的示例代码(根据上面的@amit回答) .