js构造类广度优先搜索

基础概念

广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，逐层遍历每个节点的所有邻居节点，直到找到目标节点或遍历完所有可达节点。

优势

简单直观：BFS的实现相对简单，易于理解和编写。
最短路径：在无权图中，BFS可以找到从起点到终点的最短路径。
适用性广：适用于各种图结构，包括树、有向图和无向图。

类型

非递归实现：通常使用队列来实现。
递归实现：较少见，但也可以通过递归实现。

应用场景

社交网络分析：查找两个用户之间的最短联系链。
路径规划：如地图导航中的最短路径计算。
连通性检测：判断图中是否存在环或连通分量。

示例代码

以下是一个使用JavaScript实现的广度优先搜索的示例，假设我们有一个简单的图结构：

class Graph {
  constructor() {
    this.nodes = new Set();
    this.edges = {};
  }

  addNode(node) {
    this.nodes.add(node);
    this.edges[node] = [];
  }

  addEdge(node1, node2) {
    this.edges[node1].push(node2);
    this.edges[node2].push(node1);
  }

  bfs(startNode, targetNode) {
    const queue = [startNode];
    const visited = new Set();
    visited.add(startNode);

    while (queue.length > 0) {
      const currentNode = queue.shift();

      if (currentNode === targetNode) {
        return true; // 找到目标节点
      }

      for (const neighbor of this.edges[currentNode]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    return false; // 未找到目标节点
  }
}

// 示例用法
const graph = new Graph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addNode('D');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');

console.log(graph.bfs('A', 'D')); // 输出: true
console.log(graph.bfs('A', 'E')); // 输出: false