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

先來看怎麼實現FindAnimal這個函數，傳進去的是讀進來的圖，首先要做的第一件事情是調用Floyd演算法，把這個圖Graph給它，然後得到這個距離矩陣D,接下來我可以把FindMin寫成一個函數，也可以把FindMin寫在函數裡面，總之這個模塊要做的事情是從每個動物i它最短距離的最大值裡面找到最小的東西，我們把它定義成MinDist,最小距離，以及這個最小距離對應的動物的編號Animal,它執行完了以後，我們就要輸出動物的編號，以及它的最小距離，本質上來說FindMin就是從一堆數字裡面找最小值，訣竅就是把最短距離定義為很大很大的數(MinDist=INFINITY),把它初始化成無窮大，然後我就開始掃描每一個動物，i從0一直到Graph->Nv,對每一個動物i我調用另外一個函數FindMaxDist，找到第i個動物它的最大的距離賦給MaxDist這個變數，然後把這個最大的距離去跟我要求的最小距離比一下，如果這個距離是一個更小的距離的話，那我就找到了最長距離更小的動物，這樣我把MinDist更新成為當前動物的距離，然後記錄一下動物的編號，為什麼這個動物的編號是i+1,而不是i呢？你要注意一下，在這道題目裡面，輸入的時候是從1開始編號的，而在一個圖裡面，它的頂點是從0開始編號的，這裡是一個很小的細節，要注意處理一下，總之我如果找到了一個更小的距離的話，我就更新這個距離，並且記錄當前這個更小距離它動物的編號，我從這個for循環裡面跳出來以後，就掃描完了所有的動物，就得到了最小的動物和最小距離，在這我還空了一塊，是幹什麼用的呢？

是我們還有一種特殊情況要考慮的，就是你帶一隻動物去根本就不可能，什麼時候是這種情況呢？就是當圖根本不連通的時候，圖有不止一個連通集，所以帶一隻動物去是不可能的，那麼我什麼時候能意識到這個圖是不連通的呢？就是當我返回的MaxDist是無窮大的話，就說明從這個動物i到其它動物的最大距離是無窮大，就意味著從i開始至少存在一個動物，是它沒有辦法變出來的，所以我直接輸出一個0, 就回去了，剩下的細節就是你這邊需要什麼變數要申明一下，那這就是我們實現FindAnimal函數的辦法。

當然這裡面還有一個小的函數叫FindMaxDist,非常簡單的，它就是從一堆數據里找一個最大值

找最大值的訣竅就是先把MaxDist初始化成一個很小的數，比如是0，然後你就開始對動物i來說，你就掃描它的第i行，當j在變化的時候，如果某一個第i,j比當前的最大距離還要大的話，那我就更新一下它的最大距離，為什麼在(if( D[i][j]>MaxDist))還空了一塊東西呢？這又是一個特殊情況要考慮的，就是對角元我們是怎麼定義的，如果你還記得鄰接矩陣初始化怎麼做的話，最開始的時候所有的兩個頂點之間的距離全部都初始化為正無窮的，所以對角元的值永遠是正無窮，如果在比較的過程中我們不把對角元排除掉的話呢，一讀到對角元的時候肯定是大於MaxDist的，MaxDist永遠會返回正無窮，那就錯了，所以在比較之前，要先加一個判斷，當i !=j的時候，

才做這樣的判斷，就把對角元跳過去了。