1)要實現(xiàn)的算法

①建立圖的存儲結(jié)構(gòu)

②深度優(yōu)先搜索和廣度優(yōu)先搜索

③求圖的最小生成樹

④拓?fù)渑判?br/>
⑤最短路徑

2)存儲結(jié)構(gòu)設(shè)計

　　本系統(tǒng)采用圖結(jié)構(gòu)（mgraph）存儲抽象操作的信息。其中，各結(jié)點間的鄰接關(guān)系用圖的鄰接矩陣類型（adjmatrix）存儲。頂點信息用結(jié)構(gòu)數(shù)組（vexs）存儲。其中每個數(shù)據(jù)元素師一個結(jié)構(gòu)變量，包括一些基本信息。

此外，本系統(tǒng)還設(shè)置了三個全局變量：visited[]數(shù)組用于存儲頂點是否被訪問標(biāo)記；d[]用于存放邊上的權(quán)值或者是存儲查找路徑頂點的編號；campus是一個圖結(jié)構(gòu)的全局變量

3)功能設(shè)計

　　本程序一共設(shè)置了9個子功能菜單，圖的初始化由函數(shù)initgraph（）實現(xiàn)，依據(jù)讀入的圖的頂點個數(shù)和邊的個數(shù)。分別初始化圖結(jié)構(gòu)中圖的頂點向量數(shù)組和圖的鄰接矩陣。9個功能設(shè)計描述如下：

①建立有向圖。有向圖的建立有由BuildAdjacencyList()實現(xiàn)。當(dāng)用戶選擇該功能時，用戶要手動輸入該圖的信息。從而建立有向圖。

②輸出鄰接表。鄰接表的輸出有函數(shù)ShowAdjacencyList()實現(xiàn)。當(dāng)用戶選擇該項功能時，系統(tǒng)即以鄰接表的形式輸出各頂點所連接的點。

③輸出頂點的度。頂點讀的輸出由函數(shù)ShowAdjacencyListDegree()實現(xiàn)。當(dāng)用戶選擇該功能時，系統(tǒng)即將每個頂點的度以數(shù)字的形式輸出。

④進(jìn)行拓?fù)渑判颉Ｍ負(fù)渑判蚬δ艿膶崿F(xiàn)由函數(shù)TopologicalSortAdjacencyList()完成。一旦選擇，就會進(jìn)行排序并輸出。

⑤深度優(yōu)先遍歷。采用DFS算法進(jìn)行深度優(yōu)先遍歷，遍歷完成后，將遍歷得到的結(jié)點有序輸出。

⑥廣度優(yōu)先遍歷。采用BFS算法進(jìn)行廣度優(yōu)先遍歷，遍歷完成后，將遍歷得到的結(jié)點有序輸出。

⑦無向圖最小生成樹。最小生成樹的算法實現(xiàn)由函數(shù)AdjacencyListPrim()完成。該函數(shù)采用Prim算法對鄰接矩陣求最小生成樹并輸出。

⑧有向圖求最短路徑。最短路徑的實現(xiàn)采用函數(shù)AdjacencyListDijkstra()完成。該函數(shù)采用的是Dijkstra 算法對鄰接矩陣對各頂點到其他頂點的最短距離。并依次輸出。