数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript中的广度优先搜索遍历
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) {
// 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
更新于: 2020年6月15日
4K+浏览量
广告