迭代测试二维网格连通性的算法

Question

假设我有一个 2D 网格大小，可以在每个索引处保存 0 或 1。网格从充满零开始，然后逐渐添加。在每一步，我都想验证添加下一个不会阻止零点形成一个连通分量(使用具有北、东、南和西邻居的 4 连通网格)。

什么是迭代测试 2D 网格连通性的快速算法？

目前，我在每次迭代中都使用了洪水填充，但我觉得应该有一种更快的算法来使用以前迭代中的信息。

另外，即使它们没有断开网格，放置它们的方法有时也会取消放置它们，所以我正在寻找的算法需要能够处理这个问题。

Answer 1

这受到 Kruskal 的迷宫生成算法的启发。

我将一个正方形的邻域定义为它周围的 8 个正方形，包括网格的外部(角正方形的邻域是其周围的 3 个正方形加上外部，所以总共有 4 个“正方形”)。

将 1 放入集合中，使任意两个相邻的 1 属于同一集合。将网格的外部视为一个大 1(这意味着第一组包含它)。添加 1 时，只需要检查它的邻居。

以下是所有可能的情况。为了更容易可视化，我将从 1 开始对集合进行编号，并在每个包含 1 的方 block 中使用集合编号而不是 1。外面属于编号为 1 的集合。您也可以使用它来简化执行。括号表示新放置的 1。

如果新的1没有相邻的1，那么它属于一个新的集合。

 0 0 0 0 0
 0 2 0 0 0
 0 0 0[3]0
 0 0 0 0 0
 0 0 1 0 0

如果它有一个相邻的1，那么它属于同一个集合。

 0 0 0 0 0
 0 2 0 0 0
 0 0[2]0 0
 0 0 0 0 0
 0 0 1 0 0

如果它有多个相邻的1，并且属于同一个集合的所有邻居都是直接邻居，那么可以合并这些集合，新的1属于结果集合。您无需检查断开连接。

 0 0 0 0 0                0 0 0 0 0
 0 2 0 0 0                0 1 0 0 0
 0 0[3]1 0       ->       0 0[1]1 0
 0 0 1 1 0                0 0 1 1 0
 0 0 1 0 0                0 0 1 0 0

 0 0 0 0 0                0 0 0 0 0
 0 2 0 0 0                0 1 0 0 0
 0 2 0 1 0       ->       0 1 0 1 0
[3]0 0 1 0               [1]0 0 1 0
 1 1 1 0 0                1 1 1 0 0

如果它有多个相邻的同一个集合的 1，但它们不都是直接邻居，那么你就断线了。

 0 0 0 0 0                0 0 0 0 0 <- first group of 0s
 0 2 0 0 0                0 1 0 0 0
 0 0[3]1 0       ->       0 0[1]1 0
 0 1 0 1 1                0 1 0 1 1
 1 0 0 0 0                1 0 0 0 0 <- second group of 0s

 0 0 0 0 0 <- first group of 0s
 0 0 1 0 0
 0 1 0 1 1 
[1]1 0 0 0
 0 0 0 0 0 <- second group of 0s

 0 0 0 0 0                0 0 0 0 0
 0 2 0 0 0                0 1 0 0 0
 0 2 0 1 0       ->       0 1 0 1 0
[3]0 0 1 0               [1]0 0 1 0
 0{1}1 0 0      lone 0 -> 0{1}1 0 0

在最后一个例子中，标记为 {1} 的 1 和外面在技术上是邻居，但从新放置的 1 的角度来看不是。

一般情况下，当移除一个有多个相邻1的1时，你需要检查它们在移除后是否仍然相连(例如，通过在它们之间运行一个路径查找器)。如果不是，将它们分成不同的集合。

如果你知道 0 都是相连的，那么你可以在本地检查:如果它的邻居都是直接邻居，则删除 1 不会拆分它所属的集合(不过要小心外部)。如果它的邻域中有多个“间隙”，它就会。

在特殊情况下，您只按照与添加顺序相反的顺序删除 1，您可以跟踪哪些新添加的 1 加入了多个集合(如果需要，甚至可以跟踪当时集合是什么)。当您稍后删除它们时，它们将拆分它们的集合。