algorithm - 如何在没有邻接矩阵的情况下有效地找到图中的连接组件？

Question

我想在无向图中找到连通分量。但是，我没有邻接矩阵。相反，我有一组顶点以及一个告诉我两个顶点是否相邻的函数。找到所有连接组件的最有效方法是什么？

我知道我可以只计算整个邻接矩阵并使用深度优先搜索来查找所有组件。但这不是很有效，因为我需要检查每一对顶点。

我目前正在做的是以下程序:

1. 选择任何未分配的顶点，它现在是它自己的组件
2. 找到该顶点的所有邻居并将它们添加到组件
3. 找到刚刚添加的顶点的所有邻居(在那些尚未分配给任何组件的顶点中)并添加它们
4. 重复上一步，直到找不到新的邻居
5. 现在组件已经完成，从第一步开始重复寻找其他组件，直到所有顶点都赋值

这是伪代码:

connected_components(vertices):
  // vertices belonging to the current component and whose neighbors have not yet been added
  vertices_to_check= [vertices.pop()]
  // vertices belonging to the current component
  current_component = []
  components = []
  while (vertices.notEmpty() or vertices_to_check.notEmpty()):
    if (vertices_to_check.isEmpty()): // All vertices in the current component have been found
      components.add(current_component)
      current_component = []
      vertices_to_check= [vertices.pop()]
    next_vertex = vertices_to_check.pop()
    current_component.add(next_vertex)
    for vertex in vertices: // Find all neighbors of next_vertex
      if (vertices_adjacent(vertex, next_vertex)):
        vertices.remove(vertex)
        vertices_to_check.add(vertex)
  components.add(current_component)
  return components

我知道这种方法在大多数情况下比计算邻接矩阵要快，因为我不需要检查两个顶点是否相邻，如果已知它们属于同一个组件。但是有没有办法改进这个算法呢？

Answer 1

最终，任何算法都必须为属于不同组件的每一对顶点调用 vertices_adjacent，否则它永远无法验证这些组件之间没有链接.

现在，如果大多数顶点都属于一个组件，那么这样的对可能不会太多；但是除非您期望大多数顶点都属于一个组件，否则专门针对这种情况进行优化就没有意义了。因此，放弃那种情况，最好的情况是:

• 结果恰好有两个组件，每个都有相同数量的顶点(每个 ½|V|)。因此，有 ¼|V|² 对顶点属于单独的组件，您需要为每一对调用 vertices_adjacent。
• 这两个组件原来是完整的，或者你在选择要首先检查的边时非常幸运，这样你就可以通过检查 |V 来检测连接的部分| − 2 对。

. . .这仍然涉及制作 ¼|V|² + |V| − 2 次调用 vertices_adjacent。相比之下，构建邻接表方法使 ½|V|² − ½|V|调用——这比最好的情况多，但不到 2 倍。(最坏的-情况简单地等同于构建邻接列表方法。那如果没有组件包含两个以上的顶点，或者如果图形是非循环的并且您不太可能选择要首先检查的边，就会发生这种情况。大多数图形将介于两者之间。)

因此，可能不值得为 精确 的 vertices_adjacent 调用次数进行过于紧密的优化。

也就是说，您的方法对我来说似乎很合理；它不会对 vertices_adjacent 进行任何明显不必要的调用，因此唯一的改进将是概率改进，如果它可以更好地猜测哪些调用将对以后消除有用电话。

一种可能性:根据power-law distribution，在许多图中，有些顶点有很多邻居，有些顶点有相对较少的邻居。 .因此，如果您根据已知的邻居数量来确定顶点的优先级，则可以利用该模式。 (我认为如果大多数顶点确实确实都属于一个组件，这可能特别有用，这是唯一一个比 2 更好的改进是均匀的情况可以想象。)但是，您必须测试它是否真的对您感兴趣的图表产生影响。