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

02-25

程序框架搭建

先要在main函數裡面規劃一下到底做哪些事情，就這道題而言呢，我們可以非常簡單的分成兩步，第一步輸入讀進來，並且構建一個圖，然後我要對圖做分析，我要求任意兩點之間的最短路，我要找最短距離的最大值，然後找最大值里的最小值，我都可以把它放在一個模塊里，叫做分析圖，這樣計划了以後，我的main函數直接可以寫成這個樣子

就是我先BuildGraph(),讀入並且建立一個圖，然後下一步分析圖，就取一個名字叫FindAnimal，把找動物這件事交給這個函數去做，有一個細節我們先要考慮一下，這個Graph到底應該是哪一種圖呢？我們知道有兩種圖，一種是用鄰接表，一種是用鄰接矩陣的，那麼就這個問題而言，到底是用哪一種圖是最合適的呢？因為在解決這個問題的時候，我們主要要調用的程序模塊是Floyd演算法，就Floyd演算法而言，顯然我們把圖表示成一個矩陣的形式更加容易做一點，所以在這我們生成的是一個MGraph，也就是一個用鄰接矩陣，來表示的圖，那麼我們要運行這個main函數的時候，基本上就是要準備好兩大模塊，第一個模塊就是關於BuildGraph,如果我們想要讀入並且建立一個圖的話，首先要有MGraph的定義，如果我們想要調用BuildGraph，之前我們先要有一個函數去CreateGraph,就是去建立一個空的圖，然後會不斷的往空的圖裡面去插入邊，就是我們一邊讀輸入，一邊把這個邊插到圖裡去，這兩個模塊都是BuildGraph需要的(即CreateGraph和InsertEdge),那總的來說呢，這個模塊是現成的，我們只要把它搬過來，稍微改一改就可以用了，我們自己真正要實現的呢，是FindAnimal這個模塊，那這個模塊要做的第一件大事，就是先調用一下Floyd演算法，把這個圖裡面任意兩點之間的最短路那個距離矩陣先得到，得到距離矩陣之後呢，我們就是要做FindAnimal這件事情，要找到底應該帶哪只動物去，FindAnimal這個函數涉及到一個求最大距離，一個求最小距離的問題，也就是說我先要對第i個動物去求它所有最短距離裡面的最大值(即FindMaxDist(i))，然後我要求所有這些最大值裡面的最小值(即FindMin),然後把最小值交給FindAnimal函數最後去輸出，這個就是程序的整個框架。