algorithm - 关于路径生成算法

Question

我需要设置一个二维空间（出于所有实际目的，一个二维数组）的路径..每个索引 [y][x] 都包含一个路径..例如

+--  --+   +--  --+
|  ||  |   |  ||  |
|  | ==     ==++== 
|  ||  |   |      |
+--  --+   +------+

虽然我可以随机初始化这个空间，但我希望能够生成一系列路径，以确保每个坐标都可以从其他坐标到达。

我应该看什么算法来解决这个问题？

我已经学习了许多寻路算法，例如 Dijkstra 或 A*，但我认为这些算法不适用于我的问题。

Answer 1

您遇到的问题本质上等同于查找生成树，这可以使用深度优先搜索或广度优先搜索在 O(n) 中完成。

提示：请注意，如果 A 可以从 B 到达并且 B 可以从 C 到达，那么 A 可以从 C 到达（传递性）；也只要你没有单向走廊，那么如果 A 可以从 B 到达，那么 B 也可以从 A 到达（自反性）。

对于生成迷宫，一旦生成了跨度，就可以开始添加额外的边以添加一些变化（尽管额外的边通常会使迷宫更容易解决）。span 保证了连通性。