【前端】自学基础算法 -- 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) {
  // 如果当前层节点为空，返回false
  if (nodes == null || nodes.length == 0) return false
  let nextNodes = [] // 存储下一层的节点
  for (let i = 0; i < nodes.length; i++) {
    // 如果节点已经访问过，跳过
    if (path.indexOf(nodes[i]) > -1) continue
    // 将节点加入已访问路径
    path.push(nodes[i])
    // 如果找到目标值，返回true
    if (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', []))