使用 Union Find 查找无向图中连通分量的数量

Question

我已经盯着这个算法看了一段时间了，但没能发现我遗漏了什么。

逻辑：

初始化所有隔离组件
union frm，到每条边上的组件，如果这些组件尚未连接，则递减 # 组件。

问题：当运行这个特定的测试用例时，我怎么会得到这个 -48？

    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        roots = [i for i in range(n)]  # track disconnected components

        # n isolated islands
        for u, v in edges:

            root1 = self.findRoot(roots, u)
            root2 = self.findRoot(roots, v)

            if root1 != root2:
                roots[root1] = root2
                n -= 1
        #print(roots)
        return n

    def findRoot(self, roots, id):
        oid=id
        if roots[id] != id:
            # roots[id] = roots[roots[id]]
            id=roots[id]

        roots[oid]=id # path compression
        return id

测试用例：

n=100
edges=[[6,27],[83,9],[10,95],[48,67],[5,71],[18,72],[7,10],[92,4],[68,84],[6,41],[82,41],[18,54],[0,2],[1,2],[8,65],[47,85],[39,51],[13,78],[77,50],[70,56],[5,61],[26,56],[18,19],[35,49],[79,53],[40,22],[8,19],[60,56],[48,50],[20,70],[35,12],[99,85],[12,75],[2,36],[36,22],[21,15],[98,1],[34,94],[25,41],[65,17],[1,56],[43,96],[74,57],[19,62],[62,78],[50,86],[46,22],[10,13],[47,18],[20,66],[83,66],[51,47],[23,66],[87,42],[25,81],[60,81],[25,93],[35,89],[65,92],[87,39],[12,43],[75,73],[28,96],[47,55],[18,11],[29,58],[78,61],[62,75],[60,77],[13,46],[97,92],[4,64],[91,47],[58,66],[72,74],[28,17],[29,98],[53,66],[37,5],[38,12],[44,98],[24,31],[68,23],[86,52],[79,49],[32,25],[90,18],[16,57],[60,74],[81,73],[26,10],[54,26],[57,58],[46,47],[66,54],[52,25],[62,91],[6,72],[81,72],[50,35],[59,87],[21,3],[4,92],[70,12],[48,4],[9,23],[52,55],[43,59],[49,26],[25,90],[52,0],[55,8],[7,23],[97,41],[0,40],[69,47],[73,68],[10,6],[47,9],[64,24],[95,93],[79,66],[77,21],[80,69],[85,5],[24,48],[74,31],[80,76],[81,27],[71,94],[47,82],[3,24],[66,61],[52,13],[18,38],[1,35],[32,78],[7,58],[26,58],[64,47],[60,6],[62,5],[5,22],[60,54],[49,40],[11,56],[19,85],[65,58],[88,44],[86,58]]

Answer 1

错误在于findRoot函数。您当前正在检查提供的节点 (id) 是否是其自身的 parent，即，是否是其集合的代表元素。如果不是，你假设它的 parent 是代表，而 return 它。但这不一定是真的，即使您正在使用路径压缩。

假设您有 4 个节点 A、B、C 和 D。边是：A -> B，B -> C，A -> D。

你先把A的parent设置成B，再把B的parent设置成C，到这里就好了。但是当你到达处理最后一个边缘时，你调用 findRoot(..., A)。它检查 A 不是它自己的 parent，因此 return 是它的 parent B。但是，A 集合的代表元素甚至不是 B，而是 C。你可以看到 B 也不是它自己的 parent 。组件计数在这里并没有乱七八糟，但您可以看到它是如何产生错误结果的。

唯一需要改变的是您必须不断寻找代表元素，而不仅仅是 return 检查 1 次之后。

您的新方法将遵循：

def findRoot(self, roots, id):
    oid=id
    while roots[id] != id: # Keep looking for the representative
        id=roots[id]

    roots[oid]=id
    return id

此更改导致在您的输入数据中计算出 6 个连通分量。已与 DFS 确认。

要实现路径压缩，请将您在此循环中遇到的每个节点的 parent 设置为最终值。

使用 Union Find 查找无向图中连通分量的数量

Find the number of connected components in undirected graph using Union Find

algorithm

union-find