algorithm - 这篇关于DFS算法的帖子对吗？

Question

怎么了？我认为 4 号堆栈必须更改 [G P E]。

有什么方法可以在我访问顶点 P 时跳过顶点 G？

我觉得没有办法。有错吗？

Answer 1

这是标准 DFS 算法的变体。在标准算法中，您不会将当前节点的未访问邻居全部放在堆栈上，而只是节点本身，然后访问一个邻居。在对那个邻居执行 DFS 后，您会回溯，然后才查看其他 child 。如果其中还有一个未访问的，只有这样它才会被压入堆栈。

但是这种替代方案——在深化遍历之前将所有未访问的邻居放入堆栈——也可以正常工作。

当你将一个节点放入栈中时，你还应该将其标记为stacked，这个标记在图遍历过程中永远不会再次被移除，即使该节点稍后从栈中弹出.这样你就可以确保在整个遍历过程中，一个节点永远不会被多次放入堆栈。

当到达节点 P 时，P 的所有邻居(即 G 和 H)之前已经堆叠(H 已从中拉出，G 仍在其上)。由于 P 没有其他邻居，该 DFS 算法从堆栈中拉出下一个节点(即 E)继续遍历。

这是一个 JavaScript 实现:

class Node {
    constructor(name) {
        this.name = name;
        this.neighbors = [];
    }
    link(node) { // link nodes in both directions
        this.neighbors.push(node);
        node.neighbors.push(this);
    }
    toString() { // The string representation of the node is its name
        return this.name;
    }
    dfs() { // Main algorithm
        const stack = [this], // Start with this node on the stack
            stacked = new Set(stack); // ...and mark it as stacked

        while (stack.length > 0) { // While the stack is not empty...
            console.log('stack: ' + stack);
            const node = stack.pop(); // Pull next node from the top of the stack
            for (const neighbor of node.neighbors) {
                // Only push neighbors on the stack
                // that were never stacked before:
                if (!stacked.has(neighbor)) {
                    stack.push(neighbor); // Push on the stack,
                    stacked.add(neighbor); // ... and mark as stacked
                }
            }
        }
    }
}

// Define nodes:
const a = new Node('A'),
      e = new Node('E'),
      g = new Node('G'),
      h = new Node('H'),
      j = new Node('J'),
      m = new Node('M'),
      p = new Node('P'),
      x = new Node('X'),
      y = new Node('Y');

// Define the links between the nodes
a.link(x);
x.link(g);
x.link(h);
g.link(h);
g.link(p);
h.link(e);
h.link(p);
e.link(m);
e.link(y);
y.link(m);
m.link(j);

// Visit the nodes of the graph, starting at A
a.dfs();

.as-console-wrapper { max-height: 100% !important; top: 0; }

请注意，如果一个图是一棵树，那么沿着树向下的 DFS 遍历永远不会遇到之前已经访问过的节点，因此在这种情况下不需要这样的标记。但是你的图是一个无向循环图，所以需要这个额外的标记。