【正文】 弧的相關(guān)信息 指向下一個有相同弧尾的結(jié)點(diǎn) 指向下一個有相同弧頭的結(jié)點(diǎn) typedef struct ArcBox { // 弧 的結(jié)構(gòu)表示 int tailvex, headvex。 3. 用途： 鄰接矩陣多用于稠密圖的存儲（ e接近 n(n1)/2)； 而鄰接表多用于稀疏圖的存儲（ en2) 它是 有向圖 的另一種鏈?zhǔn)浇Y(jié)構(gòu)。 ② 鄰接矩陣中判斷兩結(jié)點(diǎn)是否相連成邊，只需看對應(yīng)矩陣元素是否為零，在鄰接表中則要掃描某一結(jié)點(diǎn)的單鏈表（鄰接鏈表）； ③ 求邊的數(shù)目時，鄰接矩陣要檢測整個矩陣，而鄰接表則只需對每個邊表中結(jié)點(diǎn)進(jìn)行計數(shù)即可。 頂點(diǎn) Vi的出度為第 i個單鏈表中的結(jié)點(diǎn)個數(shù) 頂點(diǎn) Vi的入度為整個 單鏈表中鄰接點(diǎn)域值是 i的結(jié)點(diǎn)個數(shù) 怎樣計算有向圖頂點(diǎn)的度？ 2022/3/13 54 討論：鄰接表與鄰接矩陣有什么異同之處？ 1. 聯(lián)系： 鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個數(shù)等于一行中非零元素的個數(shù)。 若是稀疏圖，則比鄰接矩陣表示法合適。 若是稀疏圖 (en2)，則比鄰接矩陣表示法 O(n2)省空間。 // 圖的種類標(biāo)志 } ALGraph。 int vexnum, arum。 // 指向第一條依附該頂點(diǎn)的弧 } VNode, AdjList[MAX_VERTEX_NUM]。 adjvex nextarc info 弧的結(jié)點(diǎn)結(jié)構(gòu)（表結(jié)點(diǎn)） 2022/3/13 51 typedef struct VNode { VertexType data。 // 指向下一條弧的指針 InfoType *info。 2022/3/13 50 typedef struct ArcNode { int adjvex。 }//CreateUDN 2022/3/13 47 0 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3 B A C D F E 二、圖的鄰接表 存儲表示 2022/3/13 48 1 4 2 3 0 1 2 0 1 2 3 4 A B C D E 有向圖的鄰接表 ? ? ? ? ? A B E C D 可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。 //若弧含有相關(guān)信息 ,則輸入 [j][i]=[i][j]。 //確定 v1和 v2在 G中位置 [i][j].adj=w。//輸入一條邊依附的頂點(diǎn)及權(quán)值 i=LocateVex(G,v1)。v2,amp。++k){//構(gòu)造鄰接矩陣 Scanf(amp。//{adj,info} For(k=0。j。i。++i)scanf(amp。 //IncInfo為 0則各弧不含其他信息 For(i=0。,amp。G){ //采用數(shù)組 (鄰接矩陣 )表示法 ,構(gòu)造無向網(wǎng) G Scanf(amp。 // 圖的種類標(biāo)志 } MGraph。 //鄰接矩陣 int vexnum, arum。 //{有向圖，有向網(wǎng)，無向圖，無向網(wǎng) } 圖的數(shù)組（鄰接矩陣）存儲表示 typedef struct { // 圖的定義 VertexType vexs[MAX_VERTEX_NUM]。 // 該弧相關(guān)信息的指針 } ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM]。對帶權(quán)圖 ,則為 權(quán)值 類型。// VRType是頂點(diǎn)關(guān)系類型。 v1 v2 v3 v4 A v5 v6 5 4 8 9 7 5 5 6 1 3 以有向網(wǎng)為例： 鄰接矩陣： ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A = ( v1 v2 v3 v4 v5 v6 ) 鄰接矩陣法 優(yōu)點(diǎn)： 鄰接矩陣法 缺點(diǎn)： 頂點(diǎn)表： 5 7 4 8 9 5 6 5 3 1 ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ 1 ∞ v1 v2 v3 v4 v5 v6 對稀疏圖而言尤其浪費(fèi)空間?？臻g效率為 O(n2)。 頂點(diǎn)表： 1 10 1 1 0 容易實現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等。 分析 2： 頂點(diǎn) vi的 出度 =第 i行元素之和 ， OD(vi )=? A[ i ][j ] 頂點(diǎn) vi的 入度 =第 i列元素之和 。 分析 1： 有向圖的鄰接矩陣 可能是不對稱 的。 頂點(diǎn)表： V= 討論 無向圖的鄰接矩陣表示。 //廣度優(yōu)先遍歷圖 G，并對每個頂點(diǎn)調(diào) //用函數(shù) Visit一次且僅一次。 //深度優(yōu)先遍歷圖 G，并對每個頂點(diǎn)調(diào)用//函數(shù) Visit一次且僅一次。 //在 G中刪除弧 v,w，若 G是無向的， //則還刪除對稱弧 w,v。 DeleteArc(amp。G, v, w)。 // 刪除 G中頂點(diǎn) v及其相關(guān)的弧。 DeleteVex(amp。G, v)。若 w 是 v 的最后一個鄰接點(diǎn)，則 // 返回“空”。 NextAdjVex(G, v, w)。 // 返回 v 的 第一個鄰接點(diǎn) 。 // 對 v賦值 value。 PutVex(amp。 GetVex(G, v)。 //若 G存在， u和 G中頂點(diǎn)有相同特征。G, V, VR)； // 按 V和 VR的定義構(gòu)造圖 DestroyGraph(amp。 數(shù)據(jù)關(guān)系 R={VR} VR＝ {v,w| v,w∈ V 且 P(v,w)} v,w表示從 v 到 w弧， 謂詞 P(v,w) 定義了弧 v,w的意義或信息。 A B E C F A B E C F 對 有向圖 ， 否則，其各個強(qiáng)連通子圖稱作它的強(qiáng)連通分量 。 若 無向圖 G中任意兩個頂點(diǎn)之間都有路徑相通 ， 則稱此圖為 連通圖 ； 若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的 連通分量 。 2022/3/13 19 簡單路徑 :序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。 路徑上邊的數(shù)目稱作 路徑長度 。 例如 : ID(B) = 2 OD(B) = 1 TD(B) = 3 對于有向圖 G＝ (V,{A})，如果弧 v,v’ ∈ A,則稱頂點(diǎn) v鄰接到 頂點(diǎn) v’,頂點(diǎn) v’鄰接自頂點(diǎn) v。頂點(diǎn) v的 度 TD(v)是和頂點(diǎn) v 相關(guān)聯(lián)的邊的數(shù)目。 網(wǎng) :帶權(quán)的圖。 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 的 子圖 。 例如 : G2=(V2,VR2) V2={A, B, C, D, E, F} VR2={(A,B), (A,E), (B,E), (C,D), (D,F), (B,F), (C,F) } 2022/3/13 11 名詞和術(shù)語 權(quán)、網(wǎng)、子圖 完全圖 、 稀疏圖、稠密圖 鄰接點(diǎn)、度、入度、出度 路徑、路徑長度、簡單路徑 、 簡單回路 連通圖、連通分量、 強(qiáng)連通圖、強(qiáng)連通分量 生成樹、生成森林 2022/3/13 12 假設(shè)圖中有 n 個頂點(diǎn)， e 條邊或弧，不考慮頂點(diǎn)到自身的邊或弧。 若 v,w ∈ VR,則 v,w表示從 v到 w的一條 弧(Arc)， v為 弧尾 （初始點(diǎn)）， w為 弧頭 （終端點(diǎn)） 若 v, w?VR 必有 w, v?VR, 即 VR是對稱的，則以無序?qū)Γ?v,w)代替這兩個有序?qū)?，表?v 和 w 之間的一條 邊 。 圖的結(jié)構(gòu)定義 : 由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為 有向圖 (Digraph)。 Graph = (V , R ) 其中， VR＝ {v,w| v,w∈ V 且 P(v,w)} v,w表示從 v 到 w 的一條弧，并稱 v 為 弧頭 ， w 為 弧尾 。 ? 應(yīng)用圖的遍歷算法求解各種簡單路徑問題。 2022/3/13 2 七橋問題 B D A C 2022/3/13 3 網(wǎng)絡(luò)路由問題 B D A C 2022/3/13 4 一筆畫問題 2022/3/13 5 2022/3/13 6 要求 ? 掌握圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法。線性表 中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。 (a1, …, ai1, ai, …, an) 知識回顧 (20221127 week 10 fri) 在 樹形結(jié)構(gòu) 中，數(shù)據(jù)元素之間有著層次關(guān)系，每一層上的數(shù)據(jù)元素可能和下一層中多個元素相關(guān)，只能和上一層中一個元素相關(guān)。 ? 熟練掌握圖的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。 圖的定義和術(shù)語 圖的存儲結(jié)構(gòu)（ ***） 圖的遍歷（ ***） 圖的連通性問題 有向無環(huán)圖及其應(yīng)用 拓?fù)渑判? 關(guān)鍵路徑 最小生成樹（ ***） 主要內(nèi)容 最短路徑 圖 是由一個 頂點(diǎn)集 V 和一個 弧集 R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 謂詞 P(v,w) 定義了弧 v,w的意義或信息。 例如 : 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 頂點(diǎn) (Vertex)：圖中的數(shù)據(jù)元素。 B C A D F E 由頂點(diǎn)集和邊集構(gòu)成的圖稱作 無向圖Undigraph。 問題： e的取值范圍？ 2022/3/13 13 假設(shè)圖中有 n 個頂點(diǎn)， e 條邊或弧， 含有 e=n(n1)/2 條邊的無向圖稱作完全圖 ； 含有 e=n(n1) 條弧的有向圖稱作 有向完全圖 ； 若邊或弧的個數(shù) enlogn，則稱作稀疏圖 ， 否則稱作 稠密圖 。 15 9 7 21 11 3 2 權(quán) ：與圖的邊或弧相關(guān)的數(shù)。 圖 G 圖 G? A C D F E 例如 : TD(B) = 3 TD(A) = 2 邊 (v, v’) 依附 于頂點(diǎn) v 和 v’，邊 (v, v’)和頂點(diǎn) v 和 v’ 相關(guān)聯(lián) 。 B 對于無向圖 G＝（ V,{E})，如果邊（ v, v’） ∈ E，則稱 v 和 v’互為 鄰接點(diǎn) ，即 v和 v’相鄰接 頂點(diǎn)的 出度 OD(v): 以頂點(diǎn) v為尾的弧的數(shù)目， A B E C F 對有向圖來說， 頂點(diǎn)的 入度 ID(v): 以頂點(diǎn) v為頭的弧的數(shù)目。 頂點(diǎn)的 度 (TD)=出度 (OD)+入度 (ID) 2022/3/13 18 設(shè)圖 G=(V,{VR})中的一個頂點(diǎn)序列 { u=vi,0,vi,1, …, vi,m=w}中 ， (vi,j1,vi,j)?VR 1≤j≤m, 則稱從頂點(diǎn) u 到頂點(diǎn) w 之間存在一