Skip to main content

2.2.1 BFS

BFS（Breadth-First Search，广度优先搜索）是图论中最基础的遍历算法之一。在 PanGaea 论文 3.2 节中，它被用来对 pangenome graph 做分区。为了理解它为什么合适，我们先从 BFS 本身讲起，再联系到 pangenome graph 的特殊结构。

1. BFS 是什么？​

BFS 从某个起点（源顶点）出发，按“层”向外扩展：

  1. 先访问起点；
  2. 再访问所有与起点直接相邻的顶点（第一层）；
  3. 然后访问与第一层顶点相邻、但还没访问过的顶点（第二层）；
  4. 依此类推，直到所有可达顶点都被访问。

实现上通常用一个队列：

  • 起点入队；
  • 出队一个顶点，访问它，把它的未访问邻居全部入队；
  • 重复直到队列为空。

因为按层扩展，BFS 有一个重要性质：在无权图中，它找到的路径是最短路径（边数最少）。这也是 BFS 常用于最短路径、连通分量、网络爬虫等场景的原因。

2. BFS 的关键性质​

结合 PanGaea 的图划分需求，BFS 有几个特别有用的性质：

① 层次扩展，宽度有限​

BFS 每次只扩展当前层的邻居，不会像 DFS（深度优先搜索）那样沿着一条路径一直深入。
在 pangenome graph 中，大部分区域是线性拓扑——就是一条长链，偶尔有分支（变异泡）。
BFS 沿着这条长链扩展时，每一层通常只有少数几个顶点，不会突然扩散到很远的地方。
这正好符合“把空间上相邻的顶点聚在一起”的目标。

② 天然的空间局部性​

BFS 访问的顶点在图上彼此靠近。
把 BFS 访问顺序中连续的顶点放进同一个分区，分区内的顶点在图上就是局部连通的，跨分区的边自然就少。
图链阶段需要频繁访问相邻顶点，局部性好意味着这些访问大多落在同一个片上分区里，减少 DRAM 访问。

③ 避免长距离依赖​

如果图中有长距离边（连接相距很远的顶点），DFS 可能会顺着这条边跳到一个很远的地方，把不相关的区域混在一起。
BFS 按层扩展，长距离边只会让某一层多一个邻居，不会让遍历主线跳走。
因此 BFS 能有效限制长距离依赖的影响，把分区边界控制在局部。

④ 支持多源并行​

BFS 可以从多个种子顶点同时开始，每个 BFS 构建一个独立分区。
这些 BFS 之间互不干扰，可以并行执行。
在硬件上，这意味着可以同时生成多个分区，提高划分效率。

3. 为什么不用 DFS 或 METIS？​

DFS 的问题​

DFS 沿着一条路径深入，容易把一条长链一路走到底，导致分区形状细长，甚至跨越很远区域。
在 pangenome graph 中，这可能把线性区域切得七零八落，或者把长距离边引入分区，破坏局部性。

METIS 的问题​

METIS 是经典的图划分算法，目标是最小化跨分区边（最小割）。
但它有两个问题：

  1. ** scalability**：在 31 亿碱基对的 pangenome graph 上，METIS 可能太慢或内存不够；
  2. 忽略节点长度异质性：METIS 只考虑顶点和边，不考虑每个顶点对应多长的 DNA 序列。
    在 pangenome graph 中，一个顶点可能代表几个碱基，也可能代表几千个碱基。
    如果只按顶点数划分，可能一个分区里全是短顶点，另一个分区里一个长顶点就撑爆 GLB。

BFS + 装箱则直接按碱基总长度约束分区大小，更贴合实际存储需求。

4. BFS 在 PanGaea 中具体怎么用？​

论文 3.2 节的流程是：

  1. 选种子顶点：可以选多个种子，并行开始 BFS。
  2. BFS 遍历：从种子出发，按层访问相邻顶点。
  3. 贪心装箱：维护当前 bin，每访问一个顶点，检查它的序列长度 σ(v)\sigma(v) 加入后是否超过容量 LL。
    • 没超过：放入当前 bin；
    • 超过了：结束当前 bin，开一个新 bin，继续装。
  4. 多源并行：多个 BFS 同时进行，各自生成独立分区。

这样得到的分区：

  • 每个 bin 内碱基总数 ≤L\leq L，能完整放进 GLB；
  • 分区内顶点在图上相邻，局部性好；
  • 跨分区边少，减少通信；
  • 长距离依赖被 BFS 的层次扩展限制住。

5. 一个直观比喻​

想象 pangenome graph 是一条很长的公路，偶尔有岔路和环岛（变异泡）。

  • DFS 像一辆车沿着一条路一直开，可能开到很远的地方才回头，容易把不同路段混在一起。
  • BFS 像从起点开始，一层一层地推进：先看最近的几个路口，再看下一层路口。
    这样自然就把一段连续的路段圈在一起，形成一个个局部区域。
  • 装箱 则像给每个区域分配一个固定大小的停车场，按车辆总长度来装，装满就换下一个停车场。

6. 总结​

BFS 在 PanGaea 中不是用来找最短路径，而是作为一种局部性驱动的图遍历策略。
它利用 pangenome graph 主要是线性拓扑的特点，按层扩展，宽度有限，天然把空间相邻的顶点聚在一起，避免长距离依赖，并支持多源并行。
再结合按碱基长度的贪心装箱，就能把庞大的 pangenome graph 划分成一个个能装进 GLB 的小分区，为 3.1 节的融合 tiling 提供基础。

一句话：BFS 在这里的作用是“沿着图一层层地圈地”，让每个圈出来的区域既局部紧凑，又不超过片上内存容量。