浙江大學-數據結構-圖:小白專場：C實現哈利波特的考試-7.2.1

小白專場：哈利波特的考試

如果harry要把一隻貓變成一隻老鼠的話，他要念的咒語是haha,如果它要把一隻老鼠變成一條魚的話，它要念的咒語是hehe,如果他要把貓變成魚的話，有兩種選擇，一種是先haha一下把它變成老鼠，再hehe一下變成魚，或者它還有另外一條捷徑，就是念另外一條咒語lalala,就直接把貓變成了魚，為什麼說這個是捷徑呢？我們衡量一個路徑的長短，是以字元串的長度為標準的，haha加上hehe,這一共是8個字元，lalala一共是6個字元，所以這是更短的一條路徑，

當然在這道題目裡頭，既可以念一聲haha,把貓變成老鼠，也可以把它反過來念，念ahah,把老鼠變回到貓，所以這是一個雙向的，所以整個圖是一個無向圖，每種動物就是圖裡面的一個結點，然後每一條無向邊上面的是有一個權重的，所以它是一個網圖，這個權重就等於字元串的長度，那麼下面我們的問題就來了，harry要去考試，他只能帶一隻動物去，他應該帶誰去比較合算呢？那我們就來挨個的看一下，比如說他帶這隻貓去，那麼如果老師讓他變出一隻老鼠的話，他需要念一段4個字元長度的咒語，如果老師讓他變出一條魚的話呢？他有兩種變法，那在裡面我們假設harry是最聰明的，他永遠都會選擇最短路，所以他會直接念lalala,把貓變成魚，那麼就貓而言，從它的出發點最難變的動物是魚，因為它需要的路徑比較長一點，那同理，如果帶這條魚去的話呢，它需要4個位元組變成老鼠，6個位元組變成貓，所以對於魚來說，最難變的動物就是一隻貓，如果我們帶老鼠去呢，它無論是變成魚還是變成貓都只需要念4個字元，所以顯然帶老鼠過去就行了

再來看一個稍微更複雜的例子，這是這道題目給出的樣例

前面的兩個數字，第一個6是表示動物的個數，就是圖裡面頂點的個數，後面11代表邊的個數，接下來每一行給出了一條邊，對應的就是無向的網圖，這個圖比剛才那個圖要複雜的多了，我們很難一眼看出來帶哪只動物去是最合算的，那我們第一件要做的事情，是不是應該首先把任意兩個動物之間的最短路徑找出來，那麼要找一個圖裡面任意一對頂點之間的最短路徑，我們應該用什麼演算法呢？很顯然，就應該用剛剛講完的Floyd演算法是最合適的了，

通過直接調用這個演算法，我們會得到最短距離的矩陣，我們把這個矩陣叫做D,那麼 記錄的就是從頂點i到頂點j之間的最短距離，

比方說這個120是什麼意思呢？它是第3行第5列，意味著從頂點3到頂點5之間的最短距離是120，就是會記錄在 的位置，那要注意到，動物的編號是從1開始的，那要回答harry究竟要帶哪只動物去的問題，怎麼做呢？首先檢查每一行裡面最大的數字，這一行裡面最大的數字代表的是什麼呢？就比方說第一行裡面最大的數字，是81，就意味著第一個動物變成第5個動物是最麻煩的，從1變到5的距離最長，那麼到底應該帶哪個動物去使得我們最難變的動物是最好變的呢？那就是從我們圈出來的6個最大值裡面，要找最小值

就在這，70，也就是說如果我們把4號帶過去的話，那麼他最困難的一個動物是要變成3，那最困難的咒語長度是70，這已經是所有其它最困難咒語裡面最容易的一個了，結論就是我們應該帶4號動物去，最難變的咒語長度是70，所以我們抽象的來總結一下，給了一個無向的網圖，我們要用Floyd演算法去算任意兩點之間的最短路徑，然後我們要對每一個頂點去掃描它到其它頂點的最短路徑裡面的最大值，把這個最大值記下來以後，我們要去找所有頂點裡面最大值裡面最小的那個值。

推薦閱讀：