用于查找图连通性的算法

Question

我正在解决一个有趣的编程问题。就是这样：我们一直在向图上添加无向边，直到图（或子图）被连接为止（即我们可以使用某种路径从每个顶点到达该子图中的任何其他顶点）。连接图表后，我们立即停止。例如，如果我们有顶点1,2,3和4，我们希望连接子图1,2,3。假设我们有边（3,4），然后是（2,3），然后是（1,4），然后是（1,3）。我们只需要在要连接的子图的前3个边中添加，然后停止（不需要边1,3）。显然，每次添加边时我都可以运行BFS，以查看是否可以达到所需的顶点，但是如果说有m条边，那么我们可能必须运行BFS m次，这似乎太慢了。还有更好的选择吗？谢谢。

Answer 1

您只能运行一次BFS来查找连接的组件。然后，每次添加一条边时，如果该边在两个不同组件的顶点之间，则可以通过参考对其进行合并。因此，该算法的复杂度为|V| + |E|。

注意，应通过一些参考技术来实现此方法，尤其是更新顶点的组件号。

Answer 2

您应该研究出色的“不交集数据结构”和相应的union-find算法。这似乎很神奇，但是最坏的情况是时间和空间复杂度很小，分别为O（α（n））和O（n），其中α是逆阿克曼函数。

Answer 3

我通常会使用不相交的集合结构来执行此操作，如Doug所建议的。就像Kruskal的算法一样，用于查找最小生成树，不同之处在于您以给定的顺序处理边缘。

但是，如果不需要生成树作为输出，则可以使用增量BFS或DFS进行此操作：

1. 选择任意一个顶点，并找到使用BFS或DFS连接到它的顶点。将这些顶点染成红色。
2. 添加边时，除非添加将红色顶点连接到非红色顶点的边，否则请勿做任何其他事情。然后运行BFS或DFS（不包括新边）以查找将连接到红色集的所有新顶点。将它们全部涂成红色。
3. 当所有顶点均为红色时停止。

实际上，这比使用不交集集要简单一些，并且花费O（| V | + | E |）的时间，因为每个顶点将被一个BFS / DFS搜索精确地遍历。

但是，它以块的形式进行工作，因此，如果您需要每个边缘测试都快速[[单独，那么不相交的集合会更好。