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