《大规模分布式计算深入解析》5.1 BFS/DFS 分布式化:宽度优先的消息波

BFS 用超步广播消息波:路径图 4 顶点 3 边共 4 个超步,末端距离 3,消息数等于边数 3;DFS 难并行故被 BFS 取代。

BFS/DFS 的分布式化

BFS 天生适合 BSP:每个超步是一条消息波。DFS 的深度优先串行依赖难并行,分布式图计算基本不做 DFS,改用 BFS/SSSP 系列。

宽度优先的消息波

超步 0 源点广播,活跃顶点计算并投票,每超步推进一层。路径图 4 顶点 3 边共 4 个超步(源点 + 3 层),末端距离 3,消息数恰好等于边数 3。

flowchart LR
    S0["超步 0\n源点 0 距离 0"]
    S1["超步 1\n顶点 1 距离 1"]
    S2["超步 2\n顶点 2 距离 2"]
    S3["超步 3\n顶点 3 距离 3"]
    S0 --> S1 --> S2 --> S3

消息波的成本

每条边只产生一条消息(用例 19、22),消息数 = 边数,通信量天然等于跨区边数。BFS 是单源最短路的特例:路径图距离 3(用例 43)、源点距离 0(用例 44)。

验证

从卷十一实验包 解包,用 bsp 用例 16、17 验证 BFS 源点距离 0、末端距离 3;用例 18 验证 4 顶点 3 边共 4 个超步;用例 19 验证 3 条边产生 3 条消息;graph 用例 7 验证 BFS 层数(源点 0 层 0、顶点 1 层 1、顶点 4 层 2);graph 用例 8 验证 DFS 遍历到全部 5 个顶点。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图