《大规模分布式计算深入解析》5.3 连通分量、最短路径与三角计数

连通分量收敛到最小 id、SSSP 用超步传距离、三角计数统计邻接交集:三者在同一顶点程序框架上落地,各有消息与收敛口径。

三类算法的统一框架

连通分量、SSSP、三角计数都写成顶点程序:每超步收消息、更新自身、决定是否继续活跃。区别只在消息内容与收敛条件。

连通分量与最短路径

连通分量每超步把「当前最小 id」传给邻居,收敛到分量内最小 id:{0,1,2} 收敛到 0,顶点 1 并入分量 0;孤链 {3,4} 分量 id 3(用例 50-51)。

SSSP 沿边传「当前最短距离」:路径图距离 3(Bellman-Ford 超步,用例 43),源点距离 0(用例 44);多跳路径 0→1→2→4 距离 3,不可达顶点保持 -1(用例 52-53)。

三角计数

三角计数不靠消息收敛,靠统计邻接交集:顶点 0 位于三角形 (0,1,2) 中,全图仅 1 个三角形(用例 54-55)。它是 motif 计数的原型,超步里比对邻居集合。

验证

从卷十一实验包 解包,用 algo 用例 50、51 验证连通分量收敛到最小 id(0 与孤链 3);用例 43、44、52、53 验证 SSSP 距离 3、源点 0、不可达 -1;用例 54、55 验证顶点 0 在 1 个三角形、全图仅 1 个三角形。

一手资料

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

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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