演算法雜談：DFS

DFS，一個有趣的玩意。

說點實在的，演算法這種東西，其實也包括所有知識，還是腳踏實地比較好。有時候，一些人總是不懂裝懂，濫竽充數，說起人工智慧什麼的，好傢夥，說得天花亂墜，其實連最基礎的排序演算法都琢磨不透，或者背了幾段代碼就開始胡嘴了。檢測一下，排序真的是想像的這麼容易嗎？

有時候，總會感覺演算法太虛了，不知道哪裡有用武之地，除了OI或者ACM，似乎在平常很難用到演算法。因為現階段做的東西還是太簡單。

但對於DFS，我試了一下，發現迷宮是一個不錯的載體（畢竟是找路）

先說一下DFS到底是什麼吧。

DFS（Depth first search）深度優先搜索

1.從圖中某個頂點v0出發，首先訪問v0;

2.訪問結點v0的第一個鄰接點，以這個鄰接點vtvt作為一個新節點，訪問vtvt所有鄰接點。直到以vtvt出發的所有節點都被訪問到，回溯到v0的下一個未被訪問過的鄰接點，以這個鄰結點為新節點，重複上述步驟。直到圖中所有與v0相通的所有節點都被訪問到。

3.若此時圖中仍有未被訪問的結點，則另選圖中的一個未被訪問的頂點作為起始點。重複深度優先搜索過程，直到圖中的所有節點均被訪問過。

如果文字不好閱讀，則看看下面的圖片吧

GIF

通俗來講，就是先一路走到底，發現死路一條，就回到原來那個節點，換一條路繼續走，直至走到終點。而回到節點的那個過程，我們稱其為回溯。

如果你在玩《爐石傳說》，裡面那個冒險模式《女巫森林》，當你用時光修補匠Toky的時候，每個回合你都可以重新開始你的回合，你可以大致想像它為回溯。

原理應該說比較簡單，因為小時候我們玩迷宮遊戲的策略不大多如此嗎？但原理簡單，不一定應用簡單。

所以，來做一個走迷宮模擬吧。先看看生成效果，感覺有點粗糙。

GIF

關於迷宮生成，這裡也是用的DFS，其實也可以用prim演算法，但是感覺有點太隨機惹，我還是比較鍾情於看似隨機，其實暗藏規律，這樣的情景賽高。

說真的，在隨機里找規律的過程很痛苦，但會給你一種奇怪的快感，噢噢哦，好爽♂

上面不是我說的，是hw說的，一個弟弟，請無視。

Back to the topic,這個過程其實細節很多。先上代碼，不多談。

其中，因為數據結構還沒有學，只能用數組將就著存數據，很low很業餘。。。也請無視

先做個簡要聲明，path是用來記錄路徑上每個點的橫縱坐標，count1表示節點個數，count2表示終點。DFS是函數體。

這裡我覺得有幾個重點，不是DFS演算法本身，而是在運用DFS時所遇見的問題。

首先，是這個ss，它是記錄count1的值的，為什麼要當中放一個ss存儲count1呢，後面回溯的時候count1的值會發生變化，所以在檢測到終點時，應該立刻檢測。

其次，為什麼要多設一個數組path呢?一開始時，我沒有設成二維數組，但後來結果總是出錯。然後我設置斷點發現了原因。後來回溯時的坐標節點會重新被賦值給數組元素，這就導致原來解謎路上記錄的坐標丟失了，自然也就失敗了。

現在是回溯階段，類似於遞歸。當回到原來那一點的時候，就好像時光倒流一樣，所有事物的狀態回到那個時候的狀態。就像這裡，經過一次DFS後，我們需要思考兩個狀態之間到底哪裡不一樣。

1、多計算了一個節點

2、給相應的數組元素賦值了

我們只需要逆向調整這兩點就OK了

當然，我現在說得很輕鬆，當時我找bug的時候可是心態爆炸。想像一下一個人對著電腦一直說wsngg的場景，差不多了。

其實，就個人感受來說，就演算法來說，懂得它的數學原理只是第一步，然後是偽代碼，如果真的要檢測自己到底有幾斤幾兩，OJ——請，或者做一個用得到演算法的小玩意，千萬不要為了一時嘴快，說的比嘴上多，到最後，會發現什麼都不懂，真的丟人。

又到了最後了，我介紹一個有意思的網站

我前面用的DFS的動畫來自這裡，一個幫助你直觀理解演算法的網站。

VisuAlgo是由Steven Halim博士在2011年發布的一款可視化學習演算法的工具，用於幫助其學生更好地理解數據結構和演算法，可以讓學生按自己的步驟來學習。上圖是VisuAlgo的主頁，不得不說我上去體驗後感覺很有趣，很適合對基礎演算法的學習和了解，是一個找到後令人驚喜的網站。

關於封面

雖然陰陽師早就退坑了，但對於躺贏花還是很喜歡的，那時候上分全靠花姐，2333

歡迎各位和我交流，thx

能關注就更好惹

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！