GraphX 带有一个 algorithm for finding connected components的图表。
我没有找到有关其实现复杂性的声明。
通常，查找连通分量可以在线性时间内完成，例如通过广度优先搜索或深度优先搜索(参见 Wikipedia article )。但是，这假设您可以将图形保存在内存中。 GraphX 实现了分布式的核外算法，所以我认为它没有可比性。
你知道他们的算法是如何工作的，有什么复杂性吗？
最佳答案
我认为图与非图解决方案的主要目标是减少解决问题所需的连续步骤数。这与复杂性不同——事实上，Graph 解决方案可能需要更多的 CPU 指令来执行，但如果它减少了顺序步骤的数量，它仍然是正确的解决方案。
就查找连通分量而言，广度优先和深度优先方法都具有相同数量的顺序步骤——即图中顶点数量的一些倍数。相同的逻辑必须按顺序应用于每个顶点。这就是整个解决方案。
即使您的图表有两个或多或少大小相等的集群，您也不能将工作分成两个工作人员并从一端开始并在中间相遇。你不知道尽头在哪里。你不知道中间在哪里。
如果您知进知出，您的顺序步骤总数可以减少一半。如果有帮助，您可以将其视为您在连续步骤方面可以做到的理论上最好的。它完全取决于图形的形状。
如果您有许多独立的独立集群，并且没有一个集群的人数超过 10 人，那么理论上您可以执行的最佳操作是 10 个连续步骤。无论您拥有多少并行处理能力，您最多只能执行 10 个连续步骤。
图形算法不仅能让您更接近理论最小值——根据您集群的形状，它实际上可以击败它。
那么Spark算法是如何工作的呢？这相当简单——每个节点只是将它的 VertexId 广播给它的邻居，它的邻居也这样做。任何接收到低于其自身广播的 VertexId 的节点将在下一轮广播；否则 Vertex 会静音。
如果你有一个集群，其中每个顶点都连接到所有其他顶点，那么在一轮消息之后，每个人都知道谁是最低的 VertexID，并且他们在下一轮都保持沉默。一个连续的步骤，整个集群。
另一方面，如果集群中的每个顶点最多只连接到其他 2 个顶点，那么在所有顶点知道最小 VertexID 是什么之前，它可能需要 N 个连续步骤.
显然，顺序步骤在图算法中具有不同的性质，甚至在图与图之间也不同。连接良好的图会生成大量消息并花费更多时间合并它们等。但它不会像连接不太好的图那样需要那么多的顺序步骤。
长话短说，图形解决方案的性能完全取决于图形的形状，但它应该比广度优先或深度优先的解决方案并行化好得多。
关于algorithm - Spark : What is the time complexity of the connected components algorithm used in GraphX?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36925353/