Kruskal 演算法迷宮生成器

Kruskal 演算法是一種最小生成樹演算法，可用於產生迷宮。它尤其擅長生成完美迷宮。 Prim 演算法是 Kruskal 演算法的替代方案，它也是一種最小生成樹演算法，但由於它們產生的迷宮相同，而且 Kruskal 演算法運行速度更快，所以我沒有實作 Prim 演算法。

完美迷宮是指從迷宮中的任意一點到另一點都只有一條路徑的迷宮。這意味著你不會最終陷入繞圈的境地，但你會經常遇到死胡同，迫使你轉身返回。

這裡產生的迷宮地圖包含一個預設版本，沒有任何起點和終點位置，因此您可以自己決定：從迷宮中的任何點到任何其他點都會有一個解決方案。如果您想要靈感，您可以啟用建議的開始和結束位置 - 甚至可以看到兩者之間的解決方案。

關於克魯斯卡爾演算法

克魯斯卡爾演算法是由美國數學家、統計學家和電腦科學家小約瑟夫·伯納德·克魯斯卡爾（Joseph Bernard Kruskal, Jr.）創建的。他於 1956 年在其論文《關於圖的最短生成子樹和旅行商問題》中首次描述了該演算法。

該演算法旨在找到圖的最小生成樹（MST），確保所有頂點以盡可能小的總邊權重連接，同時避免環路。

Kruskal演算法如何產生迷宮

步驟 1：初始化

• 將迷宮中的每個單元格視為一個單獨的集合（一個獨特的組成部分）。
• 列出相鄰單元格之間的所有牆壁作為潛在邊界。

步驟二：對牆壁進行分類

• 將牆壁打亂或隨機排序。如果將其實現為真正的克魯斯卡爾演算法，則按隨機順序對牆壁進行排序（因為迷宮生成不需要權重）。

步驟 3：處理牆體

• 遍歷打亂順序的牆壁。
• 如果被牆隔開的兩個單元格屬於不同的集合（即，它們在迷宮中尚未連接），則移除牆壁並將集合合併。
• 如果它們已經在同一組內，則跳過牆壁（以避免循環）。

第四步：繼續直至完成

• 重複此過程，直到所有單元格連接起來，形成一個生成樹。
• 最後，每個細胞都與其他細胞相連，沒有環路或孤立的部分。

由於 Kruskal 演算法依賴合併集合，因此可以使用並查集演算法對其進行最佳化。並查集演算法提供了一種在迷宮生成過程中追蹤連通單元格的有效方法。您可以在這裡查看我用 PHP 實現的並查集演算法：鏈接

進一步閱讀

如果您喜歡這篇文章，您可能也會喜歡這些建議：

• 狩獵與殺戮迷宮生成器
• 埃勒演算法迷宮生成器
• 威爾遜演算法迷宮生成器