已知边，是否存在分布式的图连通算法？

[Nostalgia]

最近工作中遇到的关于图连通的问题，感觉有些棘手。

假设给定的边如下（其中 abcdefgh 都是图的结点）：
a, b
c, d
a, c
b, e
f, g
h, g

正确的连通结果如下：
a, b, c, d, e
f, g, h

我的问题是：

1. 给定结点、边，是否存在一种通用的、分布式的图连通（无向图）算法？最好可以用 MapReduce/Spark 实现。
   个人感觉不存在，这个算法应该需要迭代进行。可能还不如单机做。
   Spark GraphX 是分布式的，应该很容易就能做这个，不知道是怎么做的呢？

2. 如果用单机做，有什么高效的图连通算法？
   我粗略想了一种时间复杂度 O(n) 的算法（ n 是图中结点个数）。
   大致思路是：对每个子图（这里就是一条条边）里的结点建倒排，然后按结点值 group by，建两个 map （一个存放各个子图的连通状态，另一个存储最终结果），用类似于并查集的方式做。

数据结构里图论掌握的比较浅，诚心求教。
谢谢大家。

[bumz]

分成 n 组，每组分别计算连通
再把结果汇总

比如

a, b
b, c
c, d

d, e
e, f
g, h

得到

a, b, c, d

d, e, f
g, h

再得到

a, b, c, d, e, f
g, h

[wingkou]

这不是并查集吗？

[bjrjk]

直接并查集不可以么

[pwrliang]

您好，我研究生阶段就是搞图计算的。
求图的强连通分量分布式是可以实现的，通过标签传播算法就可以实现。传统教科书可能会提到 DFS 来实现 CC 算法，感觉不太容易并行+分布式。你可以了解下标签传播算法，大概是这样的，每个顶点自己有一个初始标签，然后向 neighbor 发送自己的标签，一个顶点收到多个标签时取 min 或者 max，并行需要通过加锁或者 atomic 操作实现。假设我们把顶点按照机器数量平均分配，如果 neighbor 不在本机，则先把消息缓存。定期把缓存发送给 neighbor 所属的机器。
当所有顶点标签不再变化，就达到了收敛。然后每个顶点把自己的标签输出，同标签的就是处在同一个连通分量里。
至于 Map-reduce 能不能实现，肯定是可以的，只是我没有试过。GitHub 搜下应该有别人写好的。还有在 GPU 上实现 CC 的，如 hooking-jump 算法。

[aijam]

lz 都不看文档的么？ https://spark.apache.org/docs/latest/graphx-programming-guide.html#connected-components

[Nostalgia]

@bumz 谢谢回复。
这个做法感觉比较低效，因为边的划分是随机的，很难保证划分到一起的边就能连通起来。
随机的划分，很难保证连通过程最终会收敛。

[Nostalgia]

@wingkou @bjrjk
谢谢。单机做的话，并查集是很好的算法。我把做法弄复杂了。

[bsidb]

无向图做连通分量用 GraphX 性能还是可以的。如果是有向图做强连通分量检测的话，GraphX 的性能就比较拙计了，还不如直接单机串行算法。

如果图规模不大的话，GraphX 的额外开销太大，性能比不上单机 C++实现的版本。