數(shù)據(jù)結(jié)構(gòu)第七章

1、1第七章 圖地圖染色北京公交查詢系統(tǒng)鋪設(shè)線路電網(wǎng)輸電模擬導(dǎo)游系統(tǒng) V5 V01006030102010550 V1 V2 V3 V42第七章 圖圖的定義圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷圖的應(yīng)用最小生成樹最短路徑拓?fù)渑判蜿P(guān)鍵路徑 V5 V01006030102010550 V1 V2 V3 V43 圖圖是由一個(gè)是由一個(gè)頂點(diǎn)集頂點(diǎn)集 V 和一個(gè)和一個(gè)弧集弧集 R構(gòu)成構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V, R )其中，VR| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱 v 為弧尾弧尾，w 為弧頭弧頭。4 由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖有向圖。EACB

2、D例如例如: :G = (V，VR)其中V=A, B, C, D, EVR=, , , , , , 5若VR 必有VR, 則稱頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊，用邊，用(v,w)表示。BCAFED由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向無向圖圖。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) 6ABECDAEDBBC設(shè)圖G=(V,VR) 和圖 G=(V,VR),且 VV, VRVR,則稱 G 為 G 的子子圖圖。1597211132 弧或邊帶權(quán)的圖分別稱作有向有向網(wǎng)網(wǎng)

3、或無向網(wǎng)無向網(wǎng)。7假設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則 含有 e=n(n-1)/2 條邊的無向圖稱作完全圖完全圖; 含有 e=n(n-1) 條弧的有向圖稱作 有向完全圖有向完全圖; 若邊或弧的個(gè)數(shù) enlogn，則稱作稀疏圖稀疏圖，否則稱作稠密圖稠密圖。8 假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊，則稱頂點(diǎn)v 和w 互為鄰接點(diǎn)鄰接點(diǎn)，例如例如: :D(B) = 3D(A) = 2 邊(v,w) 和頂點(diǎn)v 和w 相關(guān)聯(lián)關(guān)聯(lián)。頂點(diǎn)頂點(diǎn)v的度：的度：與頂點(diǎn)與頂點(diǎn)v v相相關(guān)聯(lián)的邊的數(shù)目邊的數(shù)目。ACDFEB右側(cè)圖中9頂點(diǎn)的出度出度: : 以頂點(diǎn)v 為弧尾的弧的數(shù)目;ABECD對(duì)對(duì)有向圖有向圖來說來說，頂

4、點(diǎn)的入度入度: : 以頂點(diǎn)v為弧頭的弧的數(shù)目頂點(diǎn)的度度( (D)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1D(B) = 3由于弧有方向性，則有入度入度和出度出度之分10設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列 u=vi0,vi1, , vim=w中，(vi,j-1,vi,j)VR 1jm,則稱從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑路徑。路徑上邊的數(shù)目稱作路徑長(zhǎng)度路徑長(zhǎng)度。ABECD如如:從A到D長(zhǎng)度為 3 的路徑A,B,C,D簡(jiǎn)單路徑簡(jiǎn)單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路簡(jiǎn)單回路:指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。1

5、1若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，稱此圖為連通圖連通圖若無向圖為非連通圖，則圖中各個(gè)極大極大的連連通通子圖子圖稱作此圖的連連通分量通分量。BACDFEBACDFE12 若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖強(qiáng)連通圖。ABECDABECD對(duì)有向圖，對(duì)有向圖，否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量強(qiáng)連通分量BCDAE13BACDFE 假設(shè)一個(gè)連通圖連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中n-1 條邊和n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連極小連通子圖通子圖，稱該極小連通子圖為此連通圖的生成樹生成樹。對(duì)非連通圖非連通圖，則稱由各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林生成森林。B

6、ACDFEBACDFEBACDFE14一一. 圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲(chǔ)表示存儲(chǔ)表示二二. 圖的鄰接表存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示三三. 有向圖的十字鏈表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示 四四. 無向圖的鄰接多重表存儲(chǔ)表示無向圖的鄰接多重表存儲(chǔ)表示五五. 邊集數(shù)組表示邊集數(shù)組表示15用來表示圖中用來表示圖中頂點(diǎn)間頂點(diǎn)間相鄰關(guān)系相鄰關(guān)系的矩陣的矩陣網(wǎng)的鄰接矩陣如何表示？網(wǎng)的鄰接矩陣如何表示？Aij=0 (vi ,vj)VR1 (vi ,vj)VRAij= (vi ,vj)VRwij (vi ,vj)VRBACDFE01234501001010001100010100100111000

7、0011100 鄰接矩陣的定義鄰接矩陣的定義16ABECD1597211132有向圖的鄰接矩陣有向圖的鄰接矩陣有向網(wǎng)的鄰接矩陣有向網(wǎng)的鄰接矩陣ABECD012340 1 0 0 10 0 1 0 00 0 0 1 0110 0 00 0 1 0 0 15 9 3 211 7 21 171) 當(dāng)圖的各頂點(diǎn)的序號(hào)確定后，其鄰接矩陣是唯一確定的；2) 無向圖和無向網(wǎng)的鄰接矩陣是一個(gè)對(duì)稱矩陣；3) 無向圖的鄰接矩陣中第i行(或第i列)的非零元個(gè)數(shù)為第i個(gè)頂點(diǎn)的度； 鄰接矩陣的性質(zhì)鄰接矩陣的性質(zhì)4)有向圖的鄰接矩陣中第i行非零元個(gè)數(shù)為第i個(gè)頂點(diǎn)的出度，第i列非零元個(gè)數(shù)為第i個(gè)頂點(diǎn)的入度；5) 無向圖的邊

8、數(shù)等于矩陣中非零元個(gè)數(shù)的一半，有向圖的弧數(shù)等于矩陣中非零元的個(gè)數(shù)。1() njD ViA ji1() njD ViA ij或18圖圖的鄰接矩陣的的鄰接矩陣的C語言描述語言描述#define VNUM /圖中頂點(diǎn)的最大數(shù)目圖中頂點(diǎn)的最大數(shù)目typedef struct VertexType vexsVNUM； / 定義頂點(diǎn)定義頂點(diǎn) int arcsVNUMVNUM； / 定義邊（弧定義邊（?。?int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù)頂點(diǎn)數(shù)，弧數(shù) Graph ；/定義圖定義圖網(wǎng)網(wǎng)的鄰接矩陣的的鄰接矩陣的C語言描述語言描述#define VNUM /圖中頂點(diǎn)的最大數(shù)目圖中頂點(diǎn)的最大

9、數(shù)目typedef struct VertexType vexsVNUM； / 定義頂點(diǎn)定義頂點(diǎn) WeightType arcsVNUMVNUM； int vexnum, arcnum; / 定義邊的權(quán)值定義邊的權(quán)值 NetGraph ； /定義網(wǎng)定義網(wǎng)頂點(diǎn)的信息頂點(diǎn)的信息：用一維數(shù)組一維數(shù)組來存儲(chǔ)。邊的信息邊的信息： 用鄰接矩陣鄰接矩陣來存儲(chǔ)。 圖的圖的鄰接矩陣鄰接矩陣存儲(chǔ)方式存儲(chǔ)方式19例：已知一個(gè)無向圖，建立其存儲(chǔ)結(jié)構(gòu)。例：已知一個(gè)無向圖，建立其存儲(chǔ)結(jié)構(gòu)。void crt_gragh(Gragh &ga ) scanf(&ga.vexnum，&ga.arcnum)

10、；/頂點(diǎn)數(shù)和邊數(shù)頂點(diǎn)數(shù)和邊數(shù) for(i=0；iga.vexnum；i+) scanf(&ga.vexsi)； for(i=0；iga.vexnum；i+) for(j=0；jga.vexnum；j+ ) ga.arcsij=0； for(k=0；k arcnum ；k+) scanf(&i，&j)； / 讀入一條邊讀入一條邊 ga.arcsi-1j-1=1； ga.arcsj-1i-1=1 /crt_gragh 20已知一個(gè)有向網(wǎng)，建立其存儲(chǔ)結(jié)構(gòu)已知一個(gè)有向網(wǎng)，建立其存儲(chǔ)結(jié)構(gòu)。void crt_net(NetGraph &ga) scanf(&ga.v

11、exnum，&ga.arcnum)；/ 頂點(diǎn)數(shù)和弧數(shù)頂點(diǎn)數(shù)和弧數(shù) for(i=0；iga.vexnum；i+) scanf(ga.vexsi)； for(i=0；iga.vexnum；i+) for(j=0；jga.vexnum；j+ ) ga.arcsij= MAXINT； for(k=0；kga.arcnum；k+) scanf(&i，&j，&w)； / 讀入一條弧和弧上的權(quán)值讀入一條弧和弧上的權(quán)值 ga.arcsi-1j-1= w ； /crt_net 21 鄰接矩陣的特點(diǎn)鄰接矩陣的特點(diǎn)(1) 鄰接矩陣可以采用壓縮存儲(chǔ)方法鄰接矩陣可以采用壓縮存儲(chǔ)方法 無向

12、圖和無向網(wǎng)的鄰接矩陣為對(duì)稱矩陣;對(duì)于邊(弧)個(gè)數(shù)較少的稀疏圖,其鄰接矩陣也稀疏，用行主序存儲(chǔ)矩陣時(shí)存儲(chǔ)空間利用率低。(2) 操作特點(diǎn)操作特點(diǎn) 其存儲(chǔ)特點(diǎn)是一種順序存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)特點(diǎn)是一種順序存儲(chǔ)結(jié)構(gòu)。 較為適合操作有：較為適合操作有： 計(jì)算頂點(diǎn)的度；求一個(gè)頂點(diǎn)的所有鄰接點(diǎn)；插入或刪除一條邊(弧)等； 不太適合的操作有：不太適合的操作有： 頂點(diǎn)的插入和刪除；圖的遍歷等。22方法：方法： 對(duì)圖中對(duì)圖中每個(gè)頂點(diǎn)每個(gè)頂點(diǎn)建立一個(gè)有建立一個(gè)有鄰接關(guān)系鄰接關(guān)系的頂點(diǎn)的頂點(diǎn)單鏈表單鏈表 頂點(diǎn)鄰接表頂點(diǎn)鄰接表； (2) 用一個(gè)用一個(gè)數(shù)組數(shù)組存各鄰接表的頭結(jié)點(diǎn)存各鄰接表的頭結(jié)點(diǎn)(頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)) 對(duì)于無向圖

13、無向圖：第 i 個(gè)鏈表是與Vi相鄰接的所有鄰接點(diǎn)構(gòu)成的單鏈表； 對(duì)于有向圖有向圖：第 i 個(gè)鏈表是以Vi為弧尾的所有弧頭結(jié)點(diǎn)構(gòu)成的單鏈表； data firstarc頂點(diǎn)的結(jié)點(diǎn)頂點(diǎn)的結(jié)點(diǎn)頂點(diǎn)信息頂點(diǎn)信息 頭指針頭指針adjvex nextarc info鄰接表結(jié)點(diǎn)鄰接表結(jié)點(diǎn)( (邊結(jié)點(diǎn)邊結(jié)點(diǎn)) )鄰接點(diǎn)編號(hào)鄰接點(diǎn)編號(hào) 指針指針 邊的權(quán)值邊的權(quán)值23typedef struct ArcNode int adjvex； / 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc； / 指向下一條弧的指針 InfoType info； / 該弧相關(guān)信息 ArcNode ，*ArcPo

14、inter；鄰接表的組織：鄰接表的組織：typedef struct VertexType vexdata；/頂點(diǎn)信息頂點(diǎn)信息 ArcPointer firstarc；/出邊頭指針，指向第一條出邊出邊頭指針，指向第一條出邊 VexNode；typedef struct VexNode adjlistVnum； / 鄰接表 int vexnum，arcnum；/有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) AdjGraph24vexdata firstarc頂點(diǎn)結(jié)點(diǎn)無向圖的鄰接表無向圖的鄰接表 adjvex nextarc弧結(jié)點(diǎn)BACDFE012345102030405060704 1012345ABCDEF35

15、25 01 123 045 無向無向網(wǎng)網(wǎng)的鄰接表的鄰接表 adjvex info nextarc已知圖的鄰接表，如何求無向圖中的頂點(diǎn)vi的度?無向圖中邊的個(gè)數(shù)？1 104 30 4 505 20 0 103 605 40 2 403 70 1 200 301 50 2 605 70 25A B C D E 012340 1 2 3 4 A B C D E3 30 2 0 有向圖的鄰接表有向圖的鄰接表有向圖的有向圖的逆逆鄰接表鄰接表如何求有向圖中弧的個(gè)數(shù)?如何求有向圖中頂點(diǎn)vi的出度和入度？1 4230 1241 ABECD0123426有向圖的鄰接表：有向圖的鄰接表：0 1 2 3 4 A B

16、 C D E1 4230 12ABECD01234如何生成有向圖的鄰如何生成有向圖的鄰接表結(jié)構(gòu)？接表結(jié)構(gòu)？讀入圖的信息：讀入圖的信息：頂點(diǎn)信息頂點(diǎn)信息：A B C D E弧弧(或邊邊)的信息: 例如例如：0，10，41，22，33，03，14，227建立有向圖的鄰接表的算法：建立有向圖的鄰接表的算法：void build_adjlist(AdjGraph &gb) scanf(&gb.vexnum， &gb.arcnum)；/頂點(diǎn)個(gè)數(shù)和弧數(shù)頂點(diǎn)個(gè)數(shù)和弧數(shù) for(i=0；igb.vexnum；i+) scanf(gb.adjlisti.verdata)； gb.adjl

17、isti.firstarc= NULL； for(k=0；k gb.arcnum ；k+) scanf(&i，&j)； / 讀入一對(duì)頂點(diǎn)序號(hào)讀入一對(duì)頂點(diǎn)序號(hào) p=(ArcPointer)malloc(sizeof(ArcNode)； padjver =j； / 生成結(jié)點(diǎn)生成結(jié)點(diǎn) pnextarc= gb.adjlisti.firstarc； gb.adjlisti.firstarc = p； / build_adjlist 問：如何建立無向問：如何建立無向圖的鄰接表？圖的鄰接表？281) 圖的鄰接表的表示不是唯一的，它與鄰接點(diǎn)的讀入順序有關(guān)；2) 無向圖鄰接表中第i個(gè)單鏈表中結(jié)

18、點(diǎn)個(gè)數(shù)為第i個(gè)頂點(diǎn)的度；3) 有向圖鄰接表中第i個(gè)單鏈表中結(jié)點(diǎn)個(gè)數(shù)為第i個(gè)頂點(diǎn)的出度；其逆鄰接表中第i個(gè)單鏈表中結(jié)點(diǎn)個(gè)數(shù)為第i個(gè)頂點(diǎn)的入度； 鄰接表的性質(zhì)鄰接表的性質(zhì)4) 無向圖的邊數(shù)為鄰接表中結(jié)點(diǎn)個(gè)數(shù)的一半，有向圖的弧數(shù)為鄰接表中結(jié)點(diǎn)個(gè)數(shù)。29 鄰接表的特點(diǎn)鄰接表的特點(diǎn) 存儲(chǔ)特點(diǎn)：存儲(chǔ)特點(diǎn)： 是一種順序是一種順序+ +鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，當(dāng)圖中頂點(diǎn)個(gè)數(shù)較多，而邊比較少時(shí)，可節(jié)省大量的空間。較為適合操作有：較為適合操作有： 計(jì)算頂點(diǎn)Vi的出度；求一個(gè)頂點(diǎn)的所有鄰接點(diǎn)；插入或刪除一條邊(弧)；求頂點(diǎn)的一個(gè)鄰接點(diǎn)的下一個(gè)鄰接點(diǎn)等；不太適合的操作有：不太適合的操作有： 頂點(diǎn)的插入和刪除；

19、頂點(diǎn)的入度等。30鏈表結(jié)點(diǎn)鏈表結(jié)點(diǎn)邊起點(diǎn) 邊終點(diǎn)邊終點(diǎn) 下一入邊入邊指針 下一出邊出邊指針弧的權(quán)值tailvex headvexhlinktlinkinfo是有向圖有向圖的鄰接表和逆鄰接表結(jié)合結(jié)合起來得到的一種鏈表。表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)頂點(diǎn)信息 入邊頭指針入邊頭指針 出邊頭指針datafirstinfirstout31typedef struct VexNode / 定義頂點(diǎn)定義頂點(diǎn)(頭頭)結(jié)點(diǎn)結(jié)點(diǎn) VertexType data； ArcNode *firstin，*firstout； VexNode；typedef struct ArcBox / 定義定義弧弧結(jié)點(diǎn)結(jié)點(diǎn) int tailvex，

20、 headvex； struct ArcBox *hlink， *tlink； InfoType info； ArcNode；十字鏈表的組織：十字鏈表的組織：32#define Vnum 20typedef struct VexNode ortholistVnum； /頂點(diǎn)(表頭)結(jié)點(diǎn)數(shù)組 int vexnum，arcnum； /有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OlGraph；有向圖的結(jié)構(gòu)表示有向圖的結(jié)構(gòu)表示(十字鏈表十字鏈表)33ABC2 02 10 20 1弧頭相同弧頭相同012讀入弧： (0,1)、(0,2)、(2,0)、(2,1)弧尾相同弧尾相同 tailvex headvex hlink

21、tlink弧結(jié)點(diǎn)弧結(jié)點(diǎn)data firstin firstout頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)ABC01234ivex ilink jvex jlink邊結(jié)點(diǎn)邊結(jié)點(diǎn) ilink：指示下一條依附于頂點(diǎn)ivex的邊。 jlink：指示下一條依附于頂點(diǎn)jvex的邊。 data： 存儲(chǔ)和該頂點(diǎn)相關(guān)的信息。 firstedge：指示第一條依附于該頂點(diǎn)的邊 data firstedge頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)354 12 42 32 10 30 1 例：對(duì)于無向圖，例：對(duì)于無向圖，讀入順序如下讀入順序如下邊結(jié)點(diǎn)邊結(jié)點(diǎn):0 V01 V1 2 V2 3 V3 4 V4V0V1V2V3V4(0,1)；(0,3)；(2,1)；(2,3

22、)；(2,4)；(4,1)。ivex ilink jvex jlink36typedef struct ENode int ivex，jvex； / 頂點(diǎn)序號(hào)頂點(diǎn)序號(hào) struct enode *ilink，*jlink； ENode；typedef struct VNode DataType data； / 頂點(diǎn)信息頂點(diǎn)信息 ENode *firstedge；/ 指向第一條依附于該頂點(diǎn)的邊結(jié)點(diǎn)指向第一條依附于該頂點(diǎn)的邊結(jié)點(diǎn) VNode； / 定義頭結(jié)點(diǎn)定義頭結(jié)點(diǎn) typedef struct VNode adjmulistVnum； int vexnum，edgenum； / 圖的當(dāng)前頂點(diǎn)數(shù)

23、和邊數(shù)圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) AMLGrahp； 37方法：方法：用一個(gè)一維數(shù)組存儲(chǔ)頂點(diǎn)信息；用一個(gè)一維數(shù)組存儲(chǔ)頂點(diǎn)信息；用一個(gè)一維數(shù)組存圖中所有的邊用一個(gè)一維數(shù)組存圖中所有的邊, 數(shù)組規(guī)模數(shù)組規(guī)模圖邊數(shù)；圖邊數(shù)；每個(gè)數(shù)組元素存一條邊的起點(diǎn)、終點(diǎn)、權(quán)值，次序任意每個(gè)數(shù)組元素存一條邊的起點(diǎn)、終點(diǎn)、權(quán)值，次序任意 無向圖，邊起點(diǎn)可以任意選定；無向圖，邊起點(diǎn)可以任意選定；無權(quán)圖，省去權(quán)值存儲(chǔ)無權(quán)圖，省去權(quán)值存儲(chǔ) 邊集數(shù)組邊集數(shù)組: 12 3bacA12 3BC12 1646123112起點(diǎn)起點(diǎn).233終點(diǎn)終點(diǎn).1234起點(diǎn)起點(diǎn)1123終點(diǎn)終點(diǎn)2332權(quán)值權(quán)值121646適合：適合：對(duì)邊依次處理的運(yùn)算對(duì)

24、邊依次處理的運(yùn)算38遍歷：遍歷：從某頂點(diǎn)出發(fā), 按一定搜索方法,不重復(fù)訪問所有頂點(diǎn)。367984125問題：?jiǎn)栴}：可能存在多條路徑都能到達(dá)同一頂可能存在多條路徑都能到達(dá)同一頂點(diǎn)。點(diǎn)。即要解決頂點(diǎn)的重復(fù)訪問。解決辦法：解決辦法：對(duì)已訪問過的頂點(diǎn)做標(biāo)記。設(shè)輔助數(shù)組: int visitedn；來記錄每個(gè)頂點(diǎn)是否被訪問過。訪問過為1，否則為0。397.3.1 連通圖的深度優(yōu)先搜索連通圖的深度優(yōu)先搜索(Depth-First Search) 訪問頂點(diǎn)的次序： V3V2 V4V9V1V6 V5V8V7深度優(yōu)先遍歷：深度優(yōu)先遍歷： 訪問出發(fā)點(diǎn)V0； 任選一個(gè)出發(fā)點(diǎn)的一個(gè)沒被訪問過的鄰接點(diǎn)，以該點(diǎn)出發(fā)深度優(yōu)

25、先遍歷深度優(yōu)先遍歷； 重復(fù)，直到V0沒有鄰接點(diǎn)沒被訪問；36798412540連通圖的深度優(yōu)先遍歷的連通圖的深度優(yōu)先遍歷的邏輯算法邏輯算法：void df_traver(gragh g，int v) /從從v號(hào)頂點(diǎn)出發(fā)，深度優(yōu)先遍歷連通圖號(hào)頂點(diǎn)出發(fā)，深度優(yōu)先遍歷連通圖 g printf(v)； visitedv=1；for(w=FirstAdjVex(g, v); w; w=NextAdjVex(g, v, w) if(visitedw=0) df_traver(g，w)； / dfs 41typedef struct ArcNode int adjvex； / 該弧所指向的頂點(diǎn)的位置 str

26、uct ArcNode *nextarc； / 指向下一條弧的指針 ArcNode ，*ArcPointer；鄰接表的組織：鄰接表的組織：typedef struct VertexType vexdata；/頂點(diǎn)信息頂點(diǎn)信息 ArcPointer firstarc；/出邊頭指針，指向第一條出邊出邊頭指針，指向第一條出邊 VexNode；typedef struct VexNode adjlistVnum； / 鄰接表 int vexnum，arcnum；/有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) AdjGraph42 void df_traver (AdjGraph g，int v)/g的存儲(chǔ)結(jié)構(gòu)為鄰接表的存

27、儲(chǔ)結(jié)構(gòu)為鄰接表，v為出發(fā)點(diǎn)編號(hào)，標(biāo)志數(shù)組已初始化為為出發(fā)點(diǎn)編號(hào)，標(biāo)志數(shù)組已初始化為0 printf(g.adjlistv.vexdata)； / 訪問出發(fā)點(diǎn)訪問出發(fā)點(diǎn) visitedv= 1； / 做標(biāo)志做標(biāo)志 p=g.adjlistv.firstarc； / 找鄰接點(diǎn)找鄰接點(diǎn) while (pNULL) w = padjvex； if (visitedw=0) df_traver (g，w)；/ 遞歸調(diào)用遞歸調(diào)用 p=pnextarc； / 找下一個(gè)鄰接點(diǎn)找下一個(gè)鄰接點(diǎn) /dfs 43 從圖中的某個(gè)頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次

28、序依次訪問它們的鄰接點(diǎn)。7.3.2連通圖的廣度優(yōu)先搜索連通圖的廣度優(yōu)先搜索(Breadth-First Search) 一層一層二層二層三層三層訪問頂點(diǎn)的次序： V3V2V1V6V4V5V9V8V736798412544顯然，先被訪問的頂點(diǎn)，其鄰接點(diǎn)也先被訪問. 實(shí)現(xiàn)時(shí)需要設(shè)置一個(gè)隊(duì)列隊(duì)列，用于記住訪問頂點(diǎn)的次序：367984125算法：算法： 1. 將初始頂點(diǎn)號(hào)入隊(duì)；將初始頂點(diǎn)號(hào)入隊(duì)；2. 隊(duì)列不空，則隊(duì)列不空，則 隊(duì)頭頂點(diǎn)號(hào)出隊(duì),訪問訪問； 依次將其鄰接頂點(diǎn)號(hào)入隊(duì)；3.重復(fù)重復(fù)2，直到隊(duì)列空，直到隊(duì)列空，遍歷過程結(jié)束。45鄰接表結(jié)構(gòu)下連通圖的廣義優(yōu)先遍歷算法：鄰接表結(jié)構(gòu)下連通圖的廣義優(yōu)先遍

29、歷算法：void bf_traver (AdjGraph g，int v0) / 隊(duì)列隊(duì)列Q存放已訪問過的頂點(diǎn)編號(hào)，存放已訪問過的頂點(diǎn)編號(hào)，v0為出發(fā)點(diǎn)編號(hào)為出發(fā)點(diǎn)編號(hào) InitQueue(Q)； EnQueue(Q，v0)； while (!Qempty(Q) ) v=OutQueue(Q)； printf(g.adjlistv.vexdata)； visitedv=1； p=g.adjlistv.firstarc； while (p NULL) w=padjvex； / 取鄰接點(diǎn)編號(hào)取鄰接點(diǎn)編號(hào) if (visitedw=0) InQueue(Q，w) ； p = pnextarc ； /

30、bfs 46void traver(gragh g) for(v=0；vn；v+) visitedv=0； for(v=0；vn；v+) if (visitedv=0) df_traver(g, v)； /或或bf_travers(g, v) 從圖中的某個(gè)頂點(diǎn)V0出發(fā)深度（廣度）優(yōu)先深度（廣度）優(yōu)先遍歷，遍歷，之后另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。7.3.3 非連通圖的深度非連通圖的深度( (廣度）優(yōu)先遍歷：廣度）優(yōu)先遍歷：47 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前如何在最節(jié)省

31、經(jīng)費(fèi)的前提下建立提下建立這個(gè)通訊網(wǎng)通訊網(wǎng)？問題：?jiǎn)栴}：48圖G中的邊集合E(G)分成兩個(gè)部分:T(G)與與G中中所有頂點(diǎn)所有頂點(diǎn)構(gòu)成構(gòu)成G的極小連通子圖，的極小連通子圖，即是即是G的一棵的一棵生成樹生成樹。深度優(yōu)先生成樹B(G)：剩余的邊集。T(G)：遍歷過程中經(jīng)過的邊集遍歷過程中經(jīng)過的邊集生成樹生成樹367984125367984125廣度優(yōu)先生成樹49已知一個(gè)帶權(quán)圖，求其生成樹，使得樹中所有邊上的權(quán)值之和最小權(quán)值之和最小。 0 1 3 2 4 5 651536642最常用的算法： 普里姆普里姆(prim)算法算法 卡魯斯卡爾卡魯斯卡爾(kruskal)算法算法5014231534250V-

32、UU1. 普里姆普里姆(prim)算法算法 設(shè)G=(V, E)是連通圖，最小生成樹T的頂點(diǎn)集合為U，邊的集合是TE。首先：首先：U =u0 (u0 V) ， TE = 重復(fù)執(zhí)行下述操作：重復(fù)執(zhí)行下述操作： 在所有u U， v V-U的邊(u，v) E中找一條代價(jià)最小的邊(ui ，v0)并入集合TE，同時(shí)v0并入U(xiǎn)，直到 U = V為止。 51abcdegf195141827168213127例如例如: :aedcbgf148531621所得生成樹權(quán)值和= 14+8+3+5+16+21 = 6752帶權(quán)圖帶權(quán)圖(網(wǎng)網(wǎng))用鄰用鄰接矩陣表示接矩陣表示。struct VertexType adjvex

33、； / U集中的頂點(diǎn) WeightType lowcost; / 邊的權(quán)值 closedgeVNUM； 最小生成樹用一個(gè)結(jié)構(gòu)數(shù)組數(shù)組(closedge)表表示示，數(shù)組下標(biāo)表示圖中的頂點(diǎn)序號(hào)；對(duì)當(dāng)前VU集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：typedef struct VertexType vexsVNUM; WeightType arcsVNUMVNUM;int vexnum, arcnum; NetGraph ；53 0123456 0 1 2 3 4 5 6closedge0123456AdjvexLowcost a b c d e f gabcdegf19514182

34、7168213127aedcbaaa19141814e12ee8168d3dd7213c5 51621gf 19 14 1819 5 7 12 5 3 7 3 8 21 14 12 8 16 21 2718 16 27 0162453G.arcsij:a b c d e f g0 1 2 3 4 5 6G.vexsi:54void MiniSpanTree_P(NetGraph G, VertexType u) /帶權(quán)的連通圖G的存儲(chǔ)結(jié)構(gòu)為鄰接矩陣NetGraph， /用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹 k=LocateVex (G, u); /確定起點(diǎn)u在圖G中的位置 for (j

35、=0; jG.vexnum; j+) / 輔助數(shù)組初始化 if (jk) closedgej. adjvex = u; closedgej. lowcost= G.arcskj ; closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; i+) 55 k = minimum(closedge); / 求出加入生成樹的下一個(gè)頂點(diǎn)(k) printf(closedgek.adjvex, G.vexsk， closedgek.lowcost ); / 輸出生成樹上一條邊 closedgek.lowcost = 0; /第k頂點(diǎn)并入U(xiǎn)集 for(j=0;

36、 jG.vexnum; +j) /修改其它頂點(diǎn)的最小邊 if (G.arcskj closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej. lowcost =G.arcskj; /MiniSpanTree_P56設(shè)設(shè)G=（V， E )是連通圖是連通圖 將邊從小到大排序；將邊從小到大排序； 將將n個(gè)頂點(diǎn)分成個(gè)頂點(diǎn)分成n棵樹；棵樹； 選最小的一條邊（選最小的一條邊（u，v)，滿，滿足足u，v不在同一連通集不在同一連通集 重復(fù)，選夠重復(fù)，選夠n-1條邊停止；條邊停止；（0，2）=1 （1，2）=5（3，5）=2 （2，3）=5（1，4）=3

37、（0，1）=6（2，5）=4 （2，4）=6（0，3）=5 （4，5）=6 0 1 3 2 4 5 651536642 X X二、二、克克魯斯卡爾魯斯卡爾(kruskal)算法算法12025314525123457普里姆算法普里姆算法 克魯斯卡爾算法克魯斯卡爾算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稠密圖稀疏圖稀疏圖算法名算法名適應(yīng)范圍適應(yīng)范圍比較兩種算法58給定有向圖G=(V, E)，G中E上的權(quán)值為W(e)；設(shè)源點(diǎn)的編號(hào)為v0， G的存儲(chǔ)結(jié)構(gòu)為鄰接矩陣鄰接矩陣。 WeightType netNN； V5 V01006030102010550 V1 V2 V3 V4 10 3

38、0 100 5 50 10 20 60 netij=存儲(chǔ)存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu):59Dijkstra算法：算法： 按路徑長(zhǎng)度按路徑長(zhǎng)度遞增遞增的次序產(chǎn)生最短路徑。的次序產(chǎn)生最短路徑。 如源點(diǎn)到其它每一個(gè)頂點(diǎn)都有一條最短路徑： ( v0， ， v1) ( v0， ， v2) ( v0， ， vn) 在上面的路徑中，先求最短的，再求次短的，。首先將網(wǎng)中的所有頂點(diǎn)分成兩個(gè)集合首先將網(wǎng)中的所有頂點(diǎn)分成兩個(gè)集合S和和T：S：凡以v0為源點(diǎn)，已經(jīng)確定了最短路徑的終點(diǎn)并入集合S。S的初始狀態(tài)只包含v0。T：尚未確定最短路徑的頂點(diǎn)的集合。其初始狀態(tài)包含除源點(diǎn)外的所有頂點(diǎn)。60引進(jìn)兩個(gè)輔助數(shù)組來記源點(diǎn)(設(shè)其編號(hào)為v0)到

39、其它頂點(diǎn)的最短路徑長(zhǎng)度路徑長(zhǎng)度和路徑集合路徑集合。 disti：表示v0到頂點(diǎn)vi的最短路徑的長(zhǎng)度。 pathi: 表示以上路徑中所經(jīng)過的頂點(diǎn)集合其初始狀態(tài)為： disti = netv0i ； pathi= v0, i，當(dāng)E ，否則 初始時(shí)S=v0，以后不斷地修改以后不斷地修改S和和disti：設(shè)第一條最短路徑為(v0，vj):則 distj=min disti |viT，此時(shí) S=v0，j61假設(shè)下一條次短路徑的終點(diǎn)是vk，則這條路徑或者是(v0，vk)， 或者是(v0，vj，vk)。所以有必要修改v0號(hào)頂點(diǎn)到除j號(hào)頂點(diǎn)以外其它頂點(diǎn)的距離，即修改disti(iT)disti=minnetv

40、0i，distj+netjijS,iT重復(fù)執(zhí)行下述操作，直到選夠重復(fù)執(zhí)行下述操作，直到選夠n-1條路徑：條路徑：（1）設(shè)下一條所選路徑的終點(diǎn)為vk ，則：distk= mindistiiT，將k加入到S中。（2）修改disti iTdisti=mindisti，distk+netkikS，iT 62 v1 v2 v3 v4 v5 入選入選S的點(diǎn)的點(diǎn)disti 10 30 100pathi (v0,v2) (v0,v4) (v0,v5) 10 30 100 5 50 10 20 60 netij=從從v0出發(fā)出發(fā) 10(v0,v2)disti / 60 30 100 pathi (v0,v2,v

41、3)disti / 50 / 90pathi (v0,v4,v3) (v0,v4,v5) disti / / / 60pathi (v0,v4,v3,v5) 30(v0,v4) 50(v0,v4,v3) 60(v0,v4,v3,v5)v2v4v3v5 V5 V01006030102010550 V1 V2 V3 V463存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：Adjmatrix netnn； 存儲(chǔ)有向網(wǎng)的鄰接矩陣。WeightType distn； disti: 存儲(chǔ)v0到vi的路徑長(zhǎng)度。int insetn；若vi在頂點(diǎn)集合S中，則inseti=1，否則inseti=0；初始時(shí)：insetv0=1，其它為0。i

42、nt pathnn；二維數(shù)組二維數(shù)組； pathi是一維數(shù)組，存儲(chǔ)源點(diǎn)v0到各頂點(diǎn)vi的最短路徑，若若pathik=1，表示，表示vk在該路徑中。在該路徑中。0 0 0 0 0 00 0 0 0 0 01 0 1 0 0 01 0 0 1 1 01 0 0 0 1 01 0 0 1 1 10 1 2 3 4 5p0p1p2p3p4p564void shortpath(Adjmatrix net， int v0， WeightType &distn，int &pathnn) for (i=0；in；i+) / dist、inset、path初始化初始化 disti= netv0i

43、； inseti=0； /所有頂點(diǎn)都不在所有頂點(diǎn)都不在S中中 pathi0.n-1=0；/所有所有pathi為空路徑為空路徑 if(distiMAXINT) pathiv0=1；pathii=1； /如果如果disti ,讓讓pathi=v0，vi ； / 初始化完成初始化完成 insetv0=1；/初始化集合初始化集合S=v065for(k=0；kn；k+) / 構(gòu)造至多構(gòu)造至多n-1條路徑條路徑 min= MAXINT； j=v0； / 初始化一個(gè)最短路徑長(zhǎng)初始化一個(gè)最短路徑長(zhǎng) for(i=0；in；i+) /找入選點(diǎn)及找入選點(diǎn)及min值值 if(inseti=0 & distim

44、in) j=i； min=distj ；/min=mindisti, iT if(jv0) insetj=1；/ S=S+j for(i=0；in；i+) / 修改修改disti, iT if( inseti=0 & (distj+netjidisti) disti=distj + netji； pathi0.n-1= pathj0.n-1； pathii=1； / pathi=pathj+i / end_for k /shortpath T(n)= O(n2)66一個(gè)解決辦法是：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行dijkstra算法n次。 T(n) = O(n3)另一算法：另一算法：由F

45、loyd提出, T(n) = O(n3)，但形式較簡(jiǎn)單形式較簡(jiǎn)單存儲(chǔ)結(jié)構(gòu)仍使用鄰接矩陣存儲(chǔ)結(jié)構(gòu)仍使用鄰接矩陣net。為了描述簡(jiǎn)單，設(shè)頂點(diǎn)的編號(hào)從1n；鄰接矩陣數(shù)組的下標(biāo)也從1n。67若存在，則存在路徑vi,vj / 路徑中不含其它頂點(diǎn)若,存在，則存在路徑vi,v1,vj / 路徑中所含頂點(diǎn)序號(hào)不大于1若vi,v2, v2,vj存在， 則存在一條路徑vi, , v2, vj / 路徑中所含頂點(diǎn)序號(hào)不大于2 依次類推，則 vi 至 vj 的最短路徑應(yīng)是上述這些路徑中，路徑長(zhǎng)度最小者。68設(shè)二維數(shù)組設(shè)二維數(shù)組A來存儲(chǔ)任一對(duì)頂點(diǎn)的最短路徑長(zhǎng)度，來存儲(chǔ)任一對(duì)頂點(diǎn)的最短路徑長(zhǎng)度，開始時(shí)，開始時(shí)，Aij的值

46、取的值取netij的值的值。 將A記為A(0) 。要進(jìn)行要進(jìn)行n次試探次試探。(1)對(duì)每一條路徑，先考慮讓路徑經(jīng)過頂點(diǎn)v1，比較路徑和+ 的長(zhǎng)度，取其短者為當(dāng)前求得的最短路徑長(zhǎng)度，記為A(1)。稱為中間點(diǎn)序號(hào)不大于中間點(diǎn)序號(hào)不大于1的最短路徑(2)在A(1)的基礎(chǔ)上讓路徑經(jīng)過頂點(diǎn)v2，可求得A(2) 稱為中間點(diǎn)序號(hào)不大于中間點(diǎn)序號(hào)不大于2的最短路徑。 (n)在A(n-1)的基礎(chǔ)上讓路徑經(jīng)過頂點(diǎn)vn，可求得A(n) 69序列序列A(k)ij（k=1，2，n)的求法：的求法：假設(shè)已知A(k-1)ij，分兩種情況： 頂點(diǎn)vi到頂點(diǎn)vj的最短路徑不通過中間點(diǎn)中間點(diǎn)vk， 則: A(k)ij= A(k-

47、1)ij (2) 頂點(diǎn)vi到頂點(diǎn)vj的最短路徑經(jīng)過中間點(diǎn)中間點(diǎn)vk ， 則: 該路徑由 + 組成，此時(shí)應(yīng)修改A(k)ij為 A(k-1)ik + A(k-1)kj A(0)ij = netij A(k)ij=minA(k-1)ij，A(k-1)ik+A(k-1)kj其中：A(i)ij= A(i-1)ij；A(j)ij=A(j-1)ij； A(k)ii = A(0)ii（k=1，2，n)70A(0) = 1 4 9 2 3 5 8 6 A(3)= 1 10 3 12 9 2 3 4 6 9 10 6 A(2)= 1 10 3 9 2 3 4 6 6 A(4)= 1 9 3 11 8 2 3 4

48、6 9 10 6 A(1)= 1 4 9 2 3 4 7 6 31954862例： v3 v4 v1 v271void floyd(AdjMatrix net，PathMatrix &path ，DistancMatrix &a)/i和和j之間的最短路徑為之間的最短路徑為pij，最短路徑長(zhǎng)為，最短路徑長(zhǎng)為aij；若；若/pijk為為TRUE，則，則k是從是從i到到j(luò)當(dāng)前求得最短路徑上的頂點(diǎn)當(dāng)前求得最短路徑上的頂點(diǎn)for(i=0；in；i+) for(j=0；jn；j+) aij= netij； for(k=0；kn；k+)pijk=FALSE； if (aijMAXINT) p

49、athiji=TRUE；pathjkk=TRUE； 72for (k=0；kn；k+) for (i=0；in；i+) for (j=0；jn；j+) if (aik+akjaij) aij=aik+akj； for (t=0；tn；t+) / pathi,j=pathi,k+pathk,jpjkt=pjit | pjkt； / floyd 73有向無環(huán)圖有向無環(huán)圖(directed acycline graph)：以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。a1a10a4a7a8a2a5a3a11a6a974一一. .拓?fù)渑判騿栴}的提出拓?fù)渑判騿栴}的提出 在現(xiàn)實(shí)世界中

50、,一項(xiàng)大的工程通常有若干個(gè)子工程構(gòu)成，這些子工程和主工程的關(guān)系可以用有向圖來描述。子工程稱為活動(dòng)(Activity)，活動(dòng)之間經(jīng)常存在先后的次序關(guān)系。a1a10a4a7a8a2a5a3a11a6a975 在一個(gè)有向圖中如果用頂點(diǎn)表示活動(dòng)頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系弧表示活動(dòng)間優(yōu)先關(guān)系，該圖稱為用頂點(diǎn)表示活動(dòng)的網(wǎng) (Activity On Vertex Network) ， 簡(jiǎn)稱AOV_網(wǎng)。網(wǎng)。i是j的前驅(qū)前驅(qū)，j是i的后繼后繼； i是k的直接前直接前驅(qū)驅(qū)，k是i的直接后繼直接后繼。 i k j 二二. AOV_網(wǎng)網(wǎng)76三三. 拓?fù)湫蛄械亩x拓?fù)湫蛄械亩x 設(shè)圖G是一個(gè)具有n個(gè)頂點(diǎn)的有向

51、圖，包含圖G的所有n個(gè)頂點(diǎn)的一個(gè)序列：Vi1,Vi2,Vin，當(dāng)滿足下面條件時(shí)該序列稱為G的一個(gè)拓?fù)湫蛄型負(fù)湫蛄校寒?dāng)在圖G中，從頂點(diǎn)Vi到頂點(diǎn)Vj有一條路徑時(shí)，在序列中Vi必須排在Vj的前面。構(gòu)造拓?fù)湫蛄械倪^程稱為構(gòu)造拓?fù)湫蛄械倪^程稱為拓?fù)渑判蛲負(fù)渑判颉?7例如：在如下的AOV_網(wǎng)中：序列：v1v3v2v4v5v6v7 是一個(gè)拓?fù)湫蛄校恍蛄校簐2v1v3v5v4v7v6 也是一個(gè)拓?fù)湫蛄?；v3v1v2v4v5v6v7 程序設(shè)計(jì)程序設(shè)計(jì) 匯編匯編語言語言 信息技術(shù)信息技術(shù) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 編譯原理編譯原理 離散數(shù)學(xué)離散數(shù)學(xué) 操作系統(tǒng)操作系統(tǒng)78例如：對(duì)于下列有向圖BDAC可求得可求得拓?fù)溆行蛐?/p>

52、列拓?fù)溆行蛐蛄校?A B C D 或或 A C B D對(duì)于下列有向圖：對(duì)于下列有向圖：BDAC不能求得它的拓?fù)洳荒芮蟮盟耐負(fù)溆行蛐蛄小Ｓ行蛐蛄?。存在一個(gè)回路存在一個(gè)回路 四四. .拓?fù)湫蛄械奶攸c(diǎn)拓?fù)湫蛄械奶攸c(diǎn)1) 一個(gè)有向圖的拓?fù)湫蛄幸话悴晃ㄒ?。一個(gè)有向圖的拓?fù)湫蛄幸话悴晃ㄒ弧?) 有向無環(huán)圖一定存在拓?fù)湫蛄?。有向無環(huán)圖一定存在拓?fù)湫蛄小?9五五. 拓?fù)渑判虻乃惴枋鐾負(fù)渑判虻乃惴枋鋈绻旤c(diǎn)沒有全部輸出，且當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)，則說明有向圖中存在環(huán)(1) 在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出；(2) 從圖中刪除該頂點(diǎn)以及以該頂點(diǎn)為弧尾的所有?。?重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出。8

53、0V1V2V3V4V5V6V2V3V4V5V6V2V3V4V5例(a)輸出 V1(b) 輸出V6(c)輸出V4V2V3V5(d) 輸出V3V2V5 (e) 輸出V2或V5拓?fù)湫蛄校和負(fù)湫蛄校篤1 V6 V4 V3 V2 V5V1 V6 V4 V3 V5 V2 V6 81鄰接表存儲(chǔ)結(jié)構(gòu)中實(shí)現(xiàn)拓?fù)渑判虻乃惴ㄠ徑颖泶鎯?chǔ)結(jié)構(gòu)中實(shí)現(xiàn)拓?fù)渑判虻乃惴捎每捎眉恿巳攵扔蚣恿巳攵扔?id)的頭結(jié)點(diǎn)的的頭結(jié)點(diǎn)的鄰接表鄰接表來存儲(chǔ)有向圖。來存儲(chǔ)有向圖?；〉淖x入順序如下弧的讀入順序如下(0，1) 、(0，2)、(0，3)、(2，1)、(2，4)、(3，2)、(3，4)、(5，3)、(5，4)用一個(gè)順序棧存放入度為用一

54、個(gè)順序棧存放入度為0的頂點(diǎn)序號(hào)。的頂點(diǎn)序號(hào)。 頂點(diǎn)頂點(diǎn) 入度入度 指針指針 0 V0 0 3 2 1 1 V1 2 2 V2 2 4 1 3 V3 2 4 2 4 V4 3 5 V5 0 4 3 V0V1V4V3V4V5821、邏輯算法：、邏輯算法： InitStack(s)； 將所有入度為零的頂點(diǎn)的棧 ； m = 0； / m記已輸出頂點(diǎn)的個(gè)數(shù)記已輸出頂點(diǎn)的個(gè)數(shù) while (!Empty(s) v= Pop(s)； printf(v)； m=m+1； w = FirstAdjvex(g，v)； while (w存在) 入度(w)=入度(w)-1； if (入度(w)= 0) push(s，

55、w)； w = NextAdjvex(g，v，w) if (mn) return ERROR；/ 該圖有回路該圖有回路 else return OK； 832、鄰接表結(jié)構(gòu)下的算法：、鄰接表結(jié)構(gòu)下的算法：typedef struct arcnode int adjvex； / 鄰接點(diǎn)位置鄰接點(diǎn)位置 struct arcnode *nextarc； /下一個(gè)弧結(jié)點(diǎn)指針下一個(gè)弧結(jié)點(diǎn)指針 ArcNode，*ArcPointer；typedef struct DataType vexdata ； / 頂點(diǎn)類型頂點(diǎn)類型 int id； / 入度入度 ArcPointer firstarc； / 頭指針頭指

56、針 VexNode；typedef struct VexNode adjlistVnum； / 鄰接表鄰接表 int vexnum，arcnum； /有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) AdjGraph84status top_sort(AdjGraph g) InitStack(s)； m = 0； / 初始化順序棧初始化順序棧s for(i=0；ig.vexnum；i+)if(g.adjlisti.id=0) Push(s，i)； while (! Empty(s) v=Pop(s)； printf(g.adjlistv.vexdata)； m=m+1； p= g.adjli

57、stv.firstarc； while(pNULL) w = padjvex ； g.adjlistw.id-； if(g.adjlistw.id =0) Push(s，w)； p = pnextarc； if (mn) return ERROR；else return OK； / top_sort85 頂點(diǎn)頂點(diǎn) 入度入度 指針指針 0 V0 0 3 2 1 1 V1 2 2 V2 2 4 1 3 V3 2 4 2 4 V4 3 5 V5 0 4 3 先先輸出輸出 v5棧棧s 5 0按topsort算法得到的拓?fù)湫蛄袨椋篤5、V0、V3、V2、V1、V4。1201110003 2 41V0V1

58、V4V3V4V586 AOE_網(wǎng)(activity on edge)：在對(duì)工程進(jìn)度進(jìn)行管理時(shí)，往往用頂點(diǎn)表示往往用頂點(diǎn)表示事件事件，弧表示，弧表示活動(dòng)活動(dòng)，弧上的權(quán)表示活動(dòng)持續(xù)的時(shí)間，這種網(wǎng)稱為AOE網(wǎng)。12a1=6a4=1a2=4a3=5a5=1a6=2a9=4a11=4a7=9a10=2a8=7源點(diǎn)源點(diǎn)匯點(diǎn)匯點(diǎn)968753487(1) 完成整項(xiàng)工程至少要花多少時(shí)間？完成整項(xiàng)工程至少要花多少時(shí)間？整個(gè)工程完成的時(shí)間為整個(gè)工程完成的時(shí)間為：從有向圖的：從有向圖的源點(diǎn)源點(diǎn)到到匯點(diǎn)匯點(diǎn)的最長(zhǎng)路徑。的最長(zhǎng)路徑。abcdefghk64521187244源點(diǎn)源點(diǎn)匯點(diǎn)匯點(diǎn)6174(2) 哪些活動(dòng)是影響工程

59、進(jìn)度的關(guān)鍵？哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？關(guān)鍵路徑關(guān)鍵路徑：路徑長(zhǎng)度最長(zhǎng)最長(zhǎng)的路徑。關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)：關(guān)鍵路徑上的所有活動(dòng)。88事件事件Vi的最早發(fā)生時(shí)間的最早發(fā)生時(shí)間：從源點(diǎn)源點(diǎn)到Vi的最長(zhǎng)路徑長(zhǎng)度最長(zhǎng)路徑長(zhǎng)度。ViV1 . . .l(i) - e(i): 完成活動(dòng)完成活動(dòng)ai的的余量余量。jkai 定義定義 當(dāng)當(dāng)e(i)=l(i)時(shí)，活動(dòng)時(shí)，活動(dòng)ai為為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)。定義定義 e(i) 活動(dòng)活動(dòng)ai的的最早最早(early)開始時(shí)間。開始時(shí)間。 l(i) 活動(dòng)活動(dòng)ai的的最遲最遲(late)開始時(shí)間。開始時(shí)間。 也是也是以以Vi為尾的弧為尾的弧所表示的所表示的活動(dòng)活動(dòng)的的最早開始時(shí)間

60、最早開始時(shí)間 其中：ai 89可知Ve(j)是以Vj為弧尾的活動(dòng)ai的最早開始時(shí)間 即: Ve(j)=e(i) weight() ：活動(dòng)ai的持續(xù)時(shí)間。 “事件事件j(頂點(diǎn)頂點(diǎn))” 的的 最早最早發(fā)生時(shí)間發(fā)生時(shí)間 Ve(j)Ve(j) = 從源點(diǎn)到頂點(diǎn)從源點(diǎn)到頂點(diǎn)j的的最長(zhǎng)最長(zhǎng)路徑長(zhǎng)度路徑長(zhǎng)度;“事件事件k(頂點(diǎn)頂點(diǎn))” 的的 最遲最遲發(fā)生時(shí)間發(fā)生時(shí)間 Vl(k) Vl(k) = 從頂點(diǎn)從頂點(diǎn)k到匯點(diǎn)的到匯點(diǎn)的最短最短路徑長(zhǎng)度路徑長(zhǎng)度;jkweight第第i i項(xiàng)活動(dòng)項(xiàng)活動(dòng)aiVe(j)Vl(k)e(i)，l(i) 定義定義 90假設(shè)第 i 條弧為 “活動(dòng)活動(dòng)ai(弧弧)”的 最早開始時(shí)間 e(i) e(i) = Ve(j)；“活動(dòng)活動(dòng)ai(弧弧)”的 最遲開始時(shí)間 l(i) l(i) = Vl(k) weight() ；jkai 事件發(fā)生時(shí)間的計(jì)算公式