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 个顶点。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。