这可以通过并集查找解决(尽管如其他答案所示,DFS可能更简单)。
该数据结构背后的基本思想是重复合并同一组件中的元素。这是通过将每个组件表示为树来完成的(节点跟踪其父节点,而不是相反),您可以遍历根节点来检查2个元素是否在同一组件中,并且可以合并节点通过简单地使一个根成为另一个根的父代。
一个简短的代码示例演示了这一点:
const int w = 5, h = 5;
int input[w][h] = {{1,0,0,0,1},
{1,1,0,1,1},
{0,1,0,0,1},
{1,1,1,1,0},
{0,0,0,1,0}};
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])
doUnion(x*h + y, x2*h + y2);
}
int main()
{
for (int 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);
}
// print the array
for (int x = 0; x < w; x++)
{
for (int y = 0; y < h; y++)
{
if (input[x][y] == 0)
{
cout << ' ';
continue;
}
int c = x*h + y;
while (component[c] != c) c = component[c];
cout << (char)('a'+c);
}
cout << "\n";
}
}
现场演示 。
上面将显示每组使用不同字母的字母。
p i
pp ii
p i
pppp
p
修改此属性应该很容易,以分别获取组件或获取与每个组件相对应的元素列表。一种想法是替换cout << (char)('a'+c);
上面带有componentMap[c].add(Point(x,y))
其中componentMap
是map<int, list<Point>>
-然后,此映射中的每个条目将对应于一个组件,并给出一个点列表。
有各种优化措施可以提高联合查找的效率,以上只是基本的实现。
0
几天前我曾问过类似的问题,但是我还没有找到解决问题的有效方法。我正在开发一个简单的控制台游戏,并且我有一个2D数组,如下所示:
我正在尝试查找所有包含相邻1(4路连通性)的区域。因此,在此示例中,这两个区域如下:
和:
我一直在努力的算法,找到了单元格邻居的所有邻居,并且在这种矩阵上工作得很好。但是,当我使用较大的数组(例如90 * 90)时,程序速度很慢,有时使用的巨大数组会导致堆栈溢出。
在另一个问题上,一个人告诉我有关连接组件标记的一种有效解决方案。
有人可以告诉我使用该算法的任何C ++代码,因为我对它如何与这种不相交的数据结构一起实际工作感到困惑...
非常感谢您的帮助和时间。