浙江大學-數據結構-應用實例：拯救007-6.3.1

根據現在鱷魚的分布，007有沒有可能通過跳到鱷魚的頭上從而到達岸上？這是一個圖的問題，圖的問題需要兩件事情去確定，什麼是圖的結點，什麼是圖的邊，鱷魚的腦袋肯定是圖裡面的結點，但是我相信很多人忽略了岸邊也是圖裡面的結點，儘管它看上去不像是結點的樣子，我們在說圖的時候，是一個很抽象的概念，圖的結點不一定是圓頭圓腦的東西，它可以是具有某種屬性的對象，那麼什麼是圖的邊呢？圖的邊在我們的問題裡面就是兩頭鱷魚什麼時候有關係呢？就是007可以從一條鱷魚跳到另一條鱷魚的時候，這兩條鱷魚之間就會是有一條邊的，另外還要考慮的是，007並不是為了踩鱷魚玩的，他是為了逃命，所以哪條鱷魚能讓他和岸邊拉上關係，那麼這條鱷魚和安全的岸就是有邊的，這樣我們就建立了一個圖，於是我們這個問題可以怎麼解決呢？

實際上這是圖的遍歷的應用，不管用DFS,還是BFS，只要能在遍歷的過程中發現，有一條鱷魚跟岸邊是有邊的，你就可以直接跳上去，然後告訴它說，yes,你是可以活命的

以原點為圓心，半徑是007的跳躍半徑，加上孤島的半徑，以這個為半徑畫一個圓，然後看有哪些鱷魚落在這個圓裡面，所以在程序裡面，是掃描了一遍全體的鱷魚，然後發現有一條落在圈裡的，這就是我們第一條可以踩上去的鱷魚，所以第一跳就往鱷魚的頭上跳，我們雖然是DFS,BFS都可以，但是從實現的角度來講，顯然是深度優先的比較容易實現，也比較容易理解，那就是說我們跳到鱷魚的頭上，以它為圓心，開始做DFS,遞歸去做下一件事，

下一個圓的半徑就沒有孤島這件事了，這個半徑就是007可以跳躍的最大半徑，以這個半徑畫個圓，我們發現有兩條鱷魚落在它的跳躍範圍之內，假如說他先選擇了右上角的一條

於是程序繼續遞歸，什麼叫遞歸呢？就是以這條鱷魚為圓心，再以它的跳躍半徑畫一個圓，然後再這裡檢查此路不同，

除了往回跳，就是往湖裡跳，所以要原路返回，

到什麼時候為止呢？一直到我們找到下圖的鱷魚的時候，

找到這條鱷魚的時候，雖然發現它還可以跳到下一頭鱷魚的頭上，但是已經沒有必要了，這個圓跟岸邊是有交集的，所以可以從這就跳上岸了，遞歸到這個時候，已經沒有必要再繼續下去了，可以直接跳出返回一個yes

總體演算法

007的第一跳跟其它的跳躍是不一樣的，一個明顯的區別是，第一跳的半徑是不一樣的，所以不方便把第一跳也放在遞歸裡面一起處理，因為我們遞歸的時候基本上是一個重複的同樣的過程，所以希望跳躍的半徑都是一樣的，於是孤島其實應該被作為一個特殊的結點來處理，那在剛才那個圖裡面呢，007的第一跳範圍裡面只有一條鱷魚，這個情況是比較簡單的，但是更複雜一點的測試呢，可能說在它第一跳的範圍裡面，有好幾條鱷魚是可以選擇的，那每一條鱷魚就對應了一個連通集，我們的關鍵就是要看那個連通集裡面，有沒有包含了安全的彼岸這個結點，所以呢，總體演算法不是一個簡單的DFS,而是相當於前一步實現的ListComponents那個演算法，通過在原始的ListComponents演算法上進行改進

對於G裡面的每一個V,如果沒有visited，visited在這裡面是什麼意義呢？在這個故事裡面，visited[V]在這裡面是True,就意味著007已經在這條鱷魚的頭上踩過一腳了，如果他還沒有踩過一腳，那麼我們應該去做DFS,就是一腳踩上去，除此之外，我們還要做一個什麼判斷呢？其實我們的第一跳不僅是看這個鱷魚有沒有被踩過，而且要看007能不能夠得著，所以這個條件裡面還要加一個FirstJump，這個函數的功能就是把V給到這個函數里，它要能告訴我說007的第一跳從孤島跳到這個V上面，有沒有可能，如果這個函數返回的結果是真的話，同時這條鱷魚又沒有被踩過的話，那麼我們就跳上去，那基本上到這裡我們的問題就解決了，稍微有一點細節就是，我們不僅要踩一遍鱷魚，還得告訴007，yes或者no,所以DFS在裡面，不能在像以前那樣是一個void函數，必須要返回一個結果

我們把返回的結果記在answer裡面，就是這個答案，如果這個答案是yes,那麼我不要接著往下做了，直接就跳出來，跳出來，如果這個answer是yes,我們就告訴它是yes,如果到所有的循環都做完了，始終都沒有得到一個yes的答案的話，那麼它就沒救了，你要告訴它no

那麼在這個演算法的偽代碼裡面，有兩個關鍵的函數要實現，一個是FirstJump,這個我就不實現了，很簡單，自己去做，另外一個就是DFS,這個DFS跟我們經典的DFS有什麼不一樣呢？我們來看一下，

這是經典的DFS的偽代碼，它的基本過程再回憶一下，就是我先一腳踩到這個鱷魚的頭上，踩了一腳代表我訪問過了，然後對V的每個鄰接點W,在這個問題裡面，什麼是V的鄰接點W呢？如果這條鱷魚還沒有被踩過的話，那麼我遞歸的踩到這條鱷魚的頭上去，這就是DFS演算法，那麼在我們這個改良的DFS演算法裡面，我們要做點什麼呢？首先一件事情，我要把DFS的返回值改為int,我要返回一個answer,比方說我yes定義為1，no定義為0，那麼我最後要回復它這麼一個結果，其它空著的地方都要去補全代碼的

首先007一腳踩上去了(visited[V]=true)，之後他要做的一件事情，放眼一望，他是要急著找下一條鱷魚嗎？肯定不是的，他最關心的是能不能從這條鱷魚跳到岸上去，

所以在找下一條鱷魚之前，我們先要有一個函數IsSafe,IsSafe這個函數它要做的事情是什麼呢？我把V也就是這條鱷魚的坐標傳給你，你要告訴它說從這個地方能不能直接跳上岸，如果能，返回真，不能，返回假，如果這個IsSafe函數，返回的是真的話，那麼很好，它不用往下跳了，它可以直接answer等於yes,然後就return answer它就回去了，如果這條鱷魚不行，那麼只好去看看其它的鱷魚，當然在檢查其它鱷魚，遞歸的時候，我們要返回一個answer,如果這個answer在任何時候是等於yes的話，我們就break,跳出來直接返回這個answer

那這裡面還有一個問題，就是什麼叫V的每個鄰接點W,也就是說什麼樣的W是跟V直接有邊的呢？這句話(for(V的每個鄰接點W))在我們這個問題裡面應該換成什麼？

其實應該換成的是說，如果這條鱷魚還沒有踩過，並且我們可以從V跳到W上面，所以這裡有一個Jump函數，Jump函數要解決的就是算一下V和W之間的距離，是不是小於007可以跳躍的最大距離，如果可以的話，返回真，那就意味著它真的可以跳上去，在這裡面我們掃描的是G裡面的每一個W,如果可以跳上去，就意味著它有邊，就意味著W是V的鄰接點，如果它沒有被訪問過的話，我們進行DFS

我們最後還有一個問題，我前面說過，我們介紹了圖的兩種表示方法，一種是鄰接矩陣，一種是鄰接表，那麼在這個問題裡面，你覺得是用鄰接矩陣表示好，還是用鄰接表表示好呢？還是其實什麼都不用呢？想好這個問題，再去實現你的程序，其實我的建議你可以幾種方法都試一下，你用鄰接表去表示這個圖，想一下這個事情很麻煩的，你用鄰接矩陣呢，仍然是很麻煩的，所以我要說的是其實一個圖，不一定非要用鄰接表或者鄰接矩陣來表示，怎麼方便怎麼表示就可以，圖只是一個非常抽象的概念，是一個輔助你解決問題的工具