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

BFSは、子頂点にアクセスする前に隣接頂点にアクセスし、検索プロセスでキューが使用されます。 BFSの仕組みは次のとおりです-

• 隣接する未訪問の頂点にアクセスします。訪問済みとしてマークします。表示します。キューに挿入します。
• 隣接する頂点が見つからない場合は、最初の頂点をキューから削除します。
• キューが空になるまでルール1とルール2を繰り返します。

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

ステップ	トラバーサル	説明
1		キューを初期化します。
2		まずSにアクセスします （開始ノード）そしてそれを訪問済みとしてマークします。
3		次に、Sからの未訪問の隣接ノードが表示されます。 この例では、3つのノードがありますが、アルファベット順に A、を選択します。 訪問済みとしてマークし、キューに入れます。
4		次に、 Sからの未訪問の隣接ノード はB 。訪問済みとしてマークし、キューに入れます。
5		次に、 Sからの未訪問の隣接ノード はC 。訪問済みとしてマークし、キューに入れます。
6		さて、 S 未訪問の隣接ノードはありません。したがって、デキューして Aを見つけます 。
7		から A D 未訪問の隣接ノードとして。訪問済みとしてマークし、キューに入れます。

この段階では、マークされていない（訪問されていない）ノードはありません。しかし、アルゴリズムに従って、すべての未訪問ノードを取得するためにデキューを続けます。キューが空になると、プログラムは終了します。

これをJavaScriptで実装する方法を見てみましょう。

例

BFS(node) {
   // Create a Queue and add our initial node in it
   let q = new Queue(this.nodes.length);
   let explored = new Set();
   q.enqueue(node);

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

   // We'll continue till our queue gets empty
   while (!q.isEmpty()) {
      let t = q.dequeue();

      // Log every element that comes out of the Queue
      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 add it to the queue.
      this.edges[t]
      .filter(n => !explored.has(n))
      .forEach(n => {
         explored.add(n);
         q.enqueue(n);
      });
   }
}

この関数は、-

例

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.BFS("A");

出力

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

A
C
B
D
G
E
F