algorithm - 深度优先搜索 : Wrong Iterative DFS results order

Question

我正在尝试使用 DFS 算法对我的等距矩形进行排序。 递归 版本完美运行。
这是我的实现:

            if (node.discovered)
                return;

            node.discovered = true;

            for (var i:int = 0, length:int = node.behindNodes.length; i < length; i++)
            {
                var currentNode:IsoNode = node.behindNodes[i];

                if (!currentNode.discovered)
                {
                    visitNode(currentNode, container);
                }
            }

            container.addChild(node);

然而，随处发布的**迭代**算法(例如:https://en.wikipedia.org/wiki/Depth-first_search)给了我绝对错误的顺序。

这是我的实现:

    if (node.discovered)
        return;

    var stack:Vector.<IsoNode> = new <IsoNode>[node];

    while (stack.length)
    {
        var currentNode:IsoNode = stack.pop();

        if (currentNode.discovered)
            continue;

        currentNode.discovered = true;

        for (var i:int = 0, length:int = currentNode.behindNodes.length; i < length; i++)
        {
            var behindNode:IsoNode = currentNode.behindNodes[i];

            if (!behindNode.discovered)
            {
                stack.push(behindNode);
            }
        }

        container.addChild(currentNode);
    }

Seems like it's trying to place the parent node first instead of child atthe end of chain

为什么这个版本的算法会存在？感觉这是原始算法的半逆向版本。

我该如何解决？如何让它返回与递归版本相同的结果？因为乍一看我需要向这个版本提供完全形成的堆栈(而不是使用算法本身)，但这没有任何意义!

排序的想法是以正确的顺序获得等距节点 - 从最远到最近。每个节点都保存着后面节点的信息。

所以基本上我们有图表

node_1->()  
node_2->(node_3)  
node_3->(node_1)  

递归版本示例:
正确顺序:node_1 node_3 node_2

_{(来源:yiffa.net)}

迭代版本示例:
不正确顺序:node_1 node_2 node_3

_{(来源:yiffa.net)}

Answer 1

我不想让我的答案被接受，因为也许我对常见的迭代 DFS 的理解是错误的。

我猜，我自己想出了如何正确模拟该算法的堆栈。

这是我的代码:

if (node.discovered)
    return;

var currentNode:IsoNode = node;

currentNode.discovered = true;

var discoveredStack:Vector.<IsoNode> = new <IsoNode>[currentNode];

while (discoveredStack.length)
{
    currentNode = discoveredStack[discoveredStack.length - 1];

    while (currentNode.behindNodes.length)
    {
        var behindNode:IsoNode = currentNode.behindNodes.pop();

        if (!behindNode.discovered)
        {
            behindNode.discovered = true;
            discoveredStack.push(behindNode);
            currentNode = behindNode;
        }
    }

    container.addChild(discoveredStack.pop());
}

无论如何，对于我来说，算法是迭代的还是递归的并不重要。如果算法相同并且具有相同的输入，则它必须返回相同的结果。否则就是不同的算法。

如果有人能告诉我我是对还是错，那就太好了。