Javascript 中的广度优先搜索遍历
web developmentfront end technologyjavascript
BFS 在访问子顶点之前先访问邻居顶点，搜索过程中使用队列。以下是 BFS 的工作原理 −
- 访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列。
- 如果未找到相邻顶点，则从队列中移除第一个顶点。
- 重复规则 1 和规则 2，直到队列为空。
让我们看一下 BFS 遍历的工作原理:
步骤 | 遍历 | 描述 |
|---|---|---|
1 |  | 初始化队列。 |
2 |  | 我们首先访问 S (起始节点)，并将其标记为已访问。 |
3 |  | 然后，我们从 S 中看到一个未访问的相邻节点。在此示例中，我们有三个节点，但按字母顺序我们选择 A，将其标记为已访问并将其入队。 |
4 |  | 接下来，来自 S的未访问相邻节点是 B。我们将其标记为已访问并将其入队。 |
5 |  | 接下来，来自 S的未访问相邻节点是 C。我们将其标记为已访问并将其入队。 |
6 |  | 现在，S 已没有未访问的相邻节点。因此，我们出队并查找 A。 |
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. 在边缘对象中，我们搜索此节点直接连接到的节点。
// 2. 我们过滤掉已经被探索过的节点。
// 3. 然后我们将每个未探索的节点标记为已探索并将其添加到队列中。
this.edges[t]
.filter(n => !explored.has(n))
.forEach(n => {
explored.add(n);
q.enqueue(n);
});
}
}
You can test this function using −
示例
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
