图连通性优化算法问询：边添加至目标子图连通即停止的高效方案

嘿，这个问题我太熟了！你当前每次加边后都跑BFS检测连通性的方案，时间复杂度是O(m*(n+e))，当边数m或者顶点数n很大的时候，确实会慢得让人头疼。而并查集（Union-Find）能把这个过程优化到几乎线性的时间复杂度，完美适配你的需求。

核心思路 #

我们的核心目标是追踪目标子图的连通分量数量，一旦这个数量降到1，就说明目标子图完全连通，可以立刻停止加边。并查集的find（查找顶点根节点）和union（合并顶点集合）操作刚好能高效完成这件事，而且我们只需要关注目标顶点的连通状态，非目标顶点可以当作“桥梁”来处理。

结合你的例子一步步看：

顶点为1、2、3、4，目标子图为1、2、3；边序列(3,4)、(2,3)、(1,4)、(1,3)

1. 初始状态：目标子图的连通分量数是3（每个顶点各自独立）。
2. 处理边(3,4)：3是目标顶点，4不是。合并3和4的集合，但目标分量数还是3（因为4不在目标子图里，没有减少目标顶点的独立分量）。
3. 处理边(2,3)：2和3都是目标顶点，且属于不同集合。合并后，目标分量数减到2。
4. 处理边(1,4)：1是目标顶点，4和3已经连通。合并1和4的集合后，1和3连通，相当于目标子图的三个顶点都在同一个集合里了，分量数降到1——此时立即停止，不用处理第四条边。

具体实现步骤 #

1. 初始化并查集：包含所有顶点（包括非目标顶点），同时标记每个集合是否包含目标顶点。
2. 初始化计数器：目标子图的初始连通分量数等于目标顶点的数量。
3. 遍历边序列：
   • 对每条边的两个顶点，查找它们的根节点。
   • 如果根节点不同，合并两个集合。
   • 合并前检查：如果两个集合都包含目标顶点，那么合并后目标连通分量数减1。
   • 一旦计数器变为1，立刻终止遍历，停止加边。

代码示例（Python） #

class UnionFind:
    def __init__(self, max_vertex):
        # 假设顶点编号从1开始
        self.parent = list(range(max_vertex + 1))
        self.rank = [0] * (max_vertex + 1)
        # 标记该集合是否包含目标顶点
        self.contains_target = [False] * (max_vertex + 1)

    def find(self, x):
        # 路径压缩，加速后续查找
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            # 已经在同一集合，无需合并
            return False
        
        # 按秩合并，保持树的平衡
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
            # 如果被合并的集合包含目标，更新当前根的标记
            if self.contains_target[root_x]:
                self.contains_target[root_y] = True
        else:
            self.parent[root_y] = root_x
            if self.contains_target[root_y]:
                self.contains_target[root_x] = True
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
        return True

def stop_when_target_connected(target_vertices, edge_sequence, total_vertices):
    uf = UnionFind(total_vertices)
    # 初始化目标顶点的标记
    for v in target_vertices:
        uf.contains_target[v] = True
    # 初始连通分量数等于目标顶点数量
    target_component_count = len(target_vertices)

    for u, v in edge_sequence:
        root_u = uf.find(u)
        root_v = uf.find(v)
        if root_u != root_v:
            # 合并前检查两个集合是否都包含目标顶点
            u_has_target = uf.contains_target[root_u]
            v_has_target = uf.contains_target[root_v]
            
            if uf.union(u, v):
                # 只有两个都包含目标时，合并才会减少连通分量数
                if u_has_target and v_has_target:
                    target_component_count -= 1
                    if target_component_count == 1:
                        print("目标子图已连通，停止添加边")
                        return
    print("遍历完所有边，目标子图仍未连通")

# 测试你的例子
target = [1, 2, 3]
edges = [(3, 4), (2, 3), (1, 4), (1, 3)]
stop_when_target_connected(target, edges, 4)

时间复杂度分析 #

并查集的find和union操作在路径压缩和按秩合并的优化下，时间复杂度是O(α(n))，其中α是阿克曼函数的反函数，增长极慢，几乎可以看作常数。因此整个算法的时间复杂度是O(m α(n))，比你之前的O(mn)方案高效得多，尤其适合大规模数据的场景。

内容的提问来源于stack exchange，提问作者TheLeogend