我编写了一个递归 DFS 算法来遍历图:
I have written a recursive DFS algorithm to traverse a graph:
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 算法:
Then I have written an iterative DFS algorithm using a stack:
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') 我的输出是:
My problem is that in a graph in which, for example, I enter the three nodes 'a', 'b', 'c' with arcs ('a', 'b') and ('a', 'c') my output is:
'a'、'b'、'c' 与递归 DFS 版本,以及:
'a', 'b', 'c' with the recursive DFS version, and:
'a', 'c', 'b' 与迭代 DFS 一.
'a', 'c', 'b' with the iterative DFS one.
我怎么能得到同样的订单?我做错了什么吗?
How could I get the same order? Am I doing something wrong?
谢谢!
两者都是有效的 DFS 算法.DFS 不会指定您首先看到哪个节点.这并不重要,因为边之间的顺序没有定义[记住:边通常是一个集合].不同之处在于您处理每个节点的子节点的方式.
Both are valid DFS algorithms. A DFS does not specify which node you see first. It is not important because the order between edges is not defined [remember: edges are a set usually]. The difference is due to the way you handle each node's children.
在迭代方法中:您首先将所有元素插入堆栈 - 然后处理堆栈的头部[这是插入的最后一个节点] - 因此您的第一个节点句柄是最后一个孩子.
In the iterative approach: You first insert all the elements into the stack - and then handle the head of the stack [which is the last node inserted] - thus the first node you handle is the last child.
在递归方法中:当您看到每个节点时,您就对其进行处理.因此,您处理的第一个节点是第一个子节点.
In the recursive approach: You handle each node when you see it. Thus the first node you handle is the first child.
为了使迭代 DFS 产生与递归相同的结果 - 您需要以相反的顺序向堆栈添加元素 [对于每个节点,首先插入其最后一个子节点,最后插入其第一个子节点]
To make the iterative DFS yield the same result as the recursive one - you need to add elements to the stack in reverse order [for each node, insert its last child first and its first child last]
这篇关于迭代 DFS 与递归 DFS 以及不同的元素顺序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!