使用 union-find 对角线连接的连接组件标记

Question

我正在尝试对我发现的连通分量算法进行修改，作为这个问题的答案：Connected Component Labelling。

基本上，我有由 0 和 1 组成的 2d 和 3d 矩阵。我的问题是找到 1 的连接区域，分别标记每个区域。矩阵大小可以非常大（由 2-d 中的 5e4×5e4 元素和 3d 中的 1000^3 元素组成）。所以我需要一些东西，它不会占用堆栈内存，而且速度足够快，可以在模拟过程中重复几次。

该问题的最受支持的答案使用深度优先搜索，给出了堆栈溢出错误（如评论中所述）。我一直在尝试使用另一个用户建议的联合查找算法。

原始代码（由用户 Dukeling 编写）适用于大型二维矩阵，但我希望元素之间有对角线连接。这是我的代码，其中包含我尝试使用的示例输入：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

const int w = 8, h = 8;
int input[w][h] = {{1,0,0,0,1,0,0,1},
               {1,1,0,1,1,1,1,0},
               {0,1,0,0,0,0,0,1},
               {1,1,1,1,0,1,0,1},
               {0,0,0,0,0,0,1,0},
               {0,0,1,0,0,1,0,0},
               {0,1,0,0,1,1,1,0},
               {1,0,1,1,0,1,0,1}};
int component[w*h];

void doUnion(int a, int b)
{
// get the root component of a and b, and set the one's parent to the other
while (component[a] != a)
    a = component[a];
while (component[b] != b)
    b = component[b];
component[b] = a;
}

void unionCoords(int x, int y, int x2, int y2)
{
if (y2 < h && x2 < w && input[x][y] && input[x2][y2] && y2 > 0 && x2 > 0)
    doUnion(x*h + y, x2*h + y2);
}

int main()
{
int i, j;
for (i = 0; i < w*h; i++)
    component[i] = i;

for (int x = 0; x < w; x++)
for (int y = 0; y < h; y++)
{
    unionCoords(x, y, x+1, y);
    unionCoords(x, y, x, y+1);
    unionCoords(x, y, x+1, y+1);
    unionCoords(x, y, x-1, y+1);
    unionCoords(x, y, x+1, y-1);
    unionCoords(x, y, x-1, y-1);
}


// print the array
for (int x = 0; x < w; x++)
{
    for (int y = 0; y < h; y++)
    {
        if (input[x][y] == 0)
        {
            printf("%4d ",input[x][y]);
            continue;
        }
        int c = x*h + y;
        while (component[c] != c) c = component[c];
        printf("%4d ", component[c]);

    }
    printf("\n");
}
}

如您所见，我添加了 4 个用于在元素之间进行对角线连接的命令。这是联合查找算法的有效修改吗？我特别搜索了 Google 和 Whosebug，但找不到任何对角连接的示例。此外，我想将其扩展到 3 个维度 - 因此我需要添加 26 个命令进行检查。这种方式会很好地扩展吗？我的意思是代码似乎适用于我的情况，但有时我会随机得到一个未标记的孤立元素。我不想将它与我的代码集成，但几个月后才发现错误。

谢谢。

Answer 1

您使用联合查找算法的方法没有任何问题。 Union find 在任何图上运行。对于它检查的每个节点，它检查其连接的节点以确定它们是否在同一子集中。您的方法似乎就是这样做的，检查任何观察到的节点的 8 个相邻节点。联合查找算法与图形的维度无关。您可以将该方法扩展到 3d 或任何维度，只要您的图形与该维度正确对应即可。如果您在这方面遇到错误，您可以 post 该错误的示例，或查看代码审查：https://codereview.stackexchange.com/。

使用 union-find 对角线连接的连接组件标记

Connected component labeling with diagonal connections using union-find

algorithm

matrix

connected-components