數(shù)據(jù)結(jié)構(gòu)講義六：圖

1、第六章 圖6.1 圖的定義和術(shù)語v圖(Graph)圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)有向圖有向圖G是由兩個(gè)集合V(G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是有向邊（也稱?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記為，v,w是頂點(diǎn)，v為弧尾，w為弧頭v無向圖無向圖G是由兩個(gè)集合V(G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記為（v,w）或（w,v)，并且（v,w)=(w,v)例245136G1圖G1中：V(G1)=1

2、,2,3,4,5,6 E(G1)=, , , , , , 例157324G26圖G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)v有向完備圖n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)v無向完備圖n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2v權(quán)與圖的邊或弧相關(guān)的數(shù)叫v網(wǎng)帶權(quán)的圖叫v子圖如果圖G(V,E)和圖G(V,E),滿足：lVVlEE 則稱G為G的子圖v頂點(diǎn)的度l無向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù)l有向圖中，頂點(diǎn)的度分成入度與出度u入度：以該頂點(diǎn)為頭的弧的數(shù)目u出度：以該頂點(diǎn)為尾的弧的數(shù)目

3、v路徑路徑是頂點(diǎn)的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1jn)v路徑長(zhǎng)度沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和v回路第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫v簡(jiǎn)單路徑序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫v簡(jiǎn)單回路除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫v連通從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是連通的v連通圖圖中任意兩個(gè)頂點(diǎn)都是連通的叫v連通分量非連通圖的每一個(gè)連通部分叫v強(qiáng)連通圖有向圖中，如果對(duì)每一對(duì)Vi,VjV, ViVj,從Vi到Vj 和從Vj到 Vi都存在路徑，則稱G是例213213有向完備圖無向完備圖356例245136圖與子圖例245136G

4、1頂點(diǎn)2入度：1 出度：3頂點(diǎn)4入度：1 出度：0例157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：4例157324G26例245136G1路徑：1，2，3，5，6，3路徑長(zhǎng)度：5簡(jiǎn)單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡(jiǎn)單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：1，2，3，1連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例2451366.2 圖的存儲(chǔ)結(jié)構(gòu)多重鏈表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3鄰接矩陣表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣v

5、定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣，其它0E(G)v,v或)v,(v若1,jijijiA例G12413例15324G200110001011101010101010100001100000000110v特點(diǎn)：l無向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為n(n+1)/2l有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為nl無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和l有向圖中，u頂點(diǎn)Vi的出度是A中第i行元素之和u頂點(diǎn)Vi的入度是A中第i列元素之和l網(wǎng)絡(luò)的鄰接矩陣可定義為：，其它0E(G)v,v或)v,(

6、v若,jijiijjiA0618360240120078400530750例1452375318642關(guān)聯(lián)矩陣表示頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系的矩陣v定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)，e0條邊的圖，G的關(guān)聯(lián)矩陣A是具有以下性質(zhì)的ne階矩陣為頭邊相連，且頂點(diǎn)與邊不相連頂點(diǎn)與為尾邊相連，且頂點(diǎn)與有向圖：ijijiijijiA, 1, 0, 1,邊不相連頂點(diǎn)與，邊相連頂點(diǎn)與，無向圖：jijijiA01,11000110000110114321例G124131234例15324G2123456110000000110011100101001000011432156例BDAC123456ABCD4321561

7、01011110000011100000111v特點(diǎn)l關(guān)聯(lián)矩陣每列只有兩個(gè)非零元素，是稀疏矩陣；n越大，零元素比率越大l無向圖中頂點(diǎn)Vi的度TD(Vi)是關(guān)聯(lián)矩陣A中第i行元素之和l有向圖中，u頂點(diǎn)Vi的出度是A中第i行中“1”的個(gè)數(shù)u頂點(diǎn)Vi的入度是A中第i行中“-1”的個(gè)數(shù)鄰接表v實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。﹖ypedef struct node int adjvex; /鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置 struct node *next; /鏈域，指示下一條邊或弧JD;adjvex next表頭

8、接點(diǎn)：typedef struct tnode int vexdata; /存放頂點(diǎn)信息 struct node *firstarc; /指示第一個(gè)鄰接點(diǎn)TD;TD gaM; /ga0不用vexdata firstarc例G1bdac例aecbdG21234acdbvexdata firstarc 3 2 4 1adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1 5 3 2 3v特點(diǎn)l無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)l有向圖中u頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)u頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域

9、值是i的結(jié)點(diǎn)個(gè)數(shù)l逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next有向圖的十字鏈表表示法弧結(jié)點(diǎn)：typedef struct arcnode int tailvex, headvex; /弧尾、弧頭在表頭數(shù)組中位置 struct arcnode *hlink；/指向弧頭相同的下一條弧 struct arcnode *tlink; /指向弧尾相同的下一條弧AD;tailvex headvex hlink tlink頂點(diǎn)結(jié)點(diǎn)：typedef struct dnode int data; /存與

10、頂點(diǎn)有關(guān)信息 struct arcnode *firstin；/指向以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn) struct arcnode *firstout; /指向以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)DD;DD gM; /g0不用data firstin firstout例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1無向圖的鄰接多重表表示法頂點(diǎn)結(jié)點(diǎn)：typedef struct dnode int data; /存與頂點(diǎn)有關(guān)的信息 struct node *firstedge; /指向第一條依附于該頂點(diǎn)的邊DD;DD gaM; /ga0不用data firstedge邊結(jié)

11、點(diǎn)：typedef struct node int mark; /標(biāo)志域 int ivex, jvex; /該邊依附的兩個(gè)頂點(diǎn)在表頭數(shù)組中位置 struct node *ilink, *jlink; /分別指向依附于ivex和jvex的下一條邊JD;mark ivex ilink jvex jlink例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 26.3 圖的遍歷深度優(yōu)先遍歷(DFS)v方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)

12、未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5v深度優(yōu)先遍歷算法l遞歸算法開始訪問V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)wV0W訪問過結(jié)束NYNYDFS開始標(biāo)志數(shù)組初始化Vi=1Vi訪問過DFSVi=Vi+1Vi=

13、Vexnums結(jié)束NNYYCh6_1.cV1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V4V1V2V4V5V3V7V6V8例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍歷：V1V3 V7 V6 V2 V4 V8 V5廣度優(yōu)先遍歷(BFS)v方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)

14、；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V5v廣度優(yōu)先遍歷算法開始標(biāo)志數(shù)組初始化Vi=1

15、Vi訪問過BFSVi=Vi+1Vi=Vexnums結(jié)束NNYYCh6_2.c開始訪問V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V下一鄰接點(diǎn)ww訪問過結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪問w,置標(biāo)志w入隊(duì)NaaY例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列：10 1 2 3 4 54fr遍歷序列：1 40 1 2 3 4 54 3fr遍歷序列：1 4 3例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5

16、 1 1 4 3 2 20 1 2 3 4 54 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 2 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 fr遍歷序列：1 4 3 2 5例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 26.4 生成樹生成樹v定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫v深度優(yōu)先

17、生成樹與廣度優(yōu)先生成樹v生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的v說明l一個(gè)圖可以有許多棵不同的生成樹l所有生成樹具有以下共同特點(diǎn)：u生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同u生成樹是圖的極小連通子圖u一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊u生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的u在生成樹中再加一條邊必然形成回路l含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹GHKIV1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4

18、V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林最小生成樹v問題提出要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)表示城市權(quán)城市間建立通信線路所需花費(fèi)代價(jià)希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小最小代價(jià)生成樹v問題分析1654327131791812752410n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把 所有城市（頂點(diǎn)）均連起來，且總耗費(fèi) （各邊權(quán)值之和）最小v構(gòu)造最小生成樹方法l方

19、法一：普里姆(Prim)算法u算法思想：設(shè)N=(V,E)是連通網(wǎng)，TE是N上最小生成樹中邊的集合Y初始令U=u0,(u0V), TE=Y 在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)Y 將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)Y 重復(fù)上述操作直至U=V為止，則T=(V,TE)為N的最小生成樹u算法實(shí)現(xiàn)：圖用鄰接矩陣表示u算法描述u算法評(píng)價(jià)：T(n)=O(n)Ch6_3.c例16543265135664251311631416431421164321425165432142531062460632055465051350651600 1 2 3 4 50 1 2

20、3 4 51-21-41-1例16543265135664251-51-3165432651356642516543214253l方法二：克魯斯卡爾(Kruskal)算法u算法思想：設(shè)連通網(wǎng)N=(V,E)，令最小生成樹Y初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,)，每個(gè)頂點(diǎn)自成一個(gè)連通分量Y 在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊Y 依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止例165432651356642516543212345（0）用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息（1）初始時(shí)，令每個(gè)頂點(diǎn)的j

21、ihe互不相同；每個(gè)邊的flag為0（2）選出權(quán)值最小且flag為0的邊（3）若該邊依附的兩個(gè)頂點(diǎn)的jihe 值不同，即非連通，則令 該邊的flag=1, 選中該邊；再令該邊依附的兩頂點(diǎn)的jihe 以及兩集合中所有頂點(diǎn)的jihe 相同 若該邊依附的兩個(gè)頂點(diǎn)的jihe 值相同，即連通，則令該 邊的flag=2, 即舍去該邊（4）重復(fù)上述步驟，直到選出n-1條邊為止 頂點(diǎn)結(jié)點(diǎn)：typedef struct int data; /頂點(diǎn)信息 int jihe; VEX;邊結(jié)點(diǎn)：typedef struct int vexh, vext; /邊依附的兩頂點(diǎn) int weight; /邊的權(quán)值 int f

22、lag; /標(biāo)志域EDGE;u算法實(shí)現(xiàn)：例1654326513566425Ch6_30.cu算法描述：datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222165432123456.5 拓?fù)渑判?由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判? 問題提出：學(xué)生選修課程問題頂點(diǎn)表示課程有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)拓?fù)渑判?定義

23、vAOV網(wǎng)用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex network)，簡(jiǎn)稱AOV網(wǎng)l若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼lAOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件v拓?fù)渑判虬袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程叫l(wèi)檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒╲在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之v從圖中刪除該頂點(diǎn)和所有以它為尾的弧v重復(fù)上述兩步，直至全部頂點(diǎn)均已輸

24、出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止例課程代號(hào) 課程名稱 先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一個(gè)AOV網(wǎng)

25、的拓?fù)湫蛄胁皇俏ㄒ坏腃1C2C3C4C5C6C7C8C9C10C11C12C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2（2）C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3（3）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4（4）C6C8C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9C6C8C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10（8）C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5

26、（5）C6C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7（6）C6C8C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10-C11（9）C8C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10-C11-C6（10）C8拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12（11）拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12-C8（12）算法實(shí)現(xiàn)v以鄰接表作存儲(chǔ)結(jié)構(gòu)v把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧v棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度

27、減1；若Vk的入度為0則進(jìn)棧v重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤呧徑颖斫Y(jié)點(diǎn)：typedef struct node int vex; /頂點(diǎn)域 struct node *next; /鏈域JD;表頭結(jié)點(diǎn)：typedef struct tnode int in; /入度域 struct node *link; /鏈域TD;TD gM; /g0不用32104算法描述例1234560122inlink 5 5 4 3vex next3 2 5 2 40123456Ch6_40.ctop16toptop0122inlink 5 5 4 3vex n

28、ext3 2 5 2 40123456輸出序列：63210416toptop0122inlink 5 5 4 3vex next3 2 5 2 40123456輸出序列：6321041topp0122inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6321041topp0122inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6321041topp0112inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6321041topp0112inlink 5 5 4 3vex next2 2

29、5 2 40123456輸出序列：6321041topp=NULL0112inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 1321041toptop0112inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104topp0102inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104topp40102inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top0102inlink 5 5 4 3vex next

30、2 2 5 2 40123456輸出序列：6 132104p4top0002inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top30002inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top30002inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top30001inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top30001inlink 5 5 4 3vex

31、next2 2 5 2 40123456輸出序列：6 132104p=NULL4top30001inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 1 3321044top30001inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 1 3321044topp0001inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044topp0001inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044topp0000inli

32、nk 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044topp20000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044topp20000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044top2p=NULL0000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3 2321044top2p=NULL0000inlink 5 5 4 3vex next1 2 5 2 40123456輸出

33、序列：6 1 3 2321044topp=NULL0000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3 2 4321044top0000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3 2 432104topp0000inlink 5 5 4 3vex next0 2 5 2 40123456輸出序列：6 1 3 2 432104topp50000inlink 5 5 4 3vex next0 2 5 2 40123456輸出序列：6 1 3 2 432104topp=NULL50000inli

34、nk 5 5 4 3vex next0 2 5 2 40123456輸出序列：6 1 3 2 4 532104top50000inlink 5 5 4 3vex next0 2 5 2 40123456輸出序列：6 1 3 2 4 532104topp=NULL算法分析建鄰接表：T(n)=O(e)搜索入度為0的頂點(diǎn)的時(shí)間：T(n)=O(n)拓?fù)渑判颍篢(n)=O(n+e)Ch6_4.c6.6 關(guān)鍵路徑問題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開始例 設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件事件 V1表示整個(gè)工程開始事件V9表示整個(gè)工

35、程結(jié)束問題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？ （2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4定義vAOE網(wǎng)(Activity On Edge)也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間v路徑長(zhǎng)度路徑上各活動(dòng)持續(xù)時(shí)間之和v關(guān)鍵路徑路徑長(zhǎng)度最長(zhǎng)的路徑叫vVe(j)表示事件Vj的最早發(fā)生時(shí)間vVl(j)表示事件Vj的最遲發(fā)生時(shí)間ve(i)表示活動(dòng)ai的最早開始時(shí)間vl(i)表示活動(dòng)ai的最遲開始時(shí)間vl(i)-e(i)表示完成活動(dòng)ai的時(shí)間

36、余量v關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)叫，即l(i)=e(i)的活動(dòng)問題分析v如何找e(i)=l(i)的關(guān)鍵活動(dòng)？設(shè)活動(dòng)ai用弧表示，其持續(xù)時(shí)間記為：dut()則有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut()jkaiv如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開始向前遞推為頭的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei2 ,),()()(2)從Vl(n)=Ve(n)開始向后遞推為尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11 ,),()()(求關(guān)鍵路徑步驟v求Ve(i)v求Vl(j)v求e(i)v求l(i)v計(jì)算l(i)

37、-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn) Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng) e l l-e00002266046258377077071031616014140033算法實(shí)現(xiàn)v以鄰接表作存儲(chǔ)結(jié)構(gòu)v從源點(diǎn)V1出發(fā)，令Ve1=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的Veiv從匯點(diǎn)Vn出發(fā)，令Vln=Ven,按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的Vliv根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的ei和li,找出ei=li的關(guān)鍵活動(dòng)鄰接

38、表結(jié)點(diǎn)：typedef struct node int vex; /頂點(diǎn)域 int length; struct node *next; /鏈域JD;表頭結(jié)點(diǎn)：typedef struct tnode int vexdata; int in; /入度域 struct node *link; /鏈域TD;TD gM; /g0不用算法描述v輸入頂點(diǎn)和弧信息，建立其鄰接表v計(jì)算每個(gè)頂點(diǎn)的入度v對(duì)其進(jìn)行拓?fù)渑判騦排序過程中求頂點(diǎn)的Veil將得到的拓?fù)湫蛄羞M(jìn)棧v按逆拓?fù)湫蛄星箜旤c(diǎn)的Vliv計(jì)算每條弧的ei和li,找出ei=li的關(guān)鍵活動(dòng)Ch6_20.c987645321a2=4a3=5a5=1a6=2a

39、9=4a1=6a4=1a7=9a8=7a10=2a11=4987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 946.7 最短路徑問題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中， 各邊上權(quán)值之和最小的一條路徑最短路徑從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑51643208562301371732913長(zhǎng)度最短路徑813192120v迪杰斯特拉(Dijkstra)算法思想按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，保證：（1）從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長(zhǎng)度都不大于 從V0到T中任何頂點(diǎn)的最短路徑長(zhǎng)度 （2）每個(gè)頂點(diǎn)對(duì)應(yīng)