假设我有一个 2D 网格大小，可以在每个索引处容纳零或一。网格开始时充满零，然后逐渐添加 1。在每一步中，我想验证添加下一个不会阻止零形成一个连接的组件(使用具有北、东、南和西邻居的 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 加入了多个集合(如果需要，甚至可以跟踪当时的集合是什么(。当您稍后删除它们时，这些将拆分它们的集合。