Javascriptでの深さ優先探索トラバーサル

DFSは、兄弟の頂点にアクセスする前に、子の頂点にアクセスします。つまり、その幅を調べる前に、特定のパスの深さを横断します。スタック（多くの場合、再帰によるプログラムの呼び出しスタック）は、アルゴリズムを実装するときに一般的に使用されます。

以下はDFSの仕組みです-

• 隣接する未訪問の頂点にアクセスします。訪問済みとしてマークします。表示します。スタックにプッシュします。
• 隣接する頂点が見つからない場合は、スタックから頂点をポップアップします。 （隣接する頂点がないスタックからすべての頂点がポップアップ表示されます。）
• スタックが空になるまで、ルール1とルール2を繰り返します。

DFSトラバーサルがどのように機能するかを示す図を見てみましょう。

ステップ	トラバーサル	説明
1		スタックを初期化します。
2		マークS 訪問したとおりにスタックに置きます。 Sから未訪問の隣接ノードを探索します 。 3つのノードがあり、それらのいずれかを選択できます。この例では、ノードをアルファベット順に取り上げます。
3		マークA 訪問したとおりにスタックに置きます。 Aから未訪問の隣接ノードを探索します 。両方のS およびD Aに隣接していますが、未訪問のノードのみを対象としています。
4		Dにアクセス 訪問済みとしてマークし、スタックに置きます。ここにBがあります およびC Dに隣接するノード そして両方とも訪問されていません。ただし、ここでもアルファベット順に選択します。
5		B、を選択します 訪問済みとしてマークし、スタックに置きます。ここでB 未訪問の隣接ノードはありません。そこで、 Bをポップします スタックから。
6		スタックトップが前のノードに戻っているかどうかを確認し、未訪問のノードがあるかどうかを確認します。ここに、 Dがあります スタックの一番上になります。
7		未訪問の隣接ノードのみがDからのものです C 今。そこで、 Cにアクセスします 訪問済みとしてマークし、スタックに置きます。

Cとして 未訪問の隣接ノードがないため、未訪問の隣接ノードがあるノードが見つかるまでスタックをポップし続けます。この場合、何も存在せず、スタックが空になるまでポップし続けます。これをJavaScriptで実装する方法を見てみましょう。

例

DFS(node) {
   // Create a Stack and add our initial node in it
   let s = new Stack(this.nodes.length);
   let explored = new Set();
   s.push(node);

   // Mark the first node as explored
   explored.add(node);

   // We'll continue till our Stack gets empty
   while (!s.isEmpty()) {
      let t = s.pop();

   // Log every element that comes out of the Stack
      console.log(t);

   // 1. In the edges object, we search for nodes this node is directly connected to.
   // 2. We filter out the nodes that have already been explored.
   // 3. Then we mark each unexplored node as explored and push it to the Stack.
   this.edges[t]
   .filter(n => !explored.has(n))
   .forEach(n => {
      explored.add(n);
      s.push(n);
      });
   }
}

まあ、それは簡単でした。キューをスタックと出来上がりに交換しただけです。DFSがあります。これが2.の唯一の違いです。DFSは再帰を使用して実装することもできます。ただし、この場合、グラフが大きくなると、呼び出しスタックを追跡するためだけに追加のメモリが必要になるため、これは避けるのが最善です。

-

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");

g.DFS("A");

出力

これにより、出力が得られます。

A
D
E
F
B
G
C