连接元件计数

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

我没有完全理解你的问题，把它写清楚并组织好你的问题，对你自己真的有好处。在

我的理解是，你想在0-1图像中使用8邻域来标记连接的组件。如果是这样的话，你假设得到的邻域图是平面的，这是错误的。你在“对角线”有十字路口。在这样的图像中构造K{3,3}或K{5}应该很容易。在

Answer 2

我的变体：

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}$

Answer 3

你的算法有缺陷。考虑这个例子：

11110
01010
10010
11101

你的算法有2个组件，而它只有1个组件。在

为了测试，我使用了您代码的这个稍微修改过的版本。在

^{pr2}$

让我试着用文字来解释你的算法（用图形而不是网格）。在

• Set'roots'为空集。在
• 迭代图中的节点。
  • 对于一个节点n，看看它所有的邻居已经处理过了。把这个集合称为A
  • 如果A为空，则选择一个新值k，将v[node]设置为k，并将k添加到根中。在
  • 否则，设k为A中节点v[node]的最小值。用v[x]从A中每个x的根中移除v[x]！=k
• 成分数是根的元素数。在

（您的tree与我的roots相同：请注意，您从不使用tree[]元素的值，只使用它们是否为0。。。这只是实现一个集合）

它类似于union find，只是它假定在合并两个组件时，v[]值较高的那个组件以前从未与另一个组件合并。在反例中，这是被利用的，因为中间列中的两个0已与其左侧的0合并。在