迭代测试二维网格连通性的算法
Algorithm for iteratively testing 2d grid connectiveness
假设我有一个 2D 网格大小，可以在每个索引处保存 0 或 1。网格从充满零开始，然后逐渐添加。在每一步，我都想验证添加下一个不会阻止零点形成一个连通分量（使用具有北、东、南和西邻居的 4 连通网格）。
什么是迭代测试 2D 网格连通性的快速算法？
目前我在每次迭代中都使用了洪水填充，但我觉得应该有一个更快的算法来使用以前迭代中的信息。
此外，即使不断开网格，放置的方法有时也会取消放置，所以我正在寻找的算法需要能够处理那个。
这受到 Kruskal 的迷宫生成算法的启发。
我将一个正方形的邻域定义为它周围的 8 个正方形，包括网格的外部（角正方形的邻域是其周围的 3 个正方形加上外部，所以总共 4 "squares" 个） .
将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不会分裂它所属的集合，如果它的邻居都是直接邻居（不过要小心外面）。如果附近有多个"gaps"，它就会。
在特殊情况下，您仅按添加顺序相反的顺序删除 1，您可以跟踪哪些新添加的 1 加入了多个集合（如果需要，甚至可以跟踪当时集合是什么） .当您稍后删除它们时，它们将拆分它们的集合。
假设我有一个 2D 网格大小，可以在每个索引处保存 0 或 1。网格从充满零开始，然后逐渐添加。在每一步，我都想验证添加下一个不会阻止零点形成一个连通分量（使用具有北、东、南和西邻居的 4 连通网格）。
什么是迭代测试 2D 网格连通性的快速算法？
目前我在每次迭代中都使用了洪水填充，但我觉得应该有一个更快的算法来使用以前迭代中的信息。
此外，即使不断开网格，放置的方法有时也会取消放置，所以我正在寻找的算法需要能够处理那个。
这受到 Kruskal 的迷宫生成算法的启发。
我将一个正方形的邻域定义为它周围的 8 个正方形，包括网格的外部（角正方形的邻域是其周围的 3 个正方形加上外部，所以总共 4 "squares" 个） .
将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不会分裂它所属的集合，如果它的邻居都是直接邻居（不过要小心外面）。如果附近有多个"gaps"，它就会。
在特殊情况下，您仅按添加顺序相反的顺序删除 1，您可以跟踪哪些新添加的 1 加入了多个集合（如果需要，甚至可以跟踪当时集合是什么） .当您稍后删除它们时，它们将拆分它们的集合。