【正文】 [2] 嚴(yán)蔚敏，吳偉民 . 數(shù)據(jù)結(jié)構(gòu)題集 (C語言版 ) .清華大學(xué)出版社 .2021 年 5月。 算法時間復(fù)雜度 圖的創(chuàng)建：時間復(fù)雜度為 O(n)。 case 8: cout請輸入你要添加的 e條邊以及邊上對應(yīng)的權(quán)值 !endl。 cinxy。 case 4: (G)。 break。 int choice。 cout║ ║ \n。 int n,e。 cout ┃ 姓名： xxxx ┃ \n。 if(n==nodecount)//訪問到的節(jié)點數(shù)與頂點數(shù)是否相等 return 1。 colnodecount。i++) v[i]=0。i++) { cout頂點 i的度： m[i]endl。 for(k=0。 edgecount++。 } int Graph1::getWeight(int x,int y)//獲得某條邊的權(quán)值 { return b[x1][y1]。 i()。 } } 輸出操作 本函數(shù)通過傳過來的對象 G 得到相關(guān)數(shù)組，通過 for 循環(huán)來分別輸出頂點數(shù)組和 邊的權(quán)值數(shù)組（ 鄰接 矩陣） 。 i++ ) { cout\n i+1: 。k++) a[k]=1。 Graph1::Graph1(int s=MaxNode)//構(gòu)造函數(shù) { for(int i=0。//獲得某條邊的權(quán)值 int Depth(int )。//構(gòu)造函數(shù) int getNodeCount()。輸出節(jié)點個數(shù) 輸出函數(shù)： void PrintOut(Graph1 G) 。得到 當(dāng)前的邊數(shù) 插入函數(shù)： void insertNode(int)。n)。//當(dāng)前的節(jié)點數(shù) int getEdgeCount()。在類中數(shù)據(jù)成員有 4 個，重要的是鄰接矩陣 Edge[ ][ ]、總邊數(shù) edgecount 和頂點數(shù) nodecount。 2 概要 設(shè)計 ADT 描述 ADT Glist { {VR}={圖的頂點和邊 } VR={v,w | v,w∈V, v,w 表示頂點 v 和 w 間的邊； } 基本操作： 初始化空圖； 輸入建立圖 ； 深度優(yōu)先遍歷圖； 確定圖中的頂點數(shù)目； 確定圖中邊的數(shù)目； 在 圖中插入一個頂點； 在圖中插入一條邊； 無向圖的鄰接矩陣存儲結(jié)構(gòu) 5 / 20 刪除圖中一個頂點 刪除圖中的一條邊； 求頂點的度； 求最小生成樹； } ADT Graph。其次是概要設(shè)計，說明所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次關(guān)系，以及 ADT 描述。 然后是詳細(xì) 設(shè)計，描述 實現(xiàn)概要設(shè)計中定義的基本功操作和所有數(shù)據(jù)類型 ，以及函數(shù)的功能及代碼實現(xiàn)。 程序模塊結(jié)構(gòu) 主 函 數(shù) m a i n創(chuàng) 建 函 數(shù)菜 單邊 的 插 入 函 數(shù) 頂 點 的 插 入 函 數(shù) 求 頂 點 的 度 最 小 生 成 樹 輸 出 函 數(shù) 深 度 遍 歷 函 數(shù) 判 斷 連 通 函 數(shù) 圖 ：模塊結(jié)構(gòu) 結(jié)構(gòu)體定義 本系統(tǒng)未采用結(jié)構(gòu)體方法，類的定義如下： 定義頂點 : nodecount， edgecount 邊：已經(jīng)分別存放頂點和邊的兩個數(shù)組： a[MaxNode]和 b[MaxNode][MaxNode]。 無向圖的鄰接矩陣存儲結(jié)構(gòu) 6 / 20 class Graph1 { private: int nodecount。//當(dāng)前的邊數(shù) void insertNode(int)。//深度遍歷 void outDu(Graph1 G)。插入一個節(jié)點 插入函數(shù)： void isertEdge(int ,int ,int)。輸出圖 構(gòu)建函數(shù)： void CreatG(int n,int e)。//當(dāng)前的節(jié)點數(shù) int getEdgeCount()。//深度遍歷準(zhǔn)備，用于建立頂點訪問數(shù)組 和記錄所訪問頂點個數(shù) void Depth(int v,int visited[],int amp。i=s1。 } 圖的構(gòu)建 操作 在主函數(shù)中要求輸入需要構(gòu)建的圖的頂點數(shù)和邊數(shù)，調(diào)用構(gòu)建函數(shù)，分別用兩個 for 語句來構(gòu)建圖（即輸入頂點的值和邊的權(quán)值），此處要 求輸入有一定的順序，不能隨意輸入。 cina[i]。 void Graph1::PrintOut(Graph1 G) { int i。 i++ ) { coutendli+1: 。 } 插入操作 插入頂點： 通過將傳來的值（頂點值）賦到一個當(dāng)前頂點數(shù)下一個的數(shù)組元素中實現(xiàn)插入功能，此時頂點樹加 1。 } 刪除操作 將相應(yīng)的數(shù)組值賦為 0 從而達(dá)到刪除目的。k()。 } } 深度遍歷操作 圖的深度優(yōu)先遍歷 DFS 算法是沿著某初始頂點出發(fā)的一條路徑，盡可能深入地前進(jìn)，即每次在訪問完當(dāng)前頂點后，首先訪問當(dāng)前頂點的一個未被訪問過的鄰接頂點，然后去訪問這個鄰接點的一個未被訪問過的鄰接點，這是一個遞歸算法。 Depth(node,v,n)。 col++) { if (b[v][col]==0||b[v][col]==Max) continue。 else return 0。 cout ┃ 學(xué)號： xxxxxxxxx ┃ \n。 cinne。 cout║ 請選擇您要的操作： ║ \n。 coutendl。 case 3: int node。break。 (x,y)。 cinxyw。 深度遍歷 : 時間復(fù)雜度為 O(n)。 [3] 楊秀金，數(shù)據(jù)結(jié)構(gòu) (C++版 ) .高等教育出版社 .2021 年 4 月 。