Kruskal 算法迷宫生成器

Kruskal 算法是一种最小生成树算法，可以用于生成迷宫。它尤其擅长生成完美迷宫。Prim 算法是 Kruskal 算法的替代方案，它也是一种最小生成树算法，但由于它们生成的迷宫相同，而且 Kruskal 算法运行速度更快，所以我没有实现 Prim 算法。

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

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

关于克鲁斯卡尔算法

克鲁斯卡尔算法是由美国数学家、统计学家和计算机科学家小约瑟夫·伯纳德·克鲁斯卡尔（Joseph Bernard Kruskal, Jr.）创建的。他于 1956 年在其论文《关于图的最短生成子树和旅行商问题》中首次描述了该算法。

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

Kruskal算法如何生成迷宫

步骤 1：初始化

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

步骤二：对墙壁进行分类

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

步骤 3：处理墙体

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

第四步：继续直至完成

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

由于 Kruskal 算法依赖于合并集合，因此可以使用并查集算法对其进行优化。并查集算法提供了一种在迷宫生成过程中追踪连通单元格的有效方法。您可以在这里查看我用 PHP 实现的并查集算法：链接

进一步阅读

如果您喜欢这篇文章，您可能还会喜欢这些建议：

• 生长树算法迷宫生成器
• 埃勒算法迷宫生成器
• 威尔逊算法迷宫生成器