【前端】自学基础算法 -- 21.图的广度优先搜索

图的广度优先搜索

简介

图的广度优先搜索，沿着图的宽度遍历图的节点，先访问离起始节点最近的节点，然后逐渐向外扩展。

基本步骤：

1. 选择一个起始节点作为当前节点。
2. 将当前节点加入队列。
3. 当队列不为空时，重复以下步骤：
   a. 从队列中取出一个节点，作为当前节点。
   b.标记当前节点为已访问。
   c. 对于当前节点的每一个未被访问的相邻节点，将其加入队列。
4. 重复步骤 3，直到找到目标节点或遍历完整个图。

实现方法

/*** 图的广度优先搜索*/class Node {constructor(value) {this.value = value // 节点的值this.neighbors = [] // 相邻节点的列表}
}// 创建节点
let a = new Node('a')
let b = new Node('b')
let c = new Node('c')
let d = new Node('d')
let e = new Node('e')// 设置节点a的邻居
a.neighbors = [b, c]
// 设置节点b的邻居
b.neighbors = [a, c, d]
// 设置节点c的邻居
c.neighbors = [a, b, d]
// 设置节点d的邻居
d.neighbors = [b, c, e]
// 设置节点e的邻居
e.neighbors = [d]/*** 深度优先搜索* @param {Node} nodes - 当前层节点数组* @param {any} target - 目标值* @param {Node[]} path - 已经访问过的节点路径* @returns {boolean} - 是否找到目标值*/
function bfs(nodes, target, path) {// 如果当前层节点为空，返回falseif (nodes == null || nodes.length == 0) return falselet nextNodes = [] // 存储下一层的节点for (let i = 0; i < nodes.length; i++) {// 如果节点已经访问过，跳过if (path.indexOf(nodes[i]) > -1) continue// 将节点加入已访问路径path.push(nodes[i])// 如果找到目标值，返回trueif (nodes[i].value === target) return true// 将相邻节点加入下一层节点列表else nextNodes = nextNodes.concat(nodes[i].neighbors)}// 递归搜索下一层节点return bfs(nextNodes, target, path)
}// 调用bfs函数，从节点b开始搜索，目标值为'ax'
console.log(bfs([b], 'b', []))