利用不相交集類制作迷宮遊戲（資料結構課程設計——迷宮老鼠）

之前大一的時候有幾天閑來無事，為了學習做了一個可以自動生成迷宮，可以尋找最短路徑的小遊戲，現在整理分享一下

簡單介紹：

利用不相交集類考慮一個迷宮的生成，一個簡單算法就是從各處的牆壁開始（除入口和出口之外）。此時，不斷地随機選擇一面牆，如果被該牆分割的單元彼此不聯通，那麼就把這面牆拆掉。重複這個過程直到開始單元和終止單元聯通，那麼就得到一個迷宮。實際上不斷的拆掉牆壁直到每個單元都可以從其他單元到達更好（這會使迷宮産生更多誤導的路徑）。

整理一下迷宮的生成算法就是：

（1）将迷宮初始時看成一個一個的Box,每個Box在都是隻有一個元素的等價類；

（2）不斷的随機選擇一面牆，如果被該牆分割的單元彼此不通（不是一個等價類），那麼拆掉該牆，

将牆兩邊的 等價類合并成一個等價類；

（3）如果左上角和右下角的方塊屬于同一個等價類，那麼迷宮完成。

這裡用于判斷不同單元是否在同一集合的資料結構即為不相交集類。

等價類基本知識：

即我們要建立多個等價類，聯通的元素放在同一個等價類裡面。

對應的，需要兩個操作：

将兩個元素放到一個等價類裡的話，采用union操作。

查找某個元素在哪個等價類裡，采用find操作。根據find的傳回值可以判斷兩個元素是否在一個等價類裡。

可以用數組來記錄，或者是vector。

舉個例子看可能比較清楚：

假設元素ID剛開始為 0 1 2 3 4 5 6 7 8 9

建立相同大小的數組s，數組初始化值均為-1。

最直覺的處理，比如union(4,5)即使s[5] = 4。（約定union(x,y)使得s[y]=x，效果是相同的）。

find(4)會直接傳回4本身，因為s[4]<0。

而find(5)則遞歸調用，實際上為:find(5) = find(s[5]) = 4，是以判斷出4，5屬于同一個等價類（我覺得可以了解為4這個結點即為等價類的代表）。

find最壞情形運作時間為O（N），因為對N個元素，有可能建立一個深度為N-1的樹。

是以對union和find操作都進行了改進。

另外：

為了控制樹的深度，可以重寫union的方式，比如unionBySize,unionByHeight，這裡就不說了。此時find運作時間為O(N)。

對于find巧妙的改進是路徑壓縮，即當find（x）調用時，修改遞歸找到的結點直接指向等價類的代表結點，使得路徑上的結點移近根結點，這樣下次調用時就很快了。

這種資料結構實作起來很簡單，每個例程隻需要幾行代碼，而且可以使用一個簡單的數組。

實作代碼 :

迷宮生成以及尋找最短路徑的算法部分：

java界面部分就不多說了，完整的代碼下載下傳位址：

<a href="http://download.csdn.net/detail/sunmc1204953974/8609239">http://download.csdn.net/detail/sunmc1204953974/8609239</a>

原創文章，手寫代碼，轉載請注明來源

<a href="http://blog.csdn.net/sunmc1204953974">http://blog.csdn.net/sunmc1204953974</a>