這篇文章是關於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'必須出現在深度優先遍歷的末尾，因此將它放在堆棧的底部是個不錯的主意。

位於堆棧底部的元素將最後彈出。 堆棧頂部的元素將首先彈出。