Kruskal 算法迷宫生成器

Kruskal 算法是一种最小生成树算法，可用于生成迷宫。它对于创建完美迷宫特别有效。Kruskal 算法的替代算法是 Prim 算法，它也是一种最小生成树算法，但由于它们生成的迷宫相同，而且 Kruskal 算法运行速度更快，所以我没有费心去实现 Prim 算法。

完美迷宫是指从迷宫中的任何一点到其他任何一点都只有一条路径的迷宫。这意味着你不会兜圈子，但你会经常遇到死胡同，不得不掉头回去。

这里生成的迷宫地图包括一个没有起点和终点位置的默认版本，因此您可以自行决定起点和终点位置：从迷宫中的任何一点到其他任何一点都有解法。如果你想获得灵感，可以启用建议的起点和终点位置，甚至可以查看两者之间的解法。

关于 Kruskal 算法

Kruskal 算法是由美国数学家、统计学家和计算机科学家 Joseph Bernard Kruskal, Jr. 创建的。他在 1956 年的论文《论图的最短生成子树和旅行商问题》中首次描述了该算法。

该算法旨在找到图的最小生成树 (MST)，确保所有顶点都以尽可能最小的总边权重连接，同时避免循环。

Kruskal 算法如何生成迷宫

步骤 1：初始化

• 将迷宫中的每个单元视为一个单独的集合（一个唯一的组件）。
• 将相邻单元格之间的所有壁列出作为潜在边缘。

第 2 步：对墙壁进行分类

• 打乱或随机排列墙壁。如果将其实现为真正的 Kruskal 算法，则按随机顺序对墙壁进行排序（因为迷宫生成不需要权重）。

步骤 3：流程墙

• 穿过被打乱的墙壁。
• 如果被墙隔开的两个单元格属于不同的集合（即，它们在迷宫中尚未连接），则移除墙并合并集合。
• 如果它们已经在同一组中，则跳过墙（以避免循环）。

步骤 4：继续直至完成

• 重复此过程，直到所有单元都连接起来，形成一棵单生成树。
• 最后，每个单元都与其他单元相连，没有环路或孤立的部分。

由于 Kruskal 算法依赖于合并集合，因此可以使用 Union-Find 算法对其进行优化，该算法提供了一种在迷宫生成过程中跟踪连接单元的有效方法。您可以在此处查看我对 Union-Find 算法的 PHP 实现：PHP 中的不相交集（并查集算法）