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

上次說到C實現哈利波特的考試，有了之前的那些函數，要把它們結合起來，最後我們來看一下線程模塊的引用與裁剪，那麼在這道題目裡頭，我們可以線程調用的模塊有5個，那我們從MGraph的定義開始，這個是我們MGraph定義的程序頭

那這裡頭我們唯一需要刪掉的就是頂點存儲的數據，那在我們這個問題裡面呢，每一個頂點代表的是一個動物，那我們又不存動物的名字，所以這個定義是可以刪掉的

剩下的邊的定義沒有什麼好說的，我們需要邊的兩個頂點和它的兩個權重，這個都沒問題，在圖結點的定義裡面，多餘的就是頂點的數據

因為頂點不存數據，所以這兩行是可以刪掉的，接下來我們看CreateGraph

這個是CreateGraph的原始代碼是沒有任何地方需要改的，我們這裡做的只是初始化一個有VertexNum個頂點但沒有邊的空的圖，唯一需要注意的是默認的頂點編號是從0開始的，

插入邊的模塊也是可以直接引用不需要做任何改動的，因為它是一個無向圖，所以我們要把讀進來的權重同時賦給矩陣裡面的兩個元素，那接下來就到了最關鍵的BuildGraph，我們要從輸入讀進數據來建立起一個圖，首先讀頂點的個數，建立一個空的圖，然後讀入邊的個數，如果邊數不為0，就是有邊的話，那我們創建一個新的邊的結點，然後就把邊的數據讀進來，查到圖裡面去，最後如果頂點有數據的話，還要讀入頂點的數據，那在這個問題裡頭呢，我們頂點沒數據，所以這塊整個可以刪掉

上面Vertex V也是不必要的，這一行也可以刪掉，接下來的一個細節問題就是注意當我們往這個圖裡面去插入邊的時候，這個圖默認的頂點編號是從0開始的，而當我們從輸入裡面把這個邊讀進來的時候，動物的編號是從1開始的，所以在這個地方我們是不能直接插入邊的，其實我們這的調整非常簡單只要加這麼一行就好了。

就把我們讀進來的編號全部都減1就對了，如果我們讀進來的動物編號是1的話，在這我們就把它變成0，這個編號如果是2的話，在這我就把它變成1，所以當我們讀進來一個邊從1到2的時候，存到圖裡面的時候，我們存的這條邊是從0到1的，最後是Floyd演算法

標準的Floyd演算法不僅要計算出任意兩個頂點之間的最短距離這個數值，同時還要記錄它們之間的路徑，而在我們這道題裡頭，是不需要記錄路徑的，所以所有跟path相關的句子都可以刪掉，

還有一個判斷是說Floyd演算法為什麼要返回一個Bool值呢?一般情況下，它是可以正常結束的，如果正常結束的話，我們就返回一個true,表示這個時候是正常結束的，什麼時候非正常結束呢？就是當出現負值圈的時候，我們怎麼知道有負值圈存在呢？就是當i == j的時候，也就是距離矩陣的對角元D[i][j]如果是一個負數的話，那就意味著從i出發走了一圈又回到i，這個最短距離是一個負的值，也就是對應了一個負值圈，那麼如果圖裡面有負值圈的話，Floyd演算法是不能正確得到結果的，這個時候我就不往下做了，直接return false,但是在我們這個題目裡頭，其實這個判斷是不需要的

因為我們保證輸入的所有距離都是正的，它永遠返回的都是true,那麼這個bool值也是沒有必要的，直接把bool改成void函數就可以了

到此為止，我們已經準備好了所有的代碼，剩下的事情就是把這些代碼按照正確順序拼湊起來。