如何在没有邻接矩阵的情况下有效地找到图中的连接组件？
How to find connected components in graph efficiently without adjacency matrix?
我想在无向图中找到连通分量。但是，我没有邻接矩阵。相反，我有一组顶点以及一个告诉我两个顶点是否相邻的函数。找到所有连接组件的最有效方法是什么？
我知道我可以只计算整个邻接矩阵并使用深度优先搜索来查找所有组件。但这不是很有效，因为我需要检查每一对顶点。
我目前正在做的是以下程序：
- 选择任何未分配的顶点，它现在是它自己的组件
- 找到该顶点的所有邻居并将它们添加到组件
- 找到刚刚添加的顶点的所有邻居（在那些尚未分配给任何组件的顶点中）并添加它们
- 重复上一步，直到找不到新的邻居
- 组件完成，从第一步开始重复寻找其他组件，直到所有顶点都赋值
这是伪代码：
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
我知道这种方法在大多数情况下比计算邻接矩阵要快，因为我不需要检查两个顶点是否相邻，如果已经知道它们属于同一个组件。但是有没有办法改进这个算法呢？
最终，任何算法都必须为最终属于单独组件的每一对顶点调用 vertices_adjacent，否则它将永远无法验证没有 link在这些组件之间。
现在，如果大多数顶点都属于一个组件，那么这样的对可能不会太多；但是除非你 期望 大多数顶点都属于一个组件，否则专门针对这种情况进行优化毫无意义。因此，放弃那种情况，最好的情况是：
- 结果正好是两个分量，每个分量的顶点数相同（½|V|）。所以有 ¼|V|2 对顶点属于不同的分量，你需要为每个顶点调用
vertices_adjacent那些对。
- 这两个组件原来是完整的，或者你非常幸运地选择了首先要检查的边，这样你就可以通过检查 |V 来检测连接的部分| − 2 对。
。 . .这仍然涉及制作 ¼|V|2 + |V| − 对 vertices_adjacent 的 2 次调用。相比之下，构建邻接表方法使 ½|V|2 − ½|V|调用——这比最好的情况多，但不到 2 倍。（最坏的-情况简单地等同于构建邻接列表方法。如果没有组件包含两个以上的顶点，或者如果图形是非循环的并且您不太可能选择要首先检查的边，就会发生这种情况。大多数图形将介于两者之间。）
因此，对于 vertices_adjacent.
的 确切 最小调用次数，可能不值得尝试进行过于紧密的优化
也就是说，您的方法对我来说似乎很合理；它不会对 vertices_adjacent 进行任何明显不必要的调用，因此唯一的改进将是概率改进，如果它可以更好地猜测哪些调用将对消除以后的调用有用。
一种可能性：根据power-law distribution，在许多图中，有些顶点的邻居很多，有些顶点的邻居相对较少。因此，如果您根据已知的邻居数量来确定顶点的优先级，则可以利用该模式。 （我认为如果大多数顶点真的 do 都属于一个组件，这是唯一比 2 更好的情况改进甚至是可以想象的。）但是，你必须测试看看它是否真的对你感兴趣的图表产生影响。
我想在无向图中找到连通分量。但是，我没有邻接矩阵。相反，我有一组顶点以及一个告诉我两个顶点是否相邻的函数。找到所有连接组件的最有效方法是什么？
我知道我可以只计算整个邻接矩阵并使用深度优先搜索来查找所有组件。但这不是很有效，因为我需要检查每一对顶点。
我目前正在做的是以下程序：
- 选择任何未分配的顶点，它现在是它自己的组件
- 找到该顶点的所有邻居并将它们添加到组件
- 找到刚刚添加的顶点的所有邻居（在那些尚未分配给任何组件的顶点中）并添加它们
- 重复上一步，直到找不到新的邻居
- 组件完成，从第一步开始重复寻找其他组件，直到所有顶点都赋值
这是伪代码：
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
我知道这种方法在大多数情况下比计算邻接矩阵要快，因为我不需要检查两个顶点是否相邻，如果已经知道它们属于同一个组件。但是有没有办法改进这个算法呢？
最终，任何算法都必须为最终属于单独组件的每一对顶点调用 vertices_adjacent，否则它将永远无法验证没有 link在这些组件之间。
现在，如果大多数顶点都属于一个组件，那么这样的对可能不会太多；但是除非你 期望 大多数顶点都属于一个组件，否则专门针对这种情况进行优化毫无意义。因此，放弃那种情况，最好的情况是：
- 结果正好是两个分量，每个分量的顶点数相同（½|V|）。所以有 ¼|V|2 对顶点属于不同的分量，你需要为每个顶点调用
vertices_adjacent那些对。 - 这两个组件原来是完整的，或者你非常幸运地选择了首先要检查的边，这样你就可以通过检查 |V 来检测连接的部分| − 2 对。
。 . .这仍然涉及制作 ¼|V|2 + |V| − 对 vertices_adjacent 的 2 次调用。相比之下，构建邻接表方法使 ½|V|2 − ½|V|调用——这比最好的情况多，但不到 2 倍。（最坏的-情况简单地等同于构建邻接列表方法。如果没有组件包含两个以上的顶点，或者如果图形是非循环的并且您不太可能选择要首先检查的边，就会发生这种情况。大多数图形将介于两者之间。）
因此，对于 vertices_adjacent.
也就是说，您的方法对我来说似乎很合理；它不会对 vertices_adjacent 进行任何明显不必要的调用，因此唯一的改进将是概率改进，如果它可以更好地猜测哪些调用将对消除以后的调用有用。
一种可能性：根据power-law distribution，在许多图中，有些顶点的邻居很多，有些顶点的邻居相对较少。因此，如果您根据已知的邻居数量来确定顶点的优先级，则可以利用该模式。 （我认为如果大多数顶点真的 do 都属于一个组件，这是唯一比 2 更好的情况改进甚至是可以想象的。）但是，你必须测试看看它是否真的对你感兴趣的图表产生影响。