迭代DFS与递归DFS以及不同元素的顺序

  • Z时代
  • 2024-01-10
  • 分类：问答

我编写了一个递归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’）和（’a’，’c’）输入三个节点’a’，’b’，’c’我的输出是：

递归DFS版本的’a’，’b’，’c’，以及：

带有迭代DFS的“ a”，“ c”，“ b”。

我怎样才能得到相同的订单？难道我做错了什么？

谢谢！

回答：

DFS算法。DFS没有指定您首先看到的节点。这并不重要，因为未定义边之间的顺序[请记住：边通常是一组]。差异是由于您处理每个节点的子代的方式。

在 插入堆栈中，然后处理堆栈的头（即插入的最后一个节点），因此 的 。

在 ：您可以在看到每个节点时对其进行处理。因此， 的 。

为了使迭代DFS产生与递归DFS相同的结果-您需要以

（对于每个节点，首先插入其最后一个子节点，最后插入其第一个子节点）

以上是 迭代DFS与递归DFS以及不同元素的顺序 的全部内容， 来源链接： utcz.com/qa/417276.html

回到顶部