【正文】 抽象數(shù)據(jù)類型圖的定義 圖的存儲表示 圖的遍歷 最小生成樹 兩點之間的最短路徑問題 拓撲排序 關鍵路徑 圖 是由一個 頂點集 V 和一個 弧集 R構成的數(shù)據(jù)結構。 Graph = (V , R ) 其中， R＝ {v,w| v,w∈ V 且 P(v,w)} v,w表示從 v 到 w 的一條弧，并稱 v 為弧頭， w 為弧尾。 圖的結構定義 : V W 由于“弧”是有方向的，因此稱由頂點集和弧集構成的圖為 有向圖 。 A B E C D 例如 : G1 = (V1, VR1) 其中 V1={A, B, C, D, E} VR1={A,B, A,E, B,C, C,D, D,B, D,A, E,C } 若 v, w?VR 必有 w, v?VR, 則稱 (v,w) 為頂點 v 和頂點 w 之間存在一條 邊 。 B C A D F E 由頂點集和邊集構成的圖稱作 無向圖 。 例如 : 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) } 名詞和術語 網、子圖 完全圖 、 稀疏圖、稠密圖 鄰接點、度、入度、出度 路徑、路徑長度、簡單路徑 、 簡單回路 連通圖、連通分量、 強連通圖、強連通分量 生成樹、生成森林 A B E C F A E A B B C 設圖 G=(V,{VR}) 和圖 G?=(V?,{VR?}), 且 V??V, VR??VR, 則稱 G? 為 G 的 子圖 。 15 9 7 21 11 3 2 弧或邊帶權的圖分別稱作 有向網 或無向網 。 假設圖中有 n 個頂點， e 條邊，則 含有 e=n(n1)/2 條邊的無向圖稱作完全圖 ； 含有 e=n(n1) 條弧的有向圖稱作 有向完全圖 ； 若邊或弧的個數(shù) enlogn，則稱作稀疏圖 ， 否則稱作 稠密圖 。 假若頂點 v 和頂點 w 之間存在一條邊， 則稱頂點 v 和 w 互為 鄰接點 ， A C D F E 例如 : ID(B) = 3 ID(A) = 2 邊 (v,w) 和頂點 v 和 w 相 關聯(lián) 。 和頂點 v 關聯(lián)的邊的數(shù)目定義為頂點 v的 度 。 B 頂點的 出度 : 以頂點 v 為弧尾的弧的數(shù)目； A B E C F 對有向圖來說 ， 頂點的 入度 : 以頂點 v為弧頭的弧的數(shù)目 。 頂點的 度 (TD)= 出度 (OD)+入度 (ID) 例如 : ID(B) = 2 OD(B) = 1 TD(B) = 3 設圖 G=(V,{VR})中的一個頂點序列 { u=vi,0,vi,1, …, v i,m=w}中 ， (vi,j1,vi,j)?VR 1≤j≤m, 則稱從頂點 u 到頂點 w 之間存在一條 路徑 。 路徑上邊的數(shù)目稱作 路徑長度 。 A B E C F 如 :長度為 3的路徑{A,B,C,F} 簡單路徑 :序列中頂點不重復出現(xiàn)的路徑。 簡單回路 :序列中第一個頂點和最后一個頂點相同的路徑。 若圖 G中任意兩個頂點之間都有路徑相通 ，則稱此圖為 連通圖 ； 若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的 連通分量 。 B A C D F E B A C D F E 若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為 強連通圖 。 A B E C F A B E C F 對有向圖， 否則，其各個強連通子圖稱作它的 強連通分量 。 假設一個連通圖有 n 個頂點和 e 條邊，其中 n1 條邊和 n 個頂點構成一個極小連通子圖，稱該極小連通子圖為此連通圖的 生成樹 。 對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的 生成森林 。 B A C D F E 結構的建立和銷毀 插入或刪除頂點 對鄰接點的操作 對頂點的訪問操作 遍歷 插入和刪除弧 基本操作 CreatGraph(amp。G, V, VR): // 按定義 (V, VR) 構造圖 DestroyGraph(amp。G): // 銷毀圖 結構的建立和銷毀 對頂點的訪問操作 LocateVex(G, u)。 // 若 G中存在頂點 u，則返回該頂點在 // 圖中“ 位置 ” ；否則返回其它信息。 GetVex(G, v)。 // 返回 v 的值。 PutVex(amp。G, v, value)。 // 對 v 賦值 value。 對鄰接點的操作 FirstAdjVex(G, v)。 // 返回 v 的“ 第一個鄰接點 ” 。若該頂點 //在 G 中沒有鄰接點，則返回“空”。 NextAdjVex(G, v, w)。 // 返回 v 的（相對于 w 的） “ 下一個鄰接 // 點 ”。若 w 是 v 的最后一個鄰接點，則 // 返回“空”。 插入或刪除頂點 InsertVex(amp。G, v)。 //在圖 G中增添新頂點 v。 DeleteVex(amp。G, v)。 // 刪除 G中頂點 v及其相關的弧。 插入和刪除弧 InsertArc(amp。G, v, w)。 // 在 G中增添弧 v,w，若 G是無向的， //則還增添對稱弧 w,v。 DeleteArc(amp。G, v, w)。 //在 G中刪除弧 v,w，若 G是無向的， //則還刪除對稱弧 w,v。 遍 歷 DFSTraverse(G, v, Visit())。 //從頂點 v起 深度優(yōu)先 遍歷圖 G，并對每 //個頂點調用函數(shù) Visit一次且僅一次。 BFSTraverse(G, v, Visit())。 //從頂點 v起 廣度優(yōu)先 遍歷圖 G，并對每 //個頂點調用函數(shù) Visit一次且僅一次。 圖的存儲表示 一、 圖的數(shù)組 (鄰接矩陣 )存儲表示 二、圖的鄰接表存儲表示 三、有向圖的十字鏈表存儲表示 四、無向圖的鄰接多重表存儲表示 Aij={ 0 (i,j)?VR 1 (i,j)?VR 一、 圖的數(shù)組 (鄰接矩陣 )存儲表示 B A C D F E 定義 :矩陣的元素為 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 無向圖的鄰接矩陣為對稱矩陣 A B C D E F A B C D E F 有向圖的鄰接矩陣為非對稱矩陣 A B D C E 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 A B C D E A B C D E 鄰接矩陣表示法特點： 1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次； 2）頂點 v的度：在無向圖中等于二維數(shù)組對應行（或列） 中 1的個數(shù)；在有向圖中 , 統(tǒng)計第 i 行 1 的個數(shù)可得 頂點 i 的出度，統(tǒng)計第 j 列 1 的個數(shù)可得頂點 j 的 入度。 3）判斷兩頂點 v、 u是否為鄰接點：只需判二維數(shù)組對應 分量是否為 1； 4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對 應分量賦值 1或清 0； 5）設存儲頂點的一維數(shù)組大小為 n(圖的頂點數(shù) n), G占 用存儲空間： n+n2； G占用存儲空間只與它的頂點數(shù)有關 ，與邊數(shù)無關；適用于邊稠密的圖； typedef struct ArcCell { // 弧的定義 VRType adj。 // VRType是頂點關系類型 /