Kruskal 演算法迷宮生成器

Kruskal 演算法是一種最小生成樹演算法，可以適用於迷宮生成。它對於創建完美的迷宮特別有效。 Kruskal 演算法的替代演算法是 Prim 演算法，這也是一種最小生成樹演算法，但由於它們產生相同的迷宮並且 Kruskal 演算法運行速度更快，因此我沒有費心實現 Prim 演算法。

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

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

關於 Kruskal 演算法

Kruskal 演算法是由美國數學家、統計學家和電腦科學家 Joseph Bernard Kruskal, Jr. 創建。他於 1956 年在論文「圖的最短生成子樹和旅行商問題」中首次描述了該演算法。

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

Kruskal 演算法如何產生迷宮

步驟 1：初始化

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

第 2 步：對牆壁進行分類

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

步驟 3：流程牆

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

步驟 4：繼續直至完成

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

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