迷宮

從小時候，我就對許多益智遊戲感到興趣。

一種簡單的遊戲是「走迷宮」：玩的人要從一個迷宮的某一點，走到另一點。一個典型的平面方陣迷宮，就如同右圖所示。

那麼，如何用程式來產生這樣的迷宮呢？

乍看之下，似乎不是那麼容易。然而，如果有一些圖論 (graph theory) 的背景，會發現其實是有相當漂亮的方法，來產生這類迷宮的。

將迷宮的每一方格視為一個節點 (node)。相鄰兩格若有路相通，則說此兩節點間有個連結 (link)。如此一來，迷宮中每個小方格最多會有四個（上、下、左、右）相連結的節點。要產生一個迷宮，只要任選一個小方格，再由此方格向外伸展連結， 產生一個樹狀結構 (tree structure) 來涵蓋所有的格子，就可以了。

由於在抽象模型上，我們是用 tree 來表示 (represent) 此迷宮，因此這個迷宮也會有一些有趣的性質。例如，迷宮中的任兩個方格，之間必然、且僅有一條路徑相通。