这篇文章是关于DFS算法的吗？

Question

怎么回事？我认为堆栈4号必须改变[G P E]。

当我访问顶点P时，有什么办法可以跳过顶点G吗？

我认为没有办法。这是错的吗？

Answer 1

这是标准DFS算法的变体。在标准算法中，您不会将当前节点的未访问邻居都放在堆栈上，而只放在节点本身上，然后访问一个邻居。在该邻居上执行了DFS后，您会回溯并，然后查看其他孩子。如果其中还有一个未被访问的人，那么只有它被推入堆栈。

但是，这种替代方案 - 所有未访问过的邻居都在深入旅行之前放在栈上 - 也可以很好地工作。

当你把一个节点放在堆栈上时，你也应该把它标记为堆栈，这个标记在图遍历期间不会再被移除，即使节点稍后从堆栈中弹出。通过这种方式，您可以确保在整个遍历期间节点不会多次放入堆栈。

当到达节点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遍历这树永远不能遇到一个已经访问过的一个节点，所以在这种情况下不需要这种标记。但是你的图是一个无向循环图，所以需要额外的标记。

Answer 2

怎么回事？

什么都没有。

我觉得堆栈4号必须改变[G P E]。

不，不应该。你希望堆栈顶部有要被顶层的元素。 'G'必须出现在深度优先遍历的末尾，因此将它放在堆栈的底部是个不错的主意。

位于堆栈底部的元素将最后弹出。 堆栈顶部的元素将首先弹出。