綜合材料2006浙江隊(duì)集訓(xùn)7

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

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

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

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

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

6、vi的所有遍歷子結(jié)點(diǎn)的low值均小于vi的遍歷序，則vi不是關(guān)節(jié)點(diǎn)。三、圖的連通性問(wèn)題關(guān)節(jié)點(diǎn)關(guān)節(jié)點(diǎn)的計(jì)算low值的計(jì)算lowi = minvisitedi, visitedj, lowkvj是vi的非遍歷子結(jié)點(diǎn)的鄰接點(diǎn)；vk是vi的遍歷子結(jié)點(diǎn)；ALFMJBHDCEGKI10128119671354321遍歷序MLKJIHGFEDCBA頂點(diǎn)112182214211-low10859476122311113完成序A-B-CD-EH-G-K-IM-J-LF四、有向無(wú)環(huán)圖有向無(wú)環(huán)圖概念四、有向無(wú)環(huán)圖拓?fù)渑判蛲負(fù)渑判虻母拍钏?、有向無(wú)環(huán)圖拓?fù)渑判蛲負(fù)渑判蛩惴‥1：計(jì)算各頂點(diǎn)的入度；E2：將入度為0的頂點(diǎn)入

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

8、3：計(jì)算每條弧的最早開(kāi)始時(shí)間e和最遲開(kāi)始時(shí)間l，若e等于l，則輸出該弧（關(guān)鍵?。?；四、有向無(wú)環(huán)圖關(guān)鍵路徑關(guān)鍵路徑的計(jì)算ve的計(jì)算初值的選擇vek=max vei + wik | E 四、有向無(wú)環(huán)圖關(guān)鍵路徑關(guān)鍵路徑的計(jì)算vl的計(jì)算初值的選擇vli=min vlj-wij | E 四、有向無(wú)環(huán)圖關(guān)鍵路徑關(guān)鍵路徑的計(jì)算e和l的計(jì)算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五、最短路徑單源起點(diǎn)的最短路徑問(wèn)題五、最短路徑Dijstra算法算法思想Idea1設(shè)，M = P0,i, P0,i是v0到vi的最短路徑 | i=1n-1 ，設(shè)，已知權(quán)值W0

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

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