连接二维数组中的不相交集

Question

我正在尝试生成一个随机网格，其中包含可遍历和不可遍历的位置，并确保在 4 个方向之一上存在从一个可遍历位置到任何其他可遍历位置的路径{右、上、左，吃下}。可遍历位置表示为“[]”，不可遍历位置表示为“[X]”

Here is a grid I have generated: 
[ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][X][ ][X]
[ ][ ][X][ ][ ][ ][X][ ][ ][X][X][ ][ ][ ]
[X][ ][ ][ ][ ][X][X][X][ ][ ][ ][X][ ][ ]
[ ][ ][ ][ ][ ][X][ ][ ][ ][X][ ][ ][X][ ]
[ ][X][ ][ ][ ][X][ ][ ][ ][ ][X][X][X][X]
[ ][ ][X][X][X][ ][ ][ ][X][X][X][X][X][X]
[ ][X][ ][ ][ ][X][ ][ ][ ][X][X][ ][ ][X]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][ ]
[ ][ ][X][ ][ ][ ][X][ ][X][X][ ][ ][ ][ ]
[ ][X][ ][X][ ][ ][ ][ ][ ][ ][X][X][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][X][X][ ]

我可以使用什么算法来找到网格中的不相交集并在不相交集之间创建路径？谢谢！

Answer 1

要找到不相交的组件，您可以使用从任何可遍历位置开始的广度优先搜索（使用队列）或深度优先搜索（使用堆栈）。当搜索终止时，它将标记整个组件。然后如果有未标记的位置，将其作为另一个搜索的起点，等等，直到标记完所有可遍历的位置。

为了弄清楚哪些不可遍历的位置必须被删除，如果你希望删除（几乎）尽可能少，请考虑每个 "disjoint sets"（最好称它们为 "connected components") 作为图中的单个节点，并查看连接它们的各种路径。计算将一个节点连接到另一个节点的每条路径必须删除的 X 的数量，并将其用作图中边的权重。然后您想使用例如 Kruskal 算法找到该图的最小生成树。

该方法不能保证找到要移除的最小 X 数以连接可遍历位置；例如，在您给出的图表中，删除右上角附近的单个 X 连接三个组件，而我的建议可能会导致删除两个 X。但是，您的问题描述得很含糊，所以我认为区别并不重要。

要找到要删除的 X 的确切最小数量，您必须解决 "node-weighted Steiner tree problem"，我相信这通常是 NP-hard。鉴于您的图表是平面的，您可能可以获得很好的近似值：http://www-math.mit.edu/~hajiagha/NodePlanarSteiner.pdf.

连接二维数组中的不相交集

Connecting disjoint sets in a 2D array

algorithm

grid

path-finding

disjoint-sets

disjoint-union