【正文】 / 點 。 插入和刪除弧 InsertArc(amp。一旦 visit()失敗，則操作失敗 BFSTraverse(G, Visit())。 ID(vi )=? A[ j ][i ] 頂點的 度 =第 i行元素之和 +第 i列元素之和 , 即： TD( vi ) = OD( vi ) + ID( vi ) v1 v2 v3 v4 A 鄰接矩陣： A= ( v1 v2 v3 v4 ) v1 v2 v3 v4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 注： 在有向圖的鄰接矩陣中， 第 i行含義：以結(jié)點 vi為尾的弧 (即出度邊）； 第 i列含義：以結(jié)點 vi為頭的弧 (即入度邊）。對無權(quán)圖 , //用 1或 0表示相鄰否 。 // 圖的當前頂點數(shù)和弧數(shù) GraphKind kind。i。k。//弧 v1,v2的權(quán)值 If(IncInfo) Input(*[i][j].info)。 // 該弧相關(guān)信息的指針 } ArcNode。 圖的結(jié)構(gòu)定義 2022/3/13 53 分析 1: 對于 n個頂點 e條邊的無向圖 ，鄰接表中除了 n個頭結(jié)點外，只有 2e個表結(jié)點 ,空間效率為 O(n+2e)。 ④ 鄰接矩陣的空間復(fù)雜度為 O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。 ArcBox *firstin, *firstout。 V1 V2 V3 V4 V1 V2 ∧ V3 V4 0 1 0 2 ∧ 2 0 2 3 ∧ ∧ 3 0 ∧ 3 1 ∧ 3 2 ∧ ∧ 0 1 2 3 2022/3/13 60 四、無向圖的鄰接多重表存儲表示 typedef struct Ebox { VisitIf mark。 頂點的結(jié)構(gòu)表示 typedef struct VexBox { VertexType data。 2. 如何判別 V的鄰接點是否被訪問？ 深度優(yōu)先搜索（遍歷）步驟： 簡單歸納： ? 訪問起始點 v。 VisitFunc(v)。 w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w)。 v。 其中， Vw1, Vw2, Vw8 的路徑長度為 1； Vw7, Vw3, Vw5 的 路徑長度為 2； Vw6, Vw4 的路徑長度為 3。 // 置空的輔助隊列 Q for ( v=0。 w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]=TRUE。T){ T=NULL。 //給該結(jié)點賦值 if (!T) T=p。 For(w=FirstAdjVex(G,v)。 DFSTree(G,w,q)。 2022/3/13 101 (連通網(wǎng)的 )最小生成樹 假設(shè)要在 n 個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個城市只需要修建 n1條線路， 如何在最節(jié)省經(jīng)費的前提下建立 這個 通訊網(wǎng) ？ 問題： 2022/3/13 102 構(gòu)造網(wǎng)的一棵最小生成樹（ Minimum Cost Spanning Tree），即： 在 e 條帶權(quán)的邊中選取 n1 條邊（不構(gòu)成回路），使“ 權(quán)值之和 ”為最小 。 // U集中的頂點序號 VRType lowcost。 i。 2022/3/13 111 具體做法 : 先構(gòu)造一個只含 n 個頂點的子圖 SG，然后從權(quán)值最小的邊開始，若它的添加不使 SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n1 條邊為止。 } 2022/3/13 114 普里姆算法 克魯斯卡爾算法 時間復(fù)雜度 O(n2) O(eloge) 稠密圖 稀疏圖 算法名 適應(yīng)范圍 比較兩種算法 定義： 無環(huán)的有向圖 用途： 是描述 含有公共子式 的表達式的有效工具。若?？諘r輸出的頂點個數(shù)不是 n， 則有向圖有環(huán)；否則，拓撲排序完畢 在算法中需用定量的描述替代定性的概念： 沒有前驅(qū)的頂點 ?? 入度為零的頂點 刪除頂點及以它為尾的弧 ?? 弧頭頂點的入度減 1 為避免每次都要搜索入度為零的頂點，在算法中設(shè)置一個“?！保员４妗叭攵葹榱恪钡捻旤c。 //g[0]不用 掃描頂點表，將入度為 0 的頂點入棧； while ( 棧非空 ) { 將棧頂頂點 v彈出并輸出之； 檢查 v的出邊，將每條出邊 v,u終點 u的入度減 1， 若 u的入度變?yōu)?0，則把 u推入棧； } 若輸出的頂點數(shù)小于 n，則輸出“有回路”；否則拓撲 排序正常結(jié)束。 //對輸出頂點計數(shù) while (! StackEmpty (S)) { Pop(S, i)。//該有向圖有回路 Else return OK。 p。 for ( i=0。 表頭結(jié)點： typedef struct tnode { int in。 關(guān)心兩方面問題： 工程能否順利進行。 // k 計選中的邊數(shù) while (kn1) { ++i。 // 輸出生成樹上一條邊 closedge[k].lowcost = 0。 j。 在添加的頂點 w 和已經(jīng)在生成樹上的頂點 v 之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點 v 和 w 之間的邊中取值最小 。 例如對圖 63(a)所示有向圖，從頂點 v1出發(fā)作深度優(yōu)先遍歷，在訪問頂點v2后，頂點 v2不存在未訪問的鄰接點從而成為一個 “ 死結(jié)點 ” ，如 圖 (b)所示。 If(first){Tlchild=p。 //建立以 p為根的生成樹 }} //DFSForest A B L M C F D E G H J K I ^ A ^ T p q 建立無向圖 G的深度優(yōu)先生成森林的孩子兄弟鏈表。 for(v=0。 ?對于 非連通圖 ，則需從 多個頂點 出發(fā)進行搜索，每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個 連通分量中的頂點集 。 // 訪問 v EnQueue(Q, v)。 ? 廣度優(yōu)先遍歷算法 開始 標志數(shù)組初始化 Vi=1 Vi訪問過 BFS Vi=Vi+1 Vi==Vexnums 結(jié)束 N N Y Y 開始 訪問 V0,置 標志 求 V鄰接點 w w存在嗎 V下一鄰接點 ?w w訪問過 結(jié)束 N Y N Y BFS 初始化隊列 V0入隊 隊列空嗎 隊頭 V出隊 訪問 w,置 標志 w入隊 N a a Y 2022/3/13 85 void BFSTraverse(Graph G, Status (*Visit)(int v)){ for (v=0。 – 采用二維數(shù)組： O(n2) – 采用鄰接表： O(n+e) 基本思想： —— 仿樹的層次遍歷過程 。 for (v=0。 // 對 v的尚未訪問的鄰接頂點 w // 遞歸調(diào)用 DFS } // DFS V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍歷： V1? 1 2 3 4 V1 V3 V4 V2 vexdata firstarc 2 7 8 3 ^ ^ ^ adjvex next 5 V5 6 4 1 ^ 5 1 2 8 2 ^ V6 V7 V8 6 7 8 7 3 6 3 5 4 ^ ^ ^ V3 ? V7 ? V6 ? V2 ? V5 ? V8 ? V4 DFS(Graph G, int v){ visited[v] = TRUE。 如果有 ， 則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問； 如果沒有 ， 就 再退回一步 進行搜索。 深度優(yōu)先搜索 廣度優(yōu)先搜索 2022/3/13 65 從圖中某個頂點 V0 出發(fā)，訪問此頂點，然后 依次從 V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖 ， 直至圖中所有和 V0有路徑相通的頂點都被訪問到。 // 該邊信息指針 } EBox。 //有向圖的當前頂點數(shù)和弧數(shù) } OLGraph。 InfoType *info。 — 它其實是對鄰接矩陣法的一種改進 怎樣計算無向圖頂點的度？ 鄰接表的 缺點： 鄰接表的 優(yōu)點： TD(Vi)=無向圖中頂點 Vi的度為第 i個單鏈表中的結(jié)點數(shù) 空間效率高； 容易尋找頂點的鄰接點； 判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。 data firstarc 頂點的結(jié)點結(jié)構(gòu) 2022/3/13 52 typedef struct { AdjList vertices。 2022/3/13 49 A B E C D 有向圖的逆鄰接表 A B C D E 3 0 3 4 2 0 ? ? ? ? ? 0 1 2 3 4 在有向圖的鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。w)。++i)//初始化鄰接矩陣 For(j=0。,amp。 define INFINITY INT_MAX //最大值 ∞ define MAX_VERTEX_NUM 20 //最大頂點個數(shù) Typedef enum{ DG, DN, UDG, UDN} GraphKind。 討論 3 ： 有權(quán)圖（即 網(wǎng)絡(luò) ）的 鄰接矩陣 表示。 v1 v2 v3 v5 v4 A 0 0 0 0 0 00 0 00 0 0 0 00 0 0 0 1 11 0 1鄰接矩陣： A= 討論 2 ： 有向圖的鄰接矩陣表示。G, v, w)。 //在圖 G中增添新頂點 v。 對鄰接點的操作 FirstAdjVex(G, v)。G)； // 銷毀圖 結(jié)構(gòu)的建立和銷毀 對頂點的訪問操作 LocateVex(G, u)。 簡單回路 :除了第一個頂點和最后一個頂點之外，其余頂點不重復(fù)出現(xiàn)的回路。 圖 G 圖 G? A C D F E 例如 : TD(B) = 3 TD(A) = 2 邊 (v, v’) 依附 于頂點 v 和 v’，邊 (v, v’)和頂點 v 和 v’ 相關(guān)聯(lián) 。 例如 : G1 = (V1, VR1) 其中 V1={A, B, C, D, E} VR1={A,B, A,E, B,C, C,D, D,B, D,A, E,C } A B C D E 頂點 (Vertex)：圖中的數(shù)據(jù)元素。 (a1, …, ai1, ai, …, an) 知識回顧 (20221127 week 10 fri) 在 樹形結(jié)構(gòu) 中，數(shù)據(jù)元素之間有著層次關(guān)系，每一層上的數(shù)據(jù)元素可能和下一層中多個元素相關(guān)，只能和上一層中一個元素相關(guān)。 Graph = (V , R ) 其中， VR＝ {v,w| v,w∈ V 且 P(v,w)} v,w表示從 v 到 w 的一條弧，并稱 v 為 弧頭 ， w 為 弧尾 。 1 2 3 4 1 2 3 4 無向完全圖 有向完全圖 A B E C F 有兩個圖 G=(V,{E}) 和圖 G?=(V?,{E?}), 且 V??V, E??E, 則稱 G? 為 G 的 子圖 。 路徑上邊的數(shù)目稱作 路徑長度 。 數(shù)據(jù)關(guān)系 R={VR} VR＝ {v,w| v,w∈ V 且 P(v,w)} v,w表示