假设我有一个 2D 网格大小，可以在每个索引处保存零或一。网格开始时充满了零，然后逐渐添加零。在每一步中，我想验证添加下一个不会阻止零形成一个连通分量(使用具有北、东、南、西邻居的 4 个连通网格)。
什么是能够迭代测试 2D 网格连通性的快速算法？
目前，我在每次迭代中都使用洪水填充，但我认为应该有一种更快的算法来使用以前迭代中的信息。
此外，放置这些元素的方法有时会取消放置这些元素，即使它们没有断开网格，所以我正在寻找的算法需要能够处理这个问题。
最佳答案
这受到 Kruskal 迷宫生成算法的启发。
我将一个正方形的邻域定义为它的 8 个周围的正方形，包括网格的外部(角正方形的邻域是它的 3 个周围的正方形加上外部，所以总共 4 个“正方形”)。
将 1 放入集合中，使得任意两个相邻的 1 属于同一集合。将网格的外部视为一个大 1(这意味着第一组包含它)。添加 1 时，只需检查其邻居即可。
以下是所有可能的情况。为了更容易可视化，我将从 1 开始对集合进行编号，并在每个包含 1 的方格中使用集合编号而不是 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，您可以跟踪哪些新添加的 1 加入了多个集合(如果需要，甚至可以跟踪当时的集合是什么)。当您稍后删除它们时，它们将拆分它们的集合。
关于迭代测试二维网格连通性的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51736195/