迭代测试二维网格连通性的算法
假设我有一个2D网格大小，可以在每个索引处容纳0或1。网格从充满0开始，然后逐渐添加1。在每个步骤中，我希望验证添加下一个1不会阻止0形成一个连接的组件(使用具有北、东、南和西邻居的4-连接网格)。
什么是迭代测试2D网格连通性的快速算法？
目前我在每次迭代中都使用泛洪填充，但我觉得应该有一个更快的算法来使用以前迭代中的信息。
此外，放置这些元素的方法有时会替换这些元素，即使它们没有断开网格连接，因此我正在寻找的算法需要能够处理这一点。
回答 1
Stack Overflow用户
发布于 2018-08-08 07:26:12
这是受到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加入了多个集合(如果需要，甚至可以跟踪这些集合在那个时刻是什么)。当您稍后删除它们时，它们将拆分它们的集合。
https://stackoverflow.com/questions/51736195
复制相似问题