连接元件计数

Question

在standard algorithm for connected component counting中，使用了称为union-find的不相交集数据结构。在

为什么要使用这种数据结构？我编写了一些代码来线性搜索图像，维护两个线性缓冲区来存储每个连接像素的当前和下一个组件计数，方法是检查四个邻居（E、SE、S、SW），并且在连接的情况下，更新连接映射以将较高的组件与较低的组件连接起来。 完成后，搜索所有未连接的零部件并报告计数。在

我只是不明白为什么这种方法比使用union find效率低。在

这是我的密码。输入文件已缩减为0s和1s。程序输出由0s组成的连接组件的数量

def CompCount(fname):
    fin = open(fname)
    b,l = fin.readline().split()
    b,l = int(b),int(l)+1
    inbuf = '1'*l + fin.read()
    prev = curr = [sys.maxint]*l
    nextComp = 0
    tree = dict()
    for i in xrange(1, b+1):
        curr = [sys.maxint]*l
        for j in xrange(0, l-1):
            curr[j] = sys.maxint
            if inbuf[i*l+j] == '0':
                p = [prev[j+n] for m,n in [(-l+1,1),(-l,0),(-l-1,-1)] if inbuf[i*l + j+m] == '0']
                curr[j] = min([curr[j]] + p + [curr[j-1]])
                if curr[j] == sys.maxint:
                    nextComp += 1
                    curr[j] = nextComp
                    tree[curr[j]] = 0                   
                else:
                    if curr[j] < prev[j+1]: tree[prev[j+1]] = curr[j]
                    if curr[j] < prev[j]:   tree[prev[j]]   = curr[j]
                    if curr[j] < prev[j-1]: tree[prev[j-1]] = curr[j]
                    if curr[j] < curr[j-1]: tree[curr[j-1]] = curr[j]
        prev = curr
    return len([x for x in tree if tree[x]==0])

Answer 1

我的变体：

1. 将整个图形拆分为边。将每条边添加到一个集合中。在
2. 在下一次迭代中，在步骤2中生成的边的两个外部节点之间绘制边。这意味着将新节点（及其相应的集）添加到原始边的源集中。（基本集合并）
3. 重复2次，直到要查找的两个节点位于同一集中。您还需要在步骤1之后进行检查（以防两个节点相邻）。在

一开始，你的节点将是各自的集合

 o-o     o-o    o1-o3  o2   o3-o4
   \     /                    |
   o-o-o-o             o2  o1-o3-o4 

随着算法的进展和集合的合并，它的输入相对减少了一半。在

在这个例子中，我正在检查一些图形中的组件。在将所有边合并到它们的最大可能集合之后，我只剩下3个集合，给出了3个断开的组件。 （组件数是算法完成时可以获得的集合数。）

一个可能的图形（对于上面的树）：

^{pr2}$