c++ - 连接组件计数

Question

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

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

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

这是我的代码。输入文件已减少为 0 和 1。程序输出由 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

我没有完全理解你的问题，如果你清楚地写下这个问题并构建你的问题，你真的会受益匪浅。

我的理解是，你想通过使用 8 邻域在 0-1 图像中进行连通分量标记。如果是这样，您认为生成的邻域图是平面的假设是错误的。你在“对角线”处有交叉点。在这样的图像中构造 K_{3,3} 或 K_{5} 应该很​​容易。