1、7.1 圖的定義和術(shù)語,定義：,圖 (Graph) 是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，由頂 點集合及頂點間的關(guān)系（也稱弧或邊）集合組成?？?以表示為：G(V, VR) 其中 V 是頂點的有窮非空集合； VR 是頂點之間關(guān)系 的有窮集合，也叫做弧或邊集合?；∈琼旤c的有序?qū)Γ?邊是頂點的無序?qū)Α?生成樹：所有頂點均由邊連接在一起，但不存在回路的圖。,一個圖可以有許多棵不同的生成樹。,注,所有生成樹具有以下共同特點： 生成樹的頂點個數(shù)與圖的頂點個數(shù)相同； 生成樹是圖的極小連通子圖； 一個有 n 個頂點的連通圖的生成樹有 n-1 條邊； 生成樹中任意兩個頂點間的路徑是唯一的； 在生成樹中再加一條邊必然形成回

2、路。,含 n 個頂點 n-1 條邊的圖不一定是生成樹。,7.2 圖的存儲結(jié)構(gòu),7.2.1 數(shù)組表示法（鄰接矩陣表示法）,特點：,無向圖的鄰接矩陣對稱，可壓縮存儲；有 n 個頂點的無向圖 需存儲空間為 n(n-1)/2。,有向圖鄰接矩陣不一定對稱；有 n 個頂點的有向圖需存儲空 間為n，空間復(fù)雜度為O(n2)，用于稀疏圖時空間浪費嚴重。,無向圖中頂點 vi 的度 TD(vi) 是鄰接矩陣中第 i 行 1 的個數(shù)。,有向圖中,頂點 vi 的出度是鄰接矩陣中第 i 行 1 的個數(shù)。,頂點 vi 的入度是鄰接矩陣中第 i 列 1 的個數(shù)。,7.2.2 鄰接表（類似于樹的孩子鏈表表示法）,3,1,4,2

3、,0,4,3,1,2,0,2,1,特點：,若無向圖中有 n 個頂點、e 條邊，則其鄰接表需 n 個頭結(jié)點 和 2e 個表結(jié)點。適宜存儲稀疏圖。,無向圖中頂點 vi 的度為第 i 個單鏈表中的結(jié)點數(shù)。,0,1,2,3,2,1,3,0,v1,v3,v4,v2,鄰接表,逆鄰接表,頂點 vi 的出度為第 i 個單鏈 表中的結(jié)點個數(shù)。,特點：,頂點 vi 的入度為整個單鏈表 中鄰接點域值是 i -1 的結(jié)點 個數(shù)。,找出度易，找入度難。,找入度易，找出度難。,頂點 vi 的入度為第 i 個單鏈 表中的結(jié)點個數(shù)。,頂點 vi 的出度為整個單鏈表 中鄰接點域值是 i -1 的結(jié)點 個數(shù)。,弧結(jié)點,7.2.3

4、 十字鏈表,頂點結(jié)點,7.2.3 鄰接多重表（無向圖的另一種鏈式存儲結(jié)構(gòu)）,鄰接表優(yōu)點：容易求得頂點和邊的信息。 缺點：某些操作不方便（如：刪除一條邊需找表示此 邊的兩個結(jié)點）。,鄰接多重表：每條邊用一個結(jié)點表示。其結(jié)點結(jié)構(gòu)如下：,標志域 標記此邊是 否被搜索過,7.2.3 鄰接多重表（無向圖的另一種鏈式存儲結(jié)構(gòu)）,7.3 圖的遍歷,深度優(yōu)先遍歷（Depth_First SearchDFS ） 廣度優(yōu)先遍歷（Breadth_Frist SearchBFS）,7.4.3 最小生成樹,構(gòu)造最小生成樹方法：,方法一：普里姆 (Prim) 算法。,方法二：克魯斯卡爾 (Kruskal) 算法。,最小生

5、成樹 可能不惟一,拓撲排序的方法：,在有向圖中選一個沒有前驅(qū)的頂點且輸出之。,從圖中刪除該頂點和所有以它為尾的弧。,重復(fù)上述兩步，直至全部頂點均已輸出；或者當(dāng)圖中 不存在無前驅(qū)的頂點為止,一個AOV網(wǎng)的拓撲序列不是唯一的,7.5.2 關(guān)鍵路徑,把工程計劃表示為有向圖，用頂點表示事件，弧表示活 動，弧的權(quán)表示活動持續(xù)時間。每個事件表示在它之前的活 動已經(jīng)完成，在它之后的活動可以開始。稱這種有向圖為邊 表示活動的網(wǎng)絡(luò)，簡稱為AOE （Activity On Edge）網(wǎng)。,對于AOE網(wǎng)，我們關(guān)心兩個問題： (1) 完成整項工程至少需要 多少時間？ (2) 哪些活動是影響工程進 度的關(guān)鍵？,求關(guān)鍵路徑步驟： 求 ve(i)、vl(j) 求 e(i)、l(i) 計算 l(i) - e(i),7.6 最短路徑,7.6.1 單源點最短路徑（從某個源點到其余各頂點的最短路徑）,迪杰斯特拉（Dijkstra）算法： 按路徑長度遞增次序產(chǎn)生各頂點的最短路徑。,7.6.2 每一對頂點之間的最短路徑,方法一：每次以一個頂點為源點， 重復(fù)執(zhí)