DFSアルゴリズムについてのこの記事は正しいですか？

Question

何が問題なのですか？私はスタック4を変更しなければならないと思う[G P E]。

頂点Pを訪問すると頂点Gをスキップする方法はありますか？

私はないと思います。違いますか？

Answer 1

これは標準のDFSアルゴリズムの変形です。標準的なアルゴリズムでは、現在のノードの未訪問のネイバーをスタック上に置かず、ノード自体だけを1つのネイバーを訪問させます。その隣にDFSを実行した後、あなたは逆戻りし、だけその後他の子供を見てください。それらの中にまだ未訪問のものがある場合は、だけで、がスタックにプッシュされます。

しかし、この代わりに、すべての未訪問のネイバーがスタックに置かれ、トラバルを深くすることもできます。

あなたがスタックにノードを置くときは、ノードを後でスタックからポップされた場合でも、グラフトラバーサルの間に再び除去されることはありませんマーク、を重ねて、あなたもそれをマークする必要があります。そうすれば、トラバース全体でノードがスタックに2回以上置かれることはありません。ノード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

何が問題なのですか。

何もありません。

スタックNo.4を[G P E]に変更する必要があります。

いいえ、そうしてはいけません。スタックの上部には、トッピングされる要素が必要です。 'G'は深さ優先の探索の最後に現れなければならないので、スタックの最下部に置くことをお勧めします。

スタックの一番下にある要素が最後にポップされます。 スタックの先頭にある要素が最初にポップされます。