Javascript中的广度优先搜索遍历

BFS在访问子顶点之前先访问邻居顶点，并且在搜索过程中使用队列。以下是BFS的工作方式-

• 访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列。

• 如果找不到相邻的顶点，请从队列中删除第一个顶点。

• 重复规则1和规则2，直到队列为空。

让我们看一下BFS遍历如何工作的图示：

步	遍历	描述
1		初始化队列。
2		我们首先访问S（起始节点）并将其标记为已访问。
3		然后，我们看到一个来自S的未访问的相邻节点。在此示例中，我们有三个节点，但按字母顺序选择A，将其标记为已访问并排队。
4		接下来，S中未访问的相邻节点是B，我们将其标记为已访问并对其进行排队。
5		接下来，S中未访问的相邻节点是C，我们将其标记为已访问并将其排队。
6		现在，S不再有未访问的相邻节点。所以，我们出队，并找到 一个。
7		在 A中，我们将D 作为未访问的相邻节点。我们将其标记为已访问并入队。

在这一阶段，我们没有未标记（未访问）的节点。但是按照算法，我们继续进行出队以获取所有未访问的节点。清空队列后，程序结束。

让我们看一下如何在JavaScript中实现它。 

示例

BFS(node) {
   //创建一个队列并在其中添加我们的初始节点
   let q = new Queue(this.nodes.length);
   let explored = new Set();
   q.enqueue(node);

   //将第一个节点标记为已探索。
   add(node);

   //我们将继续直到队列变空
   while (!q.isEmpty()) {
      let t = q.dequeue();

      //记录从队列中出来的每个元素
      console.log(t);

      //1.在edges对象中，我们搜索该节点直接连接到的节点。
      //2.我们过滤掉已经探索过的节点。
      //3.然后，我们将每个未探索的节点标记为已探索，并将其添加到队列中。
      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