GraphX带有图形的algorithm for finding connected components。
我没有找到有关其实现复杂性的陈述。
通常，查找连接的组件可以在线性时间内完成，例如通过广度优先搜索或深度优先搜索(请参阅Wikipedia article)。但是，这假定您可以将图形保留在内存中。 GraphX实现了一种分布式核外算法，因此我认为它不具有可比性。
您知道他们的算法如何工作以及有什么复杂性吗？
最佳答案
我认为图与非图解决方案的主要目标是减少解决问题所需的顺序步骤。这与复杂度不同-实际上，Graph解决方案可能需要更多的CPU总指令来执行，但如果减少顺序步骤的数量，它仍然是正确的解决方案。
就查找连接的组件而言，广度优先和深度优先的方法都具有相同数量的顺序步骤-即图中顶点数量的一些倍数。必须将相同的逻辑顺序应用于每个顶点。这就是整个解决方案。
即使您的图具有两个或多或少相等大小的群集，您也无法将工作分为两个工作人员，并从一端开始并在中间相遇。你不知道目的在哪里。您不知道中间在哪里。
如果您知道要执行的操作，则可以将顺序步骤的总数减少一半。如果有帮助，您可以认为这是您可以按顺序进行的理论上最好的工作。它完全取决于图形的形状。
如果您有很多离散的群集，没有连接，并且群集都不超过10个人，那么理论上最好的方法是10个连续步骤。无论您拥有多少并行处理能力，您最好的工作就是10个连续步骤。
图算法不仅使您更接近理论上的最小值，而且还取决于集群的形状，它实际上胜过了它。
那么Spark算法是如何工作的呢？这非常简单-每个节点仅将其VertexId广播给其邻居，并且其邻居也这样做。接收到的VertexId低于其自身的VertexID的任何节点都将在下一轮进行广播。如果不是这样，顶点将变为静音。
如果您有一个群集，其中每个顶点都与其他每个顶点相连，则在经过一轮消息后，每个人都会知道谁是最低的VertexID，并且它们在下一轮都将保持静默状态。一个顺序步骤，即整个群集。
另一方面，如果群集中的每个顶点最多仅连接到其他2个顶点，那么在所有顶点知道最小ojit_code是谁之前，可能需要执行N个连续步骤。
显然，顺序步骤在图算法中具有不同的性质，甚至在图与图之间也有所不同。一个连接良好的图将生成大量消息，并花费更多的时间来合并它们，等等。但是，与连接较差的图相比，它不会采取那么多的顺序步骤。
长话短说，图解决方案的性能完全取决于图的形状，但是它应该比广度优先或深度优先的解决方案并行得多，并且要好得多。