这是一个创建于 2880 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近工作中遇到的关于图连通的问题，感觉有些棘手。
假设给定的边如下（其中 abcdefgh 都是图的结点）：
a, b
c, d
a, c
b, e
f, g
h, g
正确的连通结果如下：
a, b, c, d, e
f, g, h
我的问题是：
-
给定结点、边，是否存在一种通用的、分布式的图连通（无向图）算法？最好可以用 MapReduce/Spark 实现。
个人感觉不存在，这个算法应该需要迭代进行。可能还不如单机做。
Spark GraphX 是分布式的，应该很容易就能做这个，不知道是怎么做的呢？ -
如果用单机做，有什么高效的图连通算法？
我粗略想了一种时间复杂度 O(n) 的算法（ n 是图中结点个数）。
大致思路是：对每个子图（这里就是一条条边）里的结点建倒排，然后按结点值 group by，建两个 map （一个存放各个子图的连通状态，另一个存储最终结果），用类似于并查集的方式做。
数据结构里图论掌握的比较浅，诚心求教。
谢谢大家。
 | 1 bumz 2018 年 6 月 5 日  1 分成 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 |
 | 2 wingkou 2018 年 6 月 5 日 via Android 2 这不是并查集吗？ |
3
bjrjk 2018 年 6 月 5 日 via Android 1 直接并查集不可以么
 | 4 pwrliang 2018 年 6 月 5 日 4 您好，我研究生阶段就是搞图计算的。 求图的强连通分量分布式是可以实现的，通过标签传播算法就可以实现。传统教科书可能会提到 DFS 来实现 CC 算法，感觉不太容易并行+分布式。你可以了解下标签传播算法，大概是这样的，每个顶点自己有一个初始标签，然后向 neighbor 发送自己的标签，一个顶点收到多个标签时取 min 或者 max，并行需要通过加锁或者 atomic 操作实现。假设我们把顶点按照机器数量平均分配，如果 neighbor 不在本机，则先把消息缓存。定期把缓存发送给 neighbor 所属的机器。 当所有顶点标签不再变化，就达到了收敛。然后每个顶点把自己的标签输出，同标签的就是处在同一个连通分量里。 至于 Map-reduce 能不能实现，肯定是可以的，只是我没有试过。GitHub 搜下应该有别人写好的。还有在 GPU 上实现 CC 的，如 hooking-jump 算法。 |
 | 5 aijam 2018 年 6 月 5 日 |
 | 6 Nostalgia OP |
 | 8 bsidb 2018 年 6 月 5 日 1 无向图做连通分量用 GraphX 性能还是可以的。如果是有向图做强连通分量检测的话，GraphX 的性能就比较拙计了，还不如直接单机串行算法。 如果图规模不大的话，GraphX 的额外开销太大，性能比不上单机 C++实现的版本。 |
Select Language