2021年4月19日星期一第1頁 第 七 章圖 2021年4月19日星期一第2頁 【課前思考】1. 同學們有沒有發(fā)現(xiàn)現(xiàn)在的十字路口的交通燈已從過去的一對改為三對，即每個方向的直行、左拐和右拐能否通行都有相應的交通燈指明。你能否對某個丁字路口的6條通路畫出和第一章緒論中介紹的五叉路口交通管理示意圖相類似的圖？同學們一定可以畫出如下所示類似的圖形。 2. 如果每次讓三條路同時通行，那么從圖看出哪些路可以同時通行？同時可通行的路為：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC) 2021年4月19日星期一第3頁 【學習目標】 1領會圖的類型定義。2熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲結(jié)構(gòu)的特點及其選用原則。3熟練掌握圖的兩種遍歷算法。4理解各種圖的應用問題的算法。 2021年4月19日星期一第4頁 【重點和難點】 圖的應用極為廣泛，而且圖的各種應用問題的算法都比較經(jīng)典，因此本章重點在于理解各種圖的算法及其應用場合?！局R點】 圖的類型定義、圖的存儲表示、圖的深度優(yōu)先搜索遍歷和圖的廣度優(yōu)先搜索遍歷、無向網(wǎng)的最小生成樹、最短路徑、拓撲排序、關鍵路徑。 2021年4月19日星期一第5頁 【學習指南】 離散數(shù)學中的圖論是專門研究圖性質(zhì)的一個數(shù)學分支，但圖論注重研究圖的純數(shù)學性質(zhì)，而數(shù)據(jù)結(jié)構(gòu)中對圖的討論則側(cè)重于在計算機中如何表示圖以及如何實現(xiàn)圖的操作和應用等。圖是較線性表和樹更為復雜的數(shù)據(jù)結(jié)構(gòu)，因此和線性表、樹不同，雖然在遍歷圖的同時可以對頂點或弧進行各種操作，但更多圖的應用問題如求最小生成樹和最短路徑等在圖論的研究中都早已有了特定算法，在本章中主要是介紹它們在計算機中的具體實現(xiàn)。這些算法乍一看都比較難，應多對照具體圖例的存儲結(jié)構(gòu)進行學習。而圖遍歷的兩種搜索路徑和樹遍歷的兩種搜索路徑極為相似，應將兩者的算法對照學習以便提高學習的效果。本章必須完成的算法設計題為 : 7.7,7.9,7.10,7.12,7.14,7.15,7.22 2021年4月19日星期一第6頁 7.1 圖 的 定 義 與 術(shù) 語7.2 圖 的 存 儲 表 示7.3 圖 的 遍 歷7.4 最 小 生 成 樹7.5 重 （ 雙 ） 連 通 圖 和 關 節(jié) 點7.6 兩 點 之 間 的 最 短 路 徑 問 題7.7 拓 撲 排 序7.8 關 鍵 路 徑 2021年4月19日星期一第7頁 圖 是 由 一 個 頂 點 集 V 和 一 個 弧 集 R構(gòu) 成的 數(shù) 據(jù) 結(jié) 構(gòu) 。 Graph = (V , VR )其 中 ， VR | v,w V 且 P(v,w) 表 示 從 v 到 w 的 一 條 弧 ， 并 稱 v 為弧 頭 ， w 為 弧 尾 。 謂 詞 P(v,w) 定 義 了 弧 的 意 義 或 信 息 。圖 的 結(jié) 構(gòu) 定 義 :7.1 圖 的 定 義 與 術(shù) 語 2021年4月19日星期一第8頁 由 于 “ 弧 ” 是 有 方 向 的 ， 因 此 稱 由 頂 點集 和 弧 集 構(gòu) 成 的 圖 為 有 向 圖 。 AB E C D例 如 : G1 = (V1, VR1)其 中V1=A, B, C, D, EVR1=, , , , , , 2021年4月19日星期一第9頁 若 VR 必 有 VR, 則 稱 (v,w) 為 頂 點 v 和 頂 點 w 之 間 存 在 一 條 邊 。 B CA D F E由 頂 點 集 和 邊集 構(gòu) 成 的 圖 稱作 無 向 圖 。例 如 : G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A,B),(A,E),(B,E),(C,D),(D,F), (B,F),(C,F) 2021年4月19日星期一第10頁 名 詞 和 術(shù) 語網(wǎng) 、 子 圖 完 全 圖、稀 疏 圖 、 稠 密 圖鄰 接 點 、 度 、 入 度 、 出 度路 徑 、 路 徑 長 度 、 簡 單 路 徑、簡 單 回 路連 通 圖 、 連 通 分 量 、強 連 通 圖 、 強 連 通 分 量生 成 樹 、 生 成 森 林 2021年4月19日星期一第11頁 AB EC F A EFBB C設 圖 G=(V,VR) 和圖 G=(V,VR),且 VV, VRVR,則 稱 G 為 G 的 子 圖。15 97 21 113 2 弧 或 邊 帶 權(quán) 的 圖分 別 稱 作 有 向 網(wǎng) 或無 向 網(wǎng) 。 C 2021年4月19日星期一第12頁 假 設 圖 中 有 n 個 頂 點 ， e 條 邊 ， 則 含 有 e=n(n-1)/2 條 邊 的 無 向 圖 稱 作完 全 圖 ； 含 有 e=n(n-1) 條 弧 的 有 向 圖 稱 作 有 向 完 全 圖 ； 若 邊 或 弧 的 個 數(shù) enlogn， 則 稱 作稀 疏 圖 ， 否 則 稱 作 稠 密 圖 。 2021年4月19日星期一第13頁 假 若 頂 點 v 和 頂 點 w 之 間 存 在 一 條 邊 ，則 稱 頂 點 v 和 w 互 為 鄰 接 點 ，A C DF E例 如 :ID(B) = 3ID(A) = 2 邊 (v,w) 和 頂 點 v 和 w 相 關 聯(lián) 。 和 頂 點 v 關 聯(lián) 的 邊 的 數(shù) 目 定 義 為 頂 點 v的 度 。B 2021年4月19日星期一第14頁 頂 點 的 出 度 : 以 頂 點v為 弧 尾 的 弧 的 數(shù) 目 ；AB EC F對 有 向 圖 來 說 ， 頂 點 的 入 度 : 以 頂 點 v為 弧 頭 的 弧 的 數(shù) 目 。頂 點 的 度 (TD)=出 度 (OD)+入 度 (ID)例 如 :ID(B) = 2OD(B) = 1TD(B) = 3 2021年4月19日星期一第15頁 設 圖 G=(V,VR)中 的 一 個 頂 點 序 列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則 稱 從 頂 點 u 到 頂 點 w 之 間 存 在 一 條 路 徑 。路 徑 上 邊 (或 弧 )的 數(shù) 目 稱 作 路 徑 長 度 。AB EC F如 :長 度 為 3的 路 徑A,B,C,F 簡 單 路 徑 :序 列 中 頂 點不 重 復 出 現(xiàn) 的 路 徑 。簡 單 回 路 :序 列 中 第 一個 頂 點 和 最 后 一 個 頂點 相 同 的 路 徑 而 其 余頂 點 不 重 復 。 2021年4月19日星期一第16頁 若 圖 G中 任 意 兩 個 頂點 之 間 都 有 路 徑 相 通 ，則 稱 此 圖 為 連 通 圖 ； 若 無 向 圖 為 非 連 通 圖 ，則 圖 中 各 個 極 大 連 通子 圖 稱 作 此 圖 的 連 通分 量 。 BA C DF EBA C DF E 2021年4月19日星期一第17頁 若 任 意 兩 個 頂 點 之 間 都 存 在一 條 有 向 路 徑 ， 則 稱 此 有 向 圖 為 強 連 通 圖 。AB EC F AB EC F對 有 向 圖 ，否 則 ， 其 各 個 強 連 通 子 圖 稱 作 它 的強 連 通 分 量 。 2021年4月19日星期一第18頁 假 設 一 個 連 通 圖 有 n 個 頂 點 和 e 條 邊 ，其 中 n-1 條 邊 和 n 個 頂 點 構(gòu) 成 一 個 極 小連 通 子 圖 ， 稱 該 極 小 連 通 子 圖 為 此 連 通 圖的 生 成 樹 。 對 非 連 通 圖 ， 則稱 由 各 個 連 通 分量 的 生 成 樹 的 集合 為 此 非 連 通 圖的 生 成 森 林 。BA C DF E 2021年4月19日星期一第19頁 結(jié) 構(gòu) 的 建 立 和 銷 毀插 入 或 刪 除 頂 點對 鄰 接 點 的 操 作 對 頂 點 的 訪 問 操 作遍 歷插 入 和 刪 除 弧基 本 操 作 2021年4月19日星期一第20頁 CreatGraph( / 若 G中 存 在 頂 點 u， 則 返 回 該 頂 點 在 / 圖 中 “ 位 置 ” ； 否 則 返 回 其 它 信 息 。GetVex(G, v); / 返 回 v 的 值 。PutVex( / 對 v 賦 值 value。 2021年4月19日星期一第22頁 對 鄰 接 點 的 操 作FirstAdjVex(G, v); / 返 回 v 的 “ 第 一 個 鄰 接 點 ” 。 若 該 頂 點/在 G 中 沒 有 鄰 接 點 ， 則 返 回 “ 空 ” 。NextAdjVex(G, v, w); / 返 回 v 的 （ 相 對 于 w 的 ） “ 下 一 個 鄰 接/ 點 ” 。 若 w 是 v 的 最 后 一 個 鄰 接 點 ， 則/ 返 回 “ 空 ” 。 2021年4月19日星期一第23頁 插 入 或 刪 除 頂 點InsertVex( /在 圖 G中 增 添 新 頂 點 v。DeleteVex( / 刪 除 G中 頂 點 v及 其 相 關 的 弧 。 2021年4月19日星期一第24頁 插 入 和 刪 除 弧InsertArc( / 在 G中 增 添 弧 ， 若 G是 無 向 的 ， /則 還 增 添 對 稱 弧 。DeleteArc( /在 G中 刪 除 弧 ， 若 G是 無 向 的 ， /則 還 刪 除 對 稱 弧 。 2021年4月19日星期一第25頁 遍 歷DFSTraverse(G, v, Visit(); /從 頂 點 v起 深 度 優(yōu) 先 遍 歷 圖 G， 并 對 每/個 頂 點 調(diào) 用 函 數(shù) Visit一 次 且 僅 一 次 。BFSTraverse(G, v, Visit(); /從 頂 點 v起 廣 度 優(yōu) 先 遍 歷 圖 G， 并 對 每/個 頂 點 調(diào) 用 函 數(shù) Visit一 次 且 僅 一 次 。 2021年4月19日星期一第26頁 7.2 圖 的 存 儲 表 示一 、 圖 的 數(shù) 組 (鄰 接 矩 陣 )存 儲 表 示二 、 圖 的 鄰 接 表 存 儲 表 示三 、 有 向 圖 的 十 字 鏈 表 存 儲 表 示 四 、 無 向 圖 的 鄰 接 多 重 表 存 儲 表 示 2021年4月19日星期一第27頁 Aij=0 (i,j)VR1 (i,j)VR一 、 圖 的 數(shù) 組 (鄰 接 矩 陣 )存 儲 表 示BA C DF E定 義 :矩 陣 的 元 素 為 0 1 0 0 1 01 0 0 0 1 00 0 0 1 0 1 0 0 1 0 0 11 1 0 0 0 00 1 1 1 0 0 2021年4月19日星期一第28頁 有 向 圖 的 鄰 接 矩 陣為 非 對 稱 矩 陣AB EC F 0 1 0 0 10 0 1 0 0 0 0 0 1 01 1 0 0 0 0 0 1 0 0 2021年4月19日星期一第29頁 typedef struct ArcCell / 弧 的 定 義 VRType adj; / VRType是 頂 點 關 系 類 型 。 / 對 無 權(quán) 圖 ， 用 1或 0表 示 相 鄰 否 ； / 對 帶 權(quán) 圖 ， 則 為 權(quán) 值 類 型 。 InfoType *info; / 該 弧 相 關 信 息 的 指 針 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM; 2021年4月19日星期一第30頁 typedef struct / 圖 的 定 義 VertexType / 頂 點 信 息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧 的 信 息 int vexnum, arcnum; / 頂 點 數(shù) ， 弧 數(shù) GraphKind kind; / 圖 的 種 類 標 志 MGraph; 2021年4月19日星期一第31頁 0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3 BA C DF E二 、 圖 的 鄰 接 表 存 儲 表 示 2021年4月19日星期一第32頁 1 4230 120 1 2 3 4 A B C D E有 向 圖 的 鄰 接 表 AB EC D可 見 ， 在 有 向 圖 的鄰 接 表 中 不 易 找 到指 向 該 頂 點 的 弧 。 2021年4月19日星期一第33頁 AB EC D有 向 圖 的 逆 鄰 接 表 A B C D E 3 03420 01234在 有 向 圖 的 鄰 接 表中 ， 對 每 個 頂 點 ，鏈 接 的 是 指 向 該 頂點 的 弧 。 2021年4月19日星期一第34頁 typedef struct ArcNode int adjvex; / 該 弧 所 指 向 的 頂 點 的 位 置 struct ArcNode *nextarc; / 指 向 下 一 條 弧 的 指 針 InfoType *info; / 該 弧 相 關 信 息 的 指 針 ArcNode; adjvex nextarc info弧 的 結(jié) 點 結(jié) 構(gòu) 2021年4月19日星期一第35頁 typedef struct VNode VertexType data; / 頂 點 信 息 ArcNode *firstarc; / 指 向 第 一 條 依 附 該 頂 點 的 弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc頂 點 的 結(jié) 點 結(jié) 構(gòu) 2021年4月19日星期一第36頁 typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 圖 的 種 類 標 志 ALGraph;圖 的 結(jié) 構(gòu) 定 義 2021年4月19日星期一第37頁 三 、 有 向 圖 的 十 字 鏈 表 存 儲 表 示 弧 的 結(jié) 點 結(jié) 構(gòu)弧 尾 頂 點 位 置 弧 頭 頂 點 位 置 弧 的 相 關 信 息指 向 下 一 個有 相 同 弧 尾的 結(jié) 點 指 向 下 一 個有 相 同 弧 頭的 結(jié) 點typedef struct ArcBox / 弧 的 結(jié) 構(gòu) 表 示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode; 2021年4月19日星期一第38頁 頂 點 的 結(jié) 點 結(jié) 構(gòu)頂 點 信 息 數(shù) 據(jù) 指 向 該 頂 點 的第 一 條 入 弧 指 向 該 頂 點 的第 一 條 出 弧typedef struct VexNode / 頂 點 的 結(jié) 構(gòu) 表 示 VertexType data; ArcBox *firstin, *firstout; VexNode; 2021年4月19日星期一第39頁 typedef struct VexNode xlistMAX_VERTEX_NUM; / 頂 點 結(jié) 點 (表 頭 向 量 ) int vexnum, arcnum; /有 向 圖 的 當 前 頂 點 數(shù) 和 弧 數(shù) OLGraph;有 向 圖 的 結(jié) 構(gòu) 表 示 (十 字 鏈 表 ) 2021年4月19日星期一第40頁 四 、 無 向 圖 的 鄰 接 多 重 表 存 儲 表 示typedef struct Ebox VisitIf mark; / 訪 問 標 記 int ivex, jvex; /該 邊 依 附 的 兩 個 頂 點 的位 置 struct EBox *ilink, *jlink; /分 別 指 向 依 附這 兩 個 頂 點 的 下 一 條 邊 InfoType *info; / 該 邊 信 息 指 針 EBox; 邊 的 結(jié) 構(gòu) 表 示 2021年4月19日星期一第41頁typedef struct / 鄰 接 多 重 表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph; 頂 點 的 結(jié) 構(gòu) 表 示typedef struct VexBox VertexType data; EBox *firstedge; / 指 向 第 一 條 依 附 該 頂 點 的 邊 VexBox; 無 向 圖 的 結(jié) 構(gòu) 表 示 2021年4月19日星期一第42頁 7.3 圖 的 遍 歷 從 圖 中 某 個 頂 點 出 發(fā) 游 歷 圖 ， 訪 遍圖 中 其 余 頂 點 ， 并 且 使 圖 中 的 每 個 頂 點僅 被 訪 問 一 次 的 過 程 。深 度 優(yōu) 先 搜 索廣 度 優(yōu) 先 搜 索遍 歷 應 用 舉 例 2021年4月19日星期一第43頁 從 圖 中 某 個 頂 點 V0 出 發(fā) ， 訪 問 此 頂點 ， 然 后 依 次 從 V0的 各 個 未 被 訪 問 的 鄰接 點 出 發(fā) 深 度 優(yōu) 先 搜 索 遍 歷 圖 ， 直 至 圖 中所 有 和 V0有 路 徑 相 通 的 頂 點 都 被 訪 問 到 。一 、 深 度 優(yōu) 先 搜 索 遍 歷 圖連 通 圖 的 深 度 優(yōu) 先 搜 索 遍 歷 2021年4月19日星期一第44頁 Vw1SG1 SG2 SG3 W1、W2和 W3 均 為 V 的鄰 接 點 ， SG1、SG2 和 SG3 分 別 為 含 頂 點 W1、W2和 W3 的 子 圖 。訪 問 頂 點 V ：for (W1、W2、 W3 ) 若 該 鄰 接 點 W未 被 訪 問 ， 則 從 它 出 發(fā) 進 行 深 度 優(yōu) 先 搜 索 遍 歷 。w2 w3 2021年4月19日星期一第45頁 從 上 頁 的 圖 解 可 見 :1. 從 深 度 優(yōu) 先 搜 索 遍 歷 連 通 圖 的 過程 類 似 于 樹 的 先 根 遍 歷 ；解 決 的 辦 法 是 ： 為 每 個 頂 點 設 立 一個 “ 訪 問 標 志 visitedw”。2. 如 何 判 別 V的 鄰 接 點 是 否 被 訪 問 ？ 2021年4月19日星期一第46頁 void DFS(Graph G, int v) / 從 頂 點 v出 發(fā) ， 深 度 優(yōu) 先 搜 索 遍 歷 連 通 圖 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 對 v的 尚 未 訪 問 的 鄰 接 頂 點 w / 遞 歸 調(diào) 用 DFS / DFS 2021年4月19日星期一第47頁 首 先 將 圖 中 每 個 頂 點 的 訪 問 標 志 設為 FALSE, 之 后 搜 索 圖 中 每 個 頂 點 ， 如果 未 被 訪 問 ， 則 以 該 頂 點 為 起 始 點 ， 進行 深 度 優(yōu) 先 搜 索 遍 歷 ， 否 則 繼 續(xù) 檢 查 下一 頂 點 。非 連 通 圖 的 深 度 優(yōu) 先 搜 索 遍 歷 2021年4月19日星期一第48頁 void DFSTraverse(Graph G, Status (*Visit)(int v) / 對 圖 G 作 深 度 優(yōu) 先 遍 歷 。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪 問 標 志 數(shù) 組 初 始 化 for (v=0; vw1, V-w2, V-w8 的 路 徑 長 度 為 1；V-w7, V-w3, V-w5 的 路 徑 長 度 為 2；V-w6, V-w4 的 路 徑 長 度 為 3。 2021年4月19日星期一第51頁 從 圖 中 的 某 個 頂 點 V0出 發(fā) ， 并 在 訪 問 此頂 點 之 后 依 次 訪 問 V0的 所 有 未 被 訪 問 過 的鄰 接 點 ， 之 后 按 這 些 頂 點 被 訪 問 的 先 后 次序 依 次 訪 問 它 們 的 鄰 接 點 ， 直 至 圖 中 所 有和 V0有 路 徑 相 通 的 頂 點 都 被 訪 問 到 。 若 此 時 圖 中 尚 有 頂 點 未 被 訪 問 ， 則 另 選圖 中 一 個 未 曾 被 訪 問 的 頂 點 作 起 始 點 ， 重復 上 述 過 程 ， 直 至 圖 中 所 有 頂 點 都 被 訪 問到 為 止 。 2021年4月19日星期一第52頁 void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初 始 化 訪 問 標 志 InitQueue(Q); / 置 空 的 輔 助 隊 列 Q for ( v=0; vnext = Q.rear-next = NULLvoid EnQueue( LinkQueue p-data = e; p-next = NULL; p-prior = Q.front Q.rear-next = p; Q.rear = p;void DeQueue( LinkQueue e = Q.front-data 2021年4月19日星期一第63頁 7.4 (連 通 網(wǎng) 的 )最 小 生 成 樹 假 設 要 在 n 個 城 市 之 間 建 立 通 訊聯(lián) 絡 網(wǎng) ， 則 連 通 n 個 城 市 只 需 要 修 建 n-1條 線 路 ， 如 何 在 最 節(jié) 省 經(jīng) 費 的 前提 下 建 立 這 個 通 訊 網(wǎng) ？問 題 ： 2021年4月19日星期一第64頁 構(gòu) 造 網(wǎng) 的 一 棵 最 小 生 成 樹 ， 即 ： 在 e 條 帶 權(quán) 的 邊 中 選 取 n-1 條 邊 （ 不 構(gòu) 成回 路 ） ， 使 “ 權(quán) 值 之 和 ” 為 最 小 。算 法 二 ： （ 克 魯 斯 卡 爾 算 法 ）該 問 題 等 價 于 ：算 法 一 ： （ 普 里 姆 算 法 ） 2021年4月19日星期一第65頁 取 圖 中 任 意 一 個 頂 點 v 作 為 生 成 樹 的 根 ，之 后 往 生 成 樹 上 添 加 新 的 頂 點 w。 在 待 添加 的 頂 點 w 和 已 經(jīng) 在 生 成 樹 上 的 頂 點 v 之間 必 定 存 在 一 條 邊 ， 并 且 該 邊 的 權(quán) 值 在 所有 連 通 頂 點 v 和 w 之 間 的 邊 中 取 值 最 小 。之 后 繼 續(xù) 往 生 成 樹 上 添 加 頂 點 ， 直 至 生 成樹 上 含 有 n個 頂 點 為 止 。普 里 姆 算 法 的 基 本 思 想 : 2021年4月19日星期一第66頁 a b cdeg f例 如 : 19 51418 2716 821 312 7所 得 生 成 樹 權(quán) 值 和= 14+8+3+5+16+21 = 67 2021年4月19日星期一第67頁 在 生 成 樹 的 構(gòu) 造 過 程 中 ， 圖 中 n 個頂 點 分 屬 兩 個 集 合 ： 已 落 在 生 成 樹 上 的頂 點 集 U 和 尚 未 落 在 生 成 樹 上 的 頂 點 集V-U ， 則 應 在 所 有 連 通 U中 頂 點 和 V-U中頂 點 的 邊 中 選 取 權(quán) 值 最 小 的 邊 。 一 般 情 況 下 所 添 加 的 頂 點 應 滿 足 下 列條 件 : 2021年4月19日星期一第68頁 設 置 一 個 輔 助 數(shù) 組 ， 對 當 前 V U集中 的 每 個 頂 點 ， 記 錄 和 頂 點 集 U中 頂 點相 連 接 的 代 價 最 小 的 邊 ：struct VertexType adjvex; / U集 中 的 頂 點 序 號 VRType lowcost; / 邊 的 權(quán) 值 closedgeMAX_VERTEX_NUM; 2021年4月19日星期一第69頁 a b cdeg f19 51418 2716 821 312 7 closedge 0 1 2 3 4 5 6Adjvex Lowcost a a a19 14 18 例如: e2 e e8 6d3d d7 21c5 2021年4月19日星期一第70頁 void MiniSpanTree_P(MGraph G, VertexType u) /用 普 里 姆 算 法 從 頂 點 u出 發(fā) 構(gòu) 造 網(wǎng) G的 最 小 生 成 樹 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 輔 助 數(shù) 組 初 始 化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初 始 ， U u for (i=0; iG.vexnum; +i) 繼 續(xù) 向 生 成 樹 上 添 加 頂 點 ; 2021年4月19日星期一第71頁 k = minimum(closedge); / 求 出 加 入 生 成 樹 的 下 一 個 頂 點 (k) printf(closedgek.adjvex, G.vexsk); / 輸 出 生 成 樹 上 一 條 邊 closedgek.lowcost = 0; / 第 k頂 點 并 入 U集 for (j=0; jG.vexnum; +j) /修 改 其 它 頂 點 的 最 小 邊 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ; 2021年4月19日星期一第72頁具 體 做 法 : 先 構(gòu) 造 一 個 只 含 n 個 頂 點 的 子 圖 SG， 然 后 從 權(quán) 值 最 小 的 邊 開 始 ， 若 它 的 添加 不 使 SG 中 產(chǎn) 生 回 路 ， 則 在 SG 上 加 上 這條 邊 ， 如 此 重 復 ， 直 至 加 上 n-1 條 邊 為 止 。 考 慮 問 題 的 出 發(fā) 點 : 為 使 生 成 樹 上 邊 的 權(quán)值 之 和 達 到 最 小 ， 則 應 使 生 成 樹 中 每 一 條邊 的 權(quán) 值 盡 可 能 地 小 ?？?魯 斯 卡 爾 算 法 的 基 本 思 想 ： 2021年4月19日星期一第73頁 a b cdeg f19 51418 2716 821 312 7例 如 : 2021年4月19日星期一第74頁 算 法 描 述 :構(gòu) 造 非 連 通 圖 ST=( V, ); k = i = 0; / k 計 選 中 的 邊 數(shù) while (kadjvex; DFSArticul(G, v); / 從 第 v頂 點 出 發(fā) 深 度 優(yōu) 先 搜 索 if (count nextarc) void DFSArticul(ALGraph G, int v0) / 從 第 v0個 頂 點 出 發(fā) 深 度 優(yōu) 先 遍 歷 圖 G, / 查 找 并 輸 出 關 節(jié) 點 / DFSArticulmin =visitedv0 = +count; / v0是 第 count個 訪 問 的 頂 點 , 并 設 lowv0的 初 值 為 min / 檢 查 v0的 每 個 鄰 接 點lowv0 = min; 2021年4月19日星期一第86頁 w = p-adjvex; / w為 v0的 鄰 接 頂 點 if (visitedw = 0) / w未 曾 被 訪 問 DFSArticul(G, w); / 返 回 前 求 得 loww else / w是 回 邊 上 的 頂 點if (loww =visitedv0) printf(v0, G.verticesv0.data); /輸 出 關 節(jié) 點if (visitedw min) min = visitedw; 2021年4月19日星期一第87頁 7.6 兩 點 之 間 的 最 短 路 徑 問 題 求 從 某 個 源 點 到 其 余 各 點 的最 短 路 徑 每 一 對 頂 點 之 間 的 最 短 路 徑 2021年4月19日星期一第88頁 求 從 源 點 到 其 余 各 點 的 最 短 路 徑的 算 法 的 基 本 思 想 : 依 最 短 路 徑 的 長 度 遞 增 的 次 序 求 得各 條 路 徑源 點 v1 其 中 ， 從 源 點 到頂 點 v的 最 短 路 徑是 所 有 路 徑 中 長度 最 短 者 。v2 2021年4月19日星期一第89頁 在 這 條 路 徑 上 ， 必 定 只 含 一 條 弧 ， 并 且這 條 弧 的 權(quán) 值 最 小 。 下 一 條 路 徑 長 度 次 短 的 最 短 路 徑 的 特 點 ：路 徑 長 度 最 短 的 最 短 路 徑 的 特 點 ： 它 只 可 能 有 兩 種 情 況 ： 或 者 是 直 接 從 源點 到 該 點 (只 含 一 條 弧 )； 或 者 是 從 源 點 經(jīng)過 頂 點 v1， 再 到 達 該 頂 點 (由 兩 條 弧 組 成 )。 2021年4月19日星期一第90頁其 余 最 短 路 徑 的 特 點 ： 再 下 一 條 路 徑 長 度 次 短 的 最 短 路 徑 的 特 點 : 它 可 能 有 三 種 情 況 ： 或 者 是 直 接 從 源 點 到該 點 (只 含 一 條 弧 )； 或 者 是 從 源 點 經(jīng) 過 頂 點v1， 再 到 達 該 頂 點 (由 兩 條 弧 組 成 )； 或 者 是從 源 點 經(jīng) 過 頂 點 v2， 再 到 達 該 頂 點 。 它 或 者 是 直 接 從 源 點 到 該 點 (只 含 一 條弧 )； 或 者 是 從 源 點 經(jīng) 過 已 求 得 最 短 路 徑的 頂 點 ， 再 到 達 該 頂 點 。 2021年4月19日星期一第91頁 求 最 短 路 徑 的 迪 杰 斯 特 拉 算 法 ：一 般 情 況 下 ，Distk = 或 者 = + 。 設 置 輔 助 數(shù) 組 Dist， 其 中 每 個 分 量 Distk 表 示 當 前 所 求 得 的 從 源 點 到 其 余 各 頂 點 k 的 最 短 路 徑 。 2021年4月19日星期一第92頁 1） 在 所 有 從 源 點 出 發(fā) 的 弧 中 選 取 一 條 權(quán)值 最 小 的 弧 ， 即 為 第 一 條 最 短 路 徑 。2） 修 改 其 它 各 頂 點 的 Distk值 。假 設 求 得 最 短 路 徑 的 頂 點 為 u，若 Distu+G.arcsukDistk則 將 Distk 改 為 Distu+G.arcsuk。 INFINITY kvarcsGkDist 0. V0和 k之 間 存 在 弧V0和 k之 間 不 存 在 弧其 中 的 最 小 值 即 為 最 短 路 徑 的 長 度 。 2021年4月19日星期一第93頁 求 每 一 對 頂 點 之 間 的 最 短 路 徑弗洛伊德算法的基本思想是： 從 vi 到 vj 的 所 有 可能 存 在 的 路 徑 中 ， 選 出一 條 長 度 最 短 的 路 徑 。 2021年4月19日星期一第94頁 若 存 在 ， 則 存 在 路 徑 vi,vj / 路 徑 中 不 含 其 它 頂 點若 ,存 在 ， 則 存 在 路 徑 vi,v1,vj / 路 徑 中 所 含 頂 點 序 號 不 大 于 1若 vi,v2, v2,vj存 在 ， 則 存 在 一 條 路 徑 vi, , v2, vj / 路 徑 中 所 含 頂 點 序 號 不 大 于 2 依 次 類 推 ， 則 vi 至 vj 的 最 短 路 徑 應 是上 述 這 些 路 徑 中 ， 路 徑 長 度 最 小 者 。 2021年4月19日星期一第95頁 7.7 拓 撲 排 序 問 題 : 假 設 以 有 向 圖 表 示 一 個 工 程 的 施工 圖 或 程 序 的 數(shù) 據(jù) 流 圖 ， 則 圖 中 不 允許 出 現(xiàn) 回 路 。 檢 查 有 向 圖 中 是 否 存 在 回 路 的 方 法之 一 ， 是 對 有 向 圖 進 行 拓 撲 排 序 。 2021年4月19日星期一第96頁 何 謂 “ 拓 撲 排 序 ” ？對 有 向 圖 進 行 如 下 操 作 ： 按 照 有 向 圖 給 出 的 次 序 關 系 ，將 圖 中 頂 點 排 成 一 個 線 性 序 列 ，對 于 有 向 圖 中 沒 有 限 定 次 序 關系 的 頂 點 ， 則 可 以 人 為 加 上 任意 的 次 序 關 系 。 2021年4月19日星期一第97頁 例 如 ： 對 于 下 列 有 向 圖B DA C可 求 得 拓 撲 有 序 序 列： A B C D 或 A C B D由 此 所 得 頂 點 的 線 性 序 列 稱 之 為拓 撲 有 序 序 列 2021年4月19日星期一第98頁 B DA C反 之 ， 對 于 下 列 有 向 圖不 能 求 得 它 的 拓 撲 有 序 序 列 。因 為 圖 中 存 在 一 個 回 路 B, C, D 2021年4月19日星期一第99頁 如 何 進 行 拓 撲 排 序 ？一 、 從 有 向 圖 中 選 取 一 個 沒 有 前 驅(qū) 的 頂 點 ， 并 輸 出 之 ； 重 復 上 述 兩 步 ， 直 至 圖 空 ， 或 者圖 不 空 但 找 不 到 無 前 驅(qū) 的 頂 點 為 止 。二 、 從 有 向 圖 中 刪 去 此 頂 點 以 及 所 有 以 它 為 尾 的 弧 ； 2021年4月19日星期一第100頁 ab cgh df ea b h c d g f e在 算 法 中 需 要 用 定 量 的 描 述 替 代 定 性 的 概 念 沒 有 前 驅(qū) 的 頂 點 入 度 為 零 的 頂 點刪 除 頂 點 及 以 它 為 尾 的 弧 弧 頭 頂 點 的 入 度 減 1 2021年4月19日星期一第101頁 取 入 度 為 零 的 頂 點 v;while (v0) printf(v); +m; w:=FirstAdj(v); while (w0) inDegreew-; w:=nextAdj(v,w); 取 下 一 個 入 度 為 零 的 頂 點 v;if mn printf(“圖 中 有 回 路 ” );算法描述 2021年4月19日星期一第102頁 為 避 免 每 次 都 要 搜 索 入 度 為 零 的 頂 點 ，在 算 法 中 設 置 一 個 “ 棧 ” ， 以 保 存 “ 入 度為 零 ” 的 頂 點 。CountInDegree(G,indegree); /對 各 頂 點 求 入 度InitStack(S);for ( i=0; iG.vexnum; +i) if (!indegreei) Push(S, i); /入 度 為 零 的 頂 點 入 棧 2021年4月19日星期一第103頁 count=0; /對 輸 出 頂 點 計 數(shù)while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w) -indegree(w); / 弧 頭 頂 點 的 入 度 減 一 if (!indegreew) Push(S, w); /新 產(chǎn) 生 的 入 度 為 零 的 頂 點 入 棧 if (countG.vexnum) printf(“ 圖 中 有 回 路 ” ) 2021年4月19日星期一第104頁 7.8 關 鍵 路 徑問 題 : 假 設 以 有 向 網(wǎng) 表 示 一 個 施 工 流 圖 ， 弧上 的 權(quán) 值 表 示 完 成 該 項 子 工 程 所 需 時 間 。問 ： 哪 些 子 工 程 項 是 “ 關 鍵 工 程 ” ？即 ： 哪 些 子 工 程 項 將 影 響 整 個 工 程 的 完 成期 限 的 。 2021年4月19日星期一第105頁 a bcd e f gh k645 211 87 244例 如 :“關 鍵 活 動 ” 指 的 是 ： 該 弧 上 的 權(quán) 值 增 加 將 使有 向 圖 上 的 最 長 路 徑 的 長 度 增 加 。整 個 工 程 完 成 的 時 間 為 ： 從 有 向 圖 的 源 點 到 匯 點的 最 長 路 徑 。源 點 匯 點 2021年4月19日星期一第106頁 如 何 求 關 鍵 活 動 ？“事 件 (頂 點 )” 的 最 早 發(fā) 生 時 間 ve(j)ve(j) = 從 源 點 到 頂 點 j的 最 長 路 徑 長 度 ；“事 件 (頂 點 )” 的 最 遲 發(fā) 生 時 間 vl(k) vl(k) = 從 頂 點 k到 匯 點 的 最 短 路 徑 長 度 。 2021年4月19日星期一第107頁 假 設 第 i 條 弧 為 則 對 第 i 項 活 動 言 “ 活 動 (弧 )”的 最 早 開 始 時 間 ee(i) ee(i) = ve(j)； “ 活 動 (弧 )”的 最 遲 開 始 時 間 el(i) el(i) = vl(k) dut()； 2021年4月19日星期一第108頁 事 件 發(fā) 生 時 間 的 計 算 公 式 ： ve(源 點 ) = 0； ve(k) = Maxve(j) + dut()j為 所 有 以 k為 弧 頭 的 頂 點 集 vl(匯 點 ) = ve(匯 點 )； vl(j) = Minvl(k) dut()k為 所 有 以 j為 弧 尾 的 頂 點 集 2021年4月19日星期一第109頁 a bcd e f gh k645 211 87 244 a b c d e f g h kve vl 0 0 0 0 0 0 0 0 06 4 5 7 1157 15 4 18181818181818181818 6 486 6 080 7拓 撲 有 序 序 列 : a - d - f - c - b - e - h - g - k 2021年4月19日星期一第110頁 a b c d e f g h kve vl 0 6 4 5 7 7 15 14 181814161078660 ab ac ad be ce df eg eh fh gk hk權(quán) 6 4 5 1 1 2 8 7 4 2 4 el 0 0 0 6 4 5 7 7 7 15 1414160 2 3 6 6 8 8 7 10 2021年4月19日星期一第111頁 算 法 的 實 現(xiàn) 要 點 :顯 然 ， 求 ve的 順 序 應 該 是 按 拓 撲 有 序 的 次 序 ； 而 求 vl的 順 序 應 該 是 按 拓 撲 逆 序 的 次 序 ；因 為 拓 撲 逆 序 序 列 即 為 拓 撲 有 序 序 列 的 逆 序 列 ，因 此 應 該 在 拓 撲 排 序 的 過 程 中 ， 另 設 一 個 “ 棧 ” 記 下 拓 撲 有 序 序 列 。 2021年4月19日星期一第112頁 【本章小結(jié)】 圖是一種比線性表和樹更復雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在著明顯的層次關系，并且每層的元素可能和下一層的多個元素（即其孩子結(jié)點）相鄰，但只能和上一層的一個元素（即其雙親結(jié)點）相關。而在圖形結(jié)構(gòu)中，結(jié)點之間的關系可以是任意的，圖中任意兩個元素之間都可能相鄰。和樹類似，圖的遍歷是圖的一種主要操作，可以通過遍歷判別圖中任意兩個頂點之間是否存在路徑、判別給定的圖是否是連通圖并可求得非連通圖的各個連通分量，但對于帶權(quán)圖（網(wǎng)），其最小生成樹或最短路徑都取決于弧或邊上的權(quán)值，則需要有特定的算法求解。 2021年4月19日星期一第113頁重慶工商大學計算機與信息工程學院