码海

# 广度优先搜索

比较次数: 0

已访问节点:

# 算法原理

广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的算法。它的基本思想是从一个顶点开始，先访问该顶点的所有相邻顶点，然后再按照访问的顺序依次访问这些相邻顶点的相邻顶点，直到访问完所有可达的顶点。

# 算法步骤

  1. 从起始顶点开始，将其加入队列并标记为已访问
  2. 当队列不为空时，重复以下步骤：
    • 从队列中取出一个顶点
    • 访问该顶点的所有未访问的相邻顶点
    • 将这些相邻顶点加入队列并标记为已访问
  3. 当队列为空时，算法结束

# 代码实现

// 使用队列实现BFS（邻接表表示）
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);
  
  while (queue.length > 0) {
    const vertex = queue.shift();
    console.log(vertex);  // 访问顶点
    
    // 访问所有未访问的相邻顶点
    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

// 在二叉树中使用BFS进行层次遍历
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function levelOrderTraversal(root) {
  if (root === null) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    
    // 处理当前层的所有节点
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      
      // 将下一层的节点加入队列
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(currentLevel);
  }
  
  return result;
}

# 复杂度分析

# 时间复杂度

  • O(V + E)，其中V是顶点数，E是边数
  • 对于树形结构：O(n)，其中n是节点数

# 空间复杂度

  • O(V)，需要visited集合和队列来存储顶点
  • 在最坏情况下，队列可能需要存储所有顶点

# 算法特点

# 优点

  • 可以找到最短路径
  • 适合搜索最近的节点
  • 不会陷入深层递归
  • 按层次访问节点

# 缺点

  • 空间复杂度较高
  • 不适合搜索深层次的节点
  • 对于图的搜索，可能需要大量内存

# 适用场景

  1. 寻找最短路径
  2. 层次遍历
  3. 网络爬虫
  4. 社交网络中的好友推荐
  5. 地图导航

# 实际应用

  1. 迷宫最短路径查找
  2. 网页爬虫的URL遍历
  3. 社交网络的好友关系分析
  4. GPS导航系统的路径规划

# 优化方案

  1. 双向BFS：从起点和终点同时开始搜索
  2. 启发式搜索：结合启发函数进行优化
  3. 多源BFS：从多个起点同时开始搜索
// 双向BFS示例（查找最短路径）
function bidirectionalBFS(graph, start, target) {
  if (start === target) return 0;
  
  const visitedFromStart = new Map([[start, 0]]);
  const visitedFromTarget = new Map([[target, 0]]);
  
  let queueFromStart = [start];
  let queueFromTarget = [target];
  
  while (queueFromStart.length > 0 && queueFromTarget.length > 0) {
    // 从起点扩展
    const vertex = queueFromStart.shift();
    const distance = visitedFromStart.get(vertex);
    
    for (const neighbor of graph[vertex]) {
      if (visitedFromTarget.has(neighbor)) {
        // 找到相交点，返回最短路径长度
        return distance + visitedFromTarget.get(neighbor);
      }
      
      if (!visitedFromStart.has(neighbor)) {
        visitedFromStart.set(neighbor, distance + 1);
        queueFromStart.push(neighbor);
      }
    }
    
    // 从终点扩展
    const vertexFromTarget = queueFromTarget.shift();
    const distanceFromTarget = visitedFromTarget.get(vertexFromTarget);
    
    for (const neighbor of graph[vertexFromTarget]) {
      if (visitedFromStart.has(neighbor)) {
        // 找到相交点，返回最短路径长度
        return distanceFromTarget + visitedFromStart.get(neighbor);
      }
      
      if (!visitedFromTarget.has(neighbor)) {
        visitedFromTarget.set(neighbor, distanceFromTarget + 1);
        queueFromTarget.push(neighbor);
      }
    }
  }
  
  return -1;  // 无法到达目标顶点
}

// 多源BFS示例（计算到多个源点的最短距离）
function multiSourceBFS(graph, sources) {
  const visited = new Map();
  const queue = [];
  
  // 初始化所有源点
  for (const source of sources) {
    visited.set(source, 0);
    queue.push(source);
  }
  
  while (queue.length > 0) {
    const vertex = queue.shift();
    const distance = visited.get(vertex);
    
    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.set(neighbor, distance + 1);
        queue.push(neighbor);
      }
    }
  }
  
  return visited;
}

← 深度优先搜索 →