Skip to content

图的广度优先搜索

· 3 min

同样，就是对图进行广度优先遍历。

广度优先遍历，用一句话来概括其核心思路，那就是 层层扩散。这里我们还是先以一个有向图为例：

image-20250312133737628

首先我们选择 V1 作为起始顶点，那么：

第一层：V1
第二层：V2 V4
第三层：V5 V3

当 V1 作为顶点时，它的下一层就是 V2 和 V4 这两个顶点，然后取 V2 找它的下一层，就是 V5，取 V4 找它的下一层就是 V3。注意在寻找下一层顶点的时候，要按照上一层顶点的顺序来找。例如，在第二层的时候，V2 在 V4 前面，因此在开始第三层的时候，先找 V2 的下一层顶点，然后再找 V4 的下一层顶点。最终，按照广度优先遍历出来的顺序为：V1 → V2 → V4 → V5 → V3

另外，广度优先遍历的顺序，同样不是唯一的。例如在上面的例子中，第二层我们把 V4 放在前面，V2 放在后面，导致第三层也会受到影响。倘若第二层将 V4 放在 V2 前面，那么遍历出来的顺序就是 V1 → V4 → V2 → V3 → V5。

对于一个无向图，广度优先遍历的思路也是一样的。例如下面的无向图：

image-20250312134803244

其遍历的路径有（括号表示层数）：

(V1) → (V2 → V4) → (V3 → V5)
(V1) → (V2 → V4) → (V5 → V3)
(V1) → (V4 → V2) → (V3 → V5)

代码实现

/**
 * 广度优先搜索（BFS），从指定顶点开始遍历。
 * @param {*} startVertex - 起始顶点
 * @returns {Array} 返回按访问顺序得到的顶点列表
 */
bfs(startVertex) {
   if(!this.adjacencyList.has(startVertex)) return [];


  const visited = new Set();
  const result = []; // 存储最终的结果
  const queue = []; // 需要将每一层的顶点加入到队列里面


  visited.add(startVertex);
  queue.push(startVertex);


  while(queue.length > 0){
    const current = queue.shift(); // 先拿到这个顶点
    result.push(current);


    // 接下来就需要寻找该顶点对应的下一层
    for(let nodeObj of this.adjacencyList.get(current)){
      const v = nodeObj.node;
      if(!visited.has(v)){
        visited.add(v);
        queue.push(v);
      }
    }
  }


  return result;
}

-EOF-