綜合材料2006浙江隊集訓7

1、第七章 圖一、圖圖的ADT定義G = (V, E)基本術語頂點、弧弧尾、弧頭鄰接出度、入度有向圖、無向圖邊稀疏圖、稠密圖網(wǎng)完全圖子圖G=(V, E)路徑P=(v0v1vn-1)回路R=(v0v1vn-1v0)一、圖圖的實現(xiàn)鄰接矩陣法頂點表0a1b2c3d4e5f6g012345600000011100100002000010030000000400010005000010160101000鄰接矩陣一、圖圖的實現(xiàn)鄰接表法6543210gfedcba頂點表652446313一、圖圖的實現(xiàn)重鄰接表法十字鏈表法二、圖的遍歷深度優(yōu)先遍歷E1：以任一未被遍歷過的頂點為起點，先訪問該頂點；E2：依次深度優(yōu)先

2、遍歷該頂點的所有未被遍歷過的鄰接點；E3：若還存在未被遍歷的頂點，則重復E1；深度優(yōu)先遍歷序：afedgbcabfedcg141223二、圖的遍歷廣度優(yōu)先遍歷E1：以任一未被遍歷的頂點為起點，先訪問該頂點；E2：依次訪問該頂點的所有未被遍歷的鄰接點；E3：依次訪問鄰接點的所有未被遍歷的鄰接點，并依此類推，直到?jīng)]有可訪問的頂點。E4：若還存在未被遍歷的頂點，則重復E1；廣度優(yōu)先遍歷序：afgedbcabfedcg112432三、圖的連通性問題連通圖和連通分量三、圖的連通性問題強連通圖和強連通分量abfedcg三、圖的連通性問題強連通分量的計算E1：正向深度優(yōu)先遍歷，計算遍歷結束序，記入finis

3、hed向量中；E2：按照finished倒序選擇起點，逆向深度優(yōu)先遍歷，每一趟遍歷所經(jīng)過的頂點以及與這些頂點相關的弧構成一個強連通分量。finished序：decbgaf第1趟反向深度遍歷：f第2趟反向深度遍歷：a第3趟反向深度遍歷：gdecb三、圖的連通性問題生成樹和生成森林三、圖的連通性問題最小生成樹概念三、圖的連通性問題最小生成樹MST性質設無向圖G=(V, E)三、圖的連通性問題最小生成樹Prim算法E1：任取一個頂點構成U=v0；構造向量cost0n-1和adj0n-1，costi表示頂點vi到U的最短邊的長度，adji表示頂點vi到U的最短邊在U中的鄰接點的下標；其中，viV-U。

4、初始時，生成樹T為空集。E2：重復n-1次E21：從V-U中選出cost值最小的頂點vk，將邊加入到生成樹T中，然后將vk并入U中；E22：修正V-U中各頂點的cost值和adj值；三、圖的連通性問題最小生成樹Kruskal算法E1：將所有的邊按權值排序；E2：設每個頂點為一個獨立的點集，生成樹T為空集；E3：依序掃描每一條邊，直到已輸出n-1條邊：E31：若vi、vj不在同一點集中，則將該邊加入生成樹T中，并合并這兩個點集；否則舍棄該邊；三、圖的連通性問題關節(jié)點關節(jié)點的概念ALFMJBHDCEKGI三、圖的連通性問題關節(jié)點關節(jié)點的計算vi的遍歷序：頂點vi在深度優(yōu)先遍歷中的被遍歷順序號。vi

5、的遍歷子結點：以vi為起點，準備進行深度優(yōu)先遍歷時，vi的未被遍歷的鄰接點稱為vi的遍歷子結點；以vi為根的遍歷子圖：以vi為起點，經(jīng)過一趟深度優(yōu)先遍歷，遍歷到的所有頂點構成的子圖。vi的low值：以vi為根的遍歷子圖可直達的頂點的遍歷序的最小值。12835461179101113399767121三、圖的連通性問題關節(jié)點關節(jié)點的計算遍歷起點（根結點）是否是關節(jié)點的判別以根結點的第一個鄰接點為起點，進行一趟深度優(yōu)先遍歷，若能遍歷到圖上的所有頂點，則根結點不是關節(jié)點；反之，根結點即為關節(jié)點。其他結點是否是關節(jié)點的判別若vi存在某個遍歷子結點，其low值不小于vi的遍歷序，則vi為關節(jié)點；反之，若

6、vi的所有遍歷子結點的low值均小于vi的遍歷序，則vi不是關節(jié)點。三、圖的連通性問題關節(jié)點關節(jié)點的計算low值的計算lowi = minvisitedi, visitedj, lowkvj是vi的非遍歷子結點的鄰接點；vk是vi的遍歷子結點；ALFMJBHDCEGKI10128119671354321遍歷序MLKJIHGFEDCBA頂點112182214211-low10859476122311113完成序A-B-CD-EH-G-K-IM-J-LF四、有向無環(huán)圖有向無環(huán)圖概念四、有向無環(huán)圖拓撲排序拓撲排序的概念四、有向無環(huán)圖拓撲排序拓撲排序算法E1：計算各頂點的入度；E2：將入度為0的頂點入

7、棧；E3：循環(huán)直到?？眨篍31：從棧中彈出一個頂點，輸出到拓撲序中；E32：將該頂點的所有鄰接點的入度減1，若某個鄰接點的入度減為0，則將該鄰接點入棧；入度indegree棧輸出v1v2v3v4v5v6022103v5,v1021102v1v5010002v4,v3v5,v1000001v2,v3v5,v1,v4000001v3v5,v1,v4,v2000000v6v5,v1,v4,v2,v3v5,v1,v4,v2,v3,v6四、有向無環(huán)圖關鍵路徑關鍵路徑的概念及意義四、有向無環(huán)圖關鍵路徑關鍵路徑的計算E1：依拓撲序計算各頂點的最早發(fā)生時間ve；E2：依逆拓撲序計算各頂點的最遲發(fā)生時間vl；E

8、3：計算每條弧的最早開始時間e和最遲開始時間l，若e等于l，則輸出該?。P鍵?。?；四、有向無環(huán)圖關鍵路徑關鍵路徑的計算ve的計算初值的選擇vek=max vei + wik | E 四、有向無環(huán)圖關鍵路徑關鍵路徑的計算vl的計算初值的選擇vli=min vlj-wij | E 四、有向無環(huán)圖關鍵路徑關鍵路徑的計算e和l的計算eij = veilij = vlj-wij0/0/0/0/0/0/0/0/0/0/0/0/5/0/24/41/15/3/21/18/28/41/50/62/5/620/6224/6241/6215/623/6221/6218/6228/6241/6250/6262/625

9、/50/024/2441/4115/153/921/2718/1928/2941/4750/5062/625/50/024/2441/4115/153/921/2718/1928/2941/4750/5062/620/00/65/125/53/113/915/1615/4324/2418/1921/2728/4228/2915/1541/4141/4350/5033/470/05/524/2415/1541/4150/50五、最短路徑單源起點的最短路徑問題五、最短路徑Dijstra算法算法思想Idea1設，M = P0,i, P0,i是v0到vi的最短路徑 | i=1n-1 ，設，已知權值W0

10、,k=min( W0,i | E )，即，是v0到其他各頂點的直達弧中最短的，則，(v0,vk)M，且(v0,vk)是中最短的一條路徑！五、最短路徑Dijstra算法算法思想Idea2設，M = P0,i, P0,i是v0到vi的最短路徑 | i=1n-1 ，設，P0,k=(v0,vk)是M中的最短路徑，P0,i是中的次短路徑，則，P0,i=(v0,vi)或0,i=(v0,vk,vi)五、最短路徑Dijstra算法算法思想Idea3設，M = P0,i, P0,i是v0到vi的最短路徑 | i=1n-1 ，設，已知M的一個子集U，且U中的路徑均短于M-U中的路徑，設，P0,i是M-U中的最短的

11、路徑，則：P0,i=(v0,vi)或P0,i=P0,k+vi，其中P0,kU五、最短路徑Dijstra算法設輔助向量u0n-1、shortest0n-1和path0n-1；ui為表示從v0到vi的最短路徑已經(jīng)求出，為表示尚未求出；shortesti記錄目前已知的從v0到vi的較短路徑的長度；pathi記錄目前已知的從v0到vi的較短路徑；初始時，設置從v0到vi的直達弧為目前已知的較短路徑；五、最短路徑Dijstra算法E1：初始化輔助向量u、shortest、path；E2：循環(huán)n-1次：E21：從M-U中選擇最小的shortestk；E22：將vk并入中;E23：對M-U中的各頂點vi的已知較短路徑進行修正：若P0,k+i的長度短于目前已知的P0,i的長度，則用P0,k+i取代原P0,i；CODING五、最短路徑任兩點間最短路徑問題五、最短路徑Floyd算法算法思想定義P(i,j,k)為：從vi到vj，由序號不大于k的頂點為中間點（或直達）可構成的最