圖 電子科大 數(shù)據(jù)結(jié)構(gòu) PowerPoint 演示文稿

1、1數(shù)據(jù)結(jié)構(gòu)與算法主講人：陳安龍主講人：陳安龍電子科技大學(xué)信息與軟件工程學(xué)院電子科技大學(xué)信息與軟件工程學(xué)院2n圖的基本概念圖的基本概念n圖的常用存儲(chǔ)結(jié)構(gòu)圖的常用存儲(chǔ)結(jié)構(gòu) n圖的基本運(yùn)算圖的基本運(yùn)算n圖的基本應(yīng)用圖的基本應(yīng)用第四章第四章 圖圖3道路建設(shè)、輸電線道路建設(shè)、輸電線路鋪設(shè)、煤氣管線路鋪設(shè)、煤氣管線鋪設(shè)等。鋪設(shè)等。4問(wèn)題問(wèn)題1: 造價(jià)和管線長(zhǎng)度成正造價(jià)和管線長(zhǎng)度成正比比,如何表示管線長(zhǎng)度如何表示管線長(zhǎng)度?房屋房屋1房屋房屋2房屋房屋3商場(chǎng)商場(chǎng)12825211432305房屋房屋1房屋房屋2房屋房屋 3商場(chǎng)商場(chǎng)1252114問(wèn)題問(wèn)題2: 如何以最少連線連通如何以最少連線連通所有房屋和商店所有

2、房屋和商店?問(wèn)題問(wèn)題3: 如何連通所有房屋和如何連通所有房屋和商店且造價(jià)最低商店且造價(jià)最低?如何表示？如何表示？如何存儲(chǔ)？如何存儲(chǔ)？如何快速計(jì)算？如何快速計(jì)算？6圖的基本概念圖的基本概念u無(wú)向圖（無(wú)向圖（Undigraph） G=(V, E) 其中，其中，V同有向圖的頂點(diǎn)，同有向圖的頂點(diǎn)，E為頂點(diǎn)之間的邊集合為頂點(diǎn)之間的邊集合G1=（V，E） V=v1, v2, v3, v4, v5E=(v1, v2), (v1, v4), (v2, v3), (v3, v4), (v2,v5), (v3,v5)其中，其中，(x, y)表示表示x與與y之間的一條連線，稱為邊（之間的一條連線，稱為邊（edge）

3、G1 7圖的基本概念圖的基本概念u有向圖（有向圖（Digragh） G=（V，E） 其中，其中，V為圖的頂點(diǎn)集合為圖的頂點(diǎn)集合 E為頂點(diǎn)之間的弧集合為頂點(diǎn)之間的弧集合G2=（V，E） V=v1, v2, v3, v4E=, , , 其中其中表示從表示從x到到y(tǒng)的一條?。ǖ囊粭l?。╝rc），），E為弧集合，為弧集合，x為弧為弧尾（尾（tail），），y為弧頭（為弧頭（head)G28圖的基本概念圖的基本概念設(shè)設(shè)n為頂點(diǎn)數(shù)，為頂點(diǎn)數(shù)，e為邊或弧的條數(shù)為邊或弧的條數(shù) 對(duì)對(duì)無(wú)向圖無(wú)向圖有：有：0=e=n(n-1)/2 有向圖有向圖有：有：0=e=n(n-1)n(n-1)條邊條邊。n(n-1)/29圖的

4、基本概念圖的基本概念2. 完全圖完全圖 邊達(dá)到最大的圖邊達(dá)到最大的圖 無(wú)向完全圖：無(wú)向完全圖：邊數(shù)為邊數(shù)為n(n-1)/2的無(wú)向圖的無(wú)向圖 有向完全圖：有向完全圖：弧數(shù)為弧數(shù)為n(n-1)的有向圖的有向圖權(quán)：權(quán)：與圖的邊或弧相關(guān)的數(shù)與圖的邊或弧相關(guān)的數(shù)網(wǎng)：網(wǎng)：邊或弧上帶有權(quán)值的圖邊或弧上帶有權(quán)值的圖例例213213有向完全圖無(wú)向完全圖103. 頂點(diǎn)的度頂點(diǎn)的度 TD（V） 無(wú)向圖：無(wú)向圖：為依附于頂點(diǎn)為依附于頂點(diǎn)V的邊數(shù)的邊數(shù) 有向圖：有向圖：等于以頂點(diǎn)等于以頂點(diǎn)V為弧頭的弧數(shù)（稱為為弧頭的弧數(shù)（稱為V的的 入度，記入度，記 為為ID（V）與以頂點(diǎn)）與以頂點(diǎn)V為弧尾的弧數(shù)（稱為為弧尾的弧數(shù)（稱

5、為V 的出度，記為的出度，記為OD（V）之和。即：）之和。即： TD（V）=ID（V）+OD（V） n e= 1/2（TD(vTD(vi i) )） i=1i=1 n n e= ID(vID(vi i)=)=OD(vOD(vi i) ) i=1 i=1i=1 i=1114. 路徑路徑 無(wú)向圖：無(wú)向圖：頂點(diǎn)頂點(diǎn)v到到v的路徑是一個(gè)頂點(diǎn)序列（的路徑是一個(gè)頂點(diǎn)序列（ v=vi0, vi1, , vim=v ） 其中，（其中，（vij-1,vij ）E, 1=j=m 有向圖：有向圖： 頂點(diǎn)頂點(diǎn)v 到到v的路徑是有向的頂點(diǎn)序列（的路徑是有向的頂點(diǎn)序列（v=vi0, vi1, , vim=v） 其中，其中

6、，A, 1=j=m幾個(gè)概念：幾個(gè)概念：路徑長(zhǎng)度：路徑長(zhǎng)度：路徑上邊或弧的數(shù)目路徑上邊或弧的數(shù)目回路或環(huán)：回路或環(huán)：首尾頂點(diǎn)相同的路徑，稱為回路或環(huán)。即：首尾頂點(diǎn)相同的路徑，稱為回路或環(huán)。即： （v=vi0, vi1, , vim=v）簡(jiǎn)單路徑：簡(jiǎn)單路徑：路徑中不含相同頂點(diǎn)的路徑路徑中不含相同頂點(diǎn)的路徑簡(jiǎn)單回路：簡(jiǎn)單回路：除首尾頂點(diǎn)外，路徑中不含相同頂點(diǎn)的回路除首尾頂點(diǎn)外，路徑中不含相同頂點(diǎn)的回路125. 連通連通頂點(diǎn)連通：頂點(diǎn)連通：若頂點(diǎn)若頂點(diǎn)v到頂點(diǎn)到頂點(diǎn)v有路徑，則稱頂點(diǎn)有路徑，則稱頂點(diǎn)v與與v是連通的是連通的 連連 通通 圖圖 ：包括無(wú)向連通圖和有向連通圖包括無(wú)向連通圖和有向連通圖 無(wú)向

7、圖無(wú)向圖：若圖中任意兩個(gè)頂點(diǎn)若圖中任意兩個(gè)頂點(diǎn)vi,vj都是連通的，則稱該圖都是連通的，則稱該圖 是連通圖是連通圖(vivj) 有向圖：有向圖：若圖中任意兩個(gè)頂點(diǎn)若圖中任意兩個(gè)頂點(diǎn)vi,vj，都存在從，都存在從vi到到vj和從和從 vj到到vi的路徑，則稱該有向圖為強(qiáng)連通圖的路徑，則稱該有向圖為強(qiáng)連通圖(vivj) 連通分量：連通分量： 無(wú)向圖：無(wú)向圖：無(wú)向圖中極大連通子圖，稱為連通分量無(wú)向圖中極大連通子圖，稱為連通分量 有向圖：有向圖：有向圖中極大強(qiáng)連通子圖，稱為強(qiáng)連通分量有向圖中極大強(qiáng)連通子圖，稱為強(qiáng)連通分量13G114例例213213有向完全圖無(wú)向完全圖356245136圖與子圖2451

8、36G1頂點(diǎn)2入度：1 出度：3頂點(diǎn)4入度：1 出度：0157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：415例例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，116連通圖例例245136強(qiáng)連通圖356例例非連通圖例例24513617 北京石家莊鄭州武漢西安長(zhǎng)沙成都廣州圖4.1 中國(guó)鐵路交通圖的一部分 子圖子圖是圖的一部分，它本身也是一個(gè)圖。如果有圖G=(

9、V，E)和G=(V,E)，且V是V的子集，E是E的子集，則稱G是G的子圖子圖。圖4-1實(shí)際上是中國(guó)鐵路交通圖的一個(gè)子圖。18 鄰接頂點(diǎn)鄰接頂點(diǎn) 在無(wú)向圖中，若兩個(gè)頂點(diǎn)之間有邊連接，則這在無(wú)向圖中，若兩個(gè)頂點(diǎn)之間有邊連接，則這兩個(gè)頂點(diǎn)互為鄰接頂點(diǎn)兩個(gè)頂點(diǎn)互為鄰接頂點(diǎn) BA圖4.6 頂點(diǎn)B與頂點(diǎn)A鄰接，但頂點(diǎn)A不與頂點(diǎn)B鄰接19圖的應(yīng)用圖的應(yīng)用 圖能表示數(shù)據(jù)元素之間多對(duì)多的關(guān)系，表示能力很強(qiáng)，所圖能表示數(shù)據(jù)元素之間多對(duì)多的關(guān)系，表示能力很強(qiáng)，所以圖的應(yīng)用很廣泛，用于網(wǎng)絡(luò)的分析、分子結(jié)構(gòu)的研究、航線以圖的應(yīng)用很廣泛，用于網(wǎng)絡(luò)的分析、分子結(jié)構(gòu)的研究、航線的描述。的描述。街 道 1街 道 3街 道 2大

10、 街 2大 街 1單 向單 向單 向單 向( a )街 道 地 圖165432123456( b )有 向 圖圖 4.7 街 道 以 及 其 相 應(yīng) 的 有 向 圖20圖有圖有數(shù)組數(shù)組、鄰接表鄰接表、鄰接多重表鄰接多重表和和十字鏈表十字鏈表等表示方法等表示方法一、數(shù)組表示法（鄰接矩陣）一、數(shù)組表示法（鄰接矩陣）設(shè)圖設(shè)圖G=（V，E）有）有n個(gè)頂點(diǎn)，則個(gè)頂點(diǎn)，則G的鄰接矩陣定義為的鄰接矩陣定義為n階方陣階方陣A。其中：其中：ijijijij1 (v ,v )v ,vG , 0 (v ,v )v ,v A i j若或是圖的邊若或不是圖的邊acbdacbde圖4.8 有向圖G1和無(wú)向圖G2120 1

11、 0 1 00 1 1 01 0 1 0 10 0 0 1 0 1 0 1 10 0 0 01 0 1 0 01 0 0 00 1 1 0 0AA例如：例如：G1、G2的鄰接矩陣的鄰接矩陣21 TD(Vi)=OD(Vi)+ID(Vi) n n = Ai,j+Ai,j+Aj,iAj,i j j= =1 j=11 j=1 n n TD(Vi)=Ai,j=Ai,j=Aj,iAj,i j j=1 =1 j j=1=1 22如果如果G是帶權(quán)的圖，是帶權(quán)的圖，wij是邊（是邊（vi,vj）或）或的權(quán)，則其關(guān)系的權(quán)，則其關(guān)系矩陣定義為：矩陣定義為： ijijijijv ,vv ,vG(ij) , v ,vv

12、 ,vG(ij) 0 ij ijWA i j 若（）或是圖的邊若（）或不是圖的邊所有對(duì)角線元素V1V25V34V63V51V45569780 5 7 0 4 8 0 9 5 0 6 5 0 3 1 0圖4.9網(wǎng)及其鄰接矩陣（a) 網(wǎng)(b) 鄰接矩陣23二、鄰接表（二、鄰接表（adjacency list）1. 無(wú)向圖鄰接表無(wú)向圖鄰接表typedef struct arcnode int adjvex; /鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置 struct node *next; /鏈域，指示下一條邊或弧 int weight; /該弧信息 arcnode;typedef struct

13、 Vnode int vexdata; /存放頂點(diǎn)信息 struct node *firstarc; /指示第一個(gè)鄰接點(diǎn)vnode,adjlist;每個(gè)鏈表附設(shè)一個(gè)每個(gè)鏈表附設(shè)一個(gè)頭結(jié)點(diǎn)頭結(jié)點(diǎn)，頭結(jié)點(diǎn)結(jié)構(gòu)為：，頭結(jié)點(diǎn)結(jié)構(gòu)為：vexdatafirstarc其中：其中：vexdata存放頂點(diǎn)信息（姓名、編號(hào)等）；存放頂點(diǎn)信息（姓名、編號(hào)等）； fristarc指向鏈表的第一個(gè)結(jié)點(diǎn)。指向鏈表的第一個(gè)結(jié)點(diǎn)。adjvexnextarc無(wú)權(quán)圖無(wú)權(quán)圖adjvexnextarcweight有權(quán)圖有權(quán)圖24二、鄰接表（二、鄰接表（adjacency list）1234525341543533412212G2 1

14、. 無(wú)向圖鄰接表無(wú)向圖鄰接表252. 有向圖鄰接表有向圖鄰接表與無(wú)向圖的鄰接表結(jié)構(gòu)一樣。只是在與無(wú)向圖的鄰接表結(jié)構(gòu)一樣。只是在第第i條鏈表?xiàng)l鏈表上的結(jié)點(diǎn)是以上的結(jié)點(diǎn)是以Vi為為弧尾弧尾的各個(gè)的各個(gè)弧頭頂點(diǎn)弧頭頂點(diǎn)123423414312特點(diǎn)：特點(diǎn)：1. n個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e條弧的有向圖，需條弧的有向圖，需n個(gè)表頭結(jié)點(diǎn)，個(gè)表頭結(jié)點(diǎn)，e 個(gè)表結(jié)點(diǎn)個(gè)表結(jié)點(diǎn) 2. 第第i條鏈表上的結(jié)點(diǎn)數(shù)，為條鏈表上的結(jié)點(diǎn)數(shù)，為Vi的出度的出度 （求頂點(diǎn)的出度易，求入度難）（求頂點(diǎn)的出度易，求入度難）如圖如圖G1的鄰接表為：的鄰接表為：G1263. 有向圖逆鄰接表有向圖逆鄰接表11234234114327三、十字鏈表（

15、三、十字鏈表（orthogonal list）typedef struct edge int tailvertex, headvertex; /弧尾、弧頭在表頭數(shù)組中位置 struct arcnode *hlink；/指向弧頭相同的下一條弧 struct arcnode *tlink; /指向弧尾相同的下一條弧 char * info； Edge;typedef struct vertex int data; /存與頂點(diǎn)有關(guān)信息 struct arcnode *firstin；/指向以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn) struct arcnode *firstout; /指向以該頂點(diǎn)為弧尾的第一個(gè)弧

16、結(jié)點(diǎn)Node;頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)datafirstinfirstout弧結(jié)點(diǎn)弧結(jié)點(diǎn)tailvex headvexhlinktlinkinfotypedef struct Node *Graph; /圖的定義282. 整體結(jié)構(gòu)整體結(jié)構(gòu)通過(guò)通過(guò)hlink將將弧頭相同弧頭相同的弧連在一個(gè)鏈表上；的弧連在一個(gè)鏈表上； 通過(guò)通過(guò)tlink將將弧尾相同弧尾相同的弧連在一個(gè)鏈表上的弧連在一個(gè)鏈表上 而而hlink鏈和鏈和tlink鏈的頭結(jié)點(diǎn)就是鏈的頭結(jié)點(diǎn)就是頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)3. 例例 G1的十字鏈表為：的十字鏈表為：e34e41e13e12123412134134G129例例bdacab cd1234 1 3

17、 1 2 3 4 3 1 4 3 4 2 4 1304. 特點(diǎn)：特點(diǎn)： 頂點(diǎn)結(jié)點(diǎn)數(shù)頂點(diǎn)結(jié)點(diǎn)數(shù)= =頂點(diǎn)數(shù)頂點(diǎn)數(shù) 弧結(jié)點(diǎn)數(shù)弧結(jié)點(diǎn)數(shù)= =弧的條數(shù)弧的條數(shù) 求入度求入度：從頂點(diǎn)：從頂點(diǎn)ViVi的的firstinfirstin出發(fā)，沿著弧結(jié)點(diǎn)中的出發(fā)，沿著弧結(jié)點(diǎn)中的hlinkhlink所所經(jīng)過(guò)的弧結(jié)點(diǎn)數(shù)。經(jīng)過(guò)的弧結(jié)點(diǎn)數(shù)。 求出度求出度：從頂點(diǎn)：從頂點(diǎn)ViVi的的firstoutfirstout出發(fā)，沿著弧結(jié)點(diǎn)中的出發(fā)，沿著弧結(jié)點(diǎn)中的tlinktlink所經(jīng)過(guò)的弧結(jié)點(diǎn)數(shù)。所經(jīng)過(guò)的弧結(jié)點(diǎn)數(shù)。31圖的鄰接多重表表示法圖的鄰接多重表表示法頂點(diǎn)結(jié)點(diǎn)：typedef struct vertex int data

18、; /存與頂點(diǎn)有關(guān)的信息 struct edge *firstedge; /指向第一條依附于該頂點(diǎn)的邊Node;data firstedge邊結(jié)點(diǎn)：typedef struct edge int mark; /標(biāo)志域 int ivertex, jvertex; /該邊依附的兩個(gè)頂點(diǎn)在表頭數(shù)組中位置 struct node *ilink, *jlink; /分別指向依附于ivex和jvex的下一條邊Edge;圖的定義：typedef struct Node* Graph;mark ivertex ilink jvertex jlink info 32例aecbd1234acdb5e 1 2 1

19、4 3 4 3 2 3 5 5 233四、鄰接多重表四、鄰接多重表鄰接多重表是鄰接多重表是無(wú)向圖無(wú)向圖的另一種的另一種鏈?zhǔn)芥準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)。圖的每一條邊有一個(gè)邊結(jié)點(diǎn)，邊結(jié)點(diǎn)的結(jié)構(gòu)為：圖的每一條邊有一個(gè)邊結(jié)點(diǎn)，邊結(jié)點(diǎn)的結(jié)構(gòu)為：ivexilinkjvexjlink每一個(gè)頂點(diǎn)有一個(gè)頂點(diǎn)結(jié)點(diǎn)，頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)為：每一個(gè)頂點(diǎn)有一個(gè)頂點(diǎn)結(jié)點(diǎn)，頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)為：datafirstedge其中：其中：ivex 和和jvex為該邊所依附的兩個(gè)頂點(diǎn)。為該邊所依附的兩個(gè)頂點(diǎn)。 ilink指向下一條依附于頂點(diǎn)指向下一條依附于頂點(diǎn)ivex的邊。的邊。 jlink指向下一條依附于頂點(diǎn)指向下一條依附于頂點(diǎn)jvex 的邊。的

20、邊。 data存放頂點(diǎn)的信息。存放頂點(diǎn)的信息。 firstedge指向第一條依附于該頂點(diǎn)的邊結(jié)點(diǎn)。指向第一條依附于該頂點(diǎn)的邊結(jié)點(diǎn)。34四、鄰接多重表四、鄰接多重表如圖如圖G2的鄰接多重表的鄰接多重表:特點(diǎn)：頂點(diǎn)結(jié)點(diǎn)數(shù)為特點(diǎn)：頂點(diǎn)結(jié)點(diǎn)數(shù)為n，邊結(jié)點(diǎn)數(shù)為，邊結(jié)點(diǎn)數(shù)為e； 對(duì)需要得到邊的兩個(gè)頂點(diǎn)的一類(lèi)操作很方便對(duì)需要得到邊的兩個(gè)頂點(diǎn)的一類(lèi)操作很方便 （如刪除一條邊，判一條邊是否已訪問(wèn)）。（如刪除一條邊，判一條邊是否已訪問(wèn)）。G2 2534112325214343535 364.3 圖的遍歷圖的遍歷從圖中某個(gè)頂點(diǎn)出發(fā)，沿路徑使圖中從圖中某個(gè)頂點(diǎn)出發(fā)，沿路徑使圖中每個(gè)頂點(diǎn)每個(gè)頂點(diǎn)被被訪問(wèn)且僅被訪問(wèn)一次訪

21、問(wèn)且僅被訪問(wèn)一次的過(guò)程，稱為的過(guò)程，稱為遍歷圖遍歷圖。 兩種常用遍歷圖的方法兩種常用遍歷圖的方法 深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索37n深度優(yōu)先遍歷(DFS) 方法：從圖的某一頂點(diǎn)Vi出發(fā)，訪問(wèn)此頂點(diǎn)；然后依次從Vi的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和Vi相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V738V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1 V2

22、 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V739V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V3 V6 V7 V540 深度優(yōu)先遍歷遞歸算法開(kāi)始訪問(wèn)V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)wV0W訪問(wèn)過(guò)結(jié)束NYNYDFS開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)DFSVi=Vi+1Vi= =Vexnums結(jié)束NNYYCh6_1.c41V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3

23、6 3 5 4V3 V7 V6 V2 V5 V8 V442V1V2V4V5V3V7V6V8例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍歷：V1V3 V7 V6 V2 V4 V8 V543u廣度優(yōu)先遍歷(BFS)v方法：從圖的某一頂點(diǎn)Vi出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)Vi的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V

24、6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V844V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V845V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V546v 廣度優(yōu)先遍歷算法開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)BFSVi=Vi+1Vi=Vexnums結(jié)束NNYY47開(kāi)始訪問(wèn)V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V下一鄰接點(diǎn)ww訪問(wèn)過(guò)結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪問(wèn)w,置標(biāo)志w入隊(duì)NY4

25、8void traver(TD g,int n) int i; static int visitedM; for(i=1;i=n;i+) visitedi=0; for(i=1;i=n;i+) if(visitedi=0) bfs(g,i,visited); void bfs(TD g,int v,int visited) int quM,f=0,r=0; JD *p; printf(%dn,v); visitedv=1; qu0=v; while(fadjvex; if(visitedv=0) visitedv=1; printf(%dn,v); qu+r=v; p=p-next; 49例1

26、423512341342vexdata 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 350例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 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 5510 1

27、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 252二、最小生成樹(shù)性質(zhì)二、最小生成樹(shù)性質(zhì)MST設(shè)設(shè)N=（V，E）是一個(gè)連通網(wǎng)，）是一個(gè)連通網(wǎng)，U是頂點(diǎn)集是頂點(diǎn)集V的一個(gè)非空子集。的一個(gè)非空子集。若（若（u，v）是一條具有最小權(quán)值的邊，其中）是一條具有最小權(quán)值的邊，其中uU,vV-U,即（即（u，v）=Mincost(x,y)|xU,yV-U則必

28、存在一棵包含邊（則必存在一棵包含邊（u，v）的最小生成樹(shù)。）的最小生成樹(shù)。uv-uuvuv含義：將頂點(diǎn)分為兩個(gè)不相交的集合含義：將頂點(diǎn)分為兩個(gè)不相交的集合U和和V-U，若邊（若邊（u，v）是連接這兩個(gè)頂點(diǎn)集的最小權(quán)值）是連接這兩個(gè)頂點(diǎn)集的最小權(quán)值邊，則邊（邊，則邊（u，v）必然是某最小生成樹(shù)的邊。）必然是某最小生成樹(shù)的邊。 53n普里姆(Prim)最小生成樹(shù)算法算法思想：設(shè)N=(V,E)是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合l初始令U=u0,(u0V), TE=l在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)l將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)l重復(fù)上述操

29、作直至U=V為止，則T=(V,TE)為N的最小生成樹(shù)算法實(shí)現(xiàn)：圖用鄰接矩陣表示54Prim算法步驟算法步驟1. TE=,U=u02. 當(dāng)當(dāng)UV，重復(fù)下列步驟：，重復(fù)下列步驟：(1)選取（選?。╱0,v0)=mincost(u,v)|uU,vV-U，保證不形成回路保證不形成回路(2)TE=TE+（u0,v0), 邊（邊（u0,v0)并入并入TE(3)U=U+V0，頂點(diǎn)頂點(diǎn)V0 并入并入U(xiǎn)初始化：第1步：第2步：第3步：第4步：2第5步：特點(diǎn)特點(diǎn): 以連通為主以連通為主選代價(jià)最小的鄰接邊選代價(jià)最小的鄰接邊55例16543265135664251311631416431421164321425165

30、4321425356 0 0 0 0 0 0 0 6 1 5 max max iclosestilowcosti 0 1 2 3 4 5 iclosestilowcosti 0 1 2 3 4 5U= v0U= v0,v2對(duì)對(duì)i i V-U V-U closesti= j (jclosesti= j (j U)U) (j,i)(j,i)是一條邊，且是是一條邊，且是 i i 到到 U U 中各頂點(diǎn)中各頂點(diǎn)“權(quán)最小邊權(quán)最小邊”LowcostiLowcosti：用來(lái)保存連接：用來(lái)保存連接 i i 到到 U U 中各頂點(diǎn)中各頂點(diǎn)“權(quán)最小邊權(quán)最小邊”的權(quán)。的權(quán)。V-U= v1,V2,V3,V4,V5 V

31、-U= v1, V3,V4,V5 V V2 2V V0 0V V3 3V V5 5V V4 4V V1 UV V2 2V V0 0V V3 3V V5 5V V4 4V V1 U 0 2 0 0 2 2 0 2 0 0 2 2 0 5 0 5 60 5 0 5 6 4 457 0 2 0 5 2 0 0 2 0 5 2 0 0 50 5 0 0 2 2 6 0 6 0 iclosestilowcosti 0 1 2 3 4 5 iclosestilowcosti 0 1 2 3 4 5U= v0,V2,V5U= v0,v2,V3,V5V-U=

32、 v1, V3,V4V-U= v1, V4 V V2 2V V0 0V V3 3V V5 5V V4 4V V1 U 0 2 0 0 2 0 0 2 0 0 2 0 0 0 5 5 0 0 6 0 0 6 0 0V V2 2V V0 0V V3 3V V5 5V V4 4V V1 U58 iclosestilowcosti 0 1 2 3 4 5U= v0,V1,v2,V3,V5V-U=V4 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 6 6 0 0V V2 2V V0 0V V3 3V V5 5V V4

33、4V V1 U59/* 用prim算法從序號(hào)為0的頂點(diǎn)出發(fā)構(gòu)造有vtxnum個(gè)頂點(diǎn)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的網(wǎng)gn的最小生成樹(shù)T，并輸出T的各條邊 */void minispantree_PRIM(int gnmax,int vtxnum) int v,i,j,k; float min; /* 根據(jù)鄰接矩陣的值對(duì)結(jié)構(gòu)數(shù)組進(jìn)行初始化 */ for(v=1;i vtxnum;v+) Closedgev.vex=0; Closedgev.lowcost=gn0v; /* 從序號(hào)為0的頂點(diǎn)出發(fā)生成最小生成樹(shù) */ Closedge0.lowcost=0; Closedge0.vex

34、=0;60 for(i=1;i vtxnum;i+) /* 尋找當(dāng)前最小權(quán)值的邊的頂點(diǎn) */ k=minimum(closedge); printf(“”,closedgek.vex,k); /* 輸出生成樹(shù)的邊 */ closedgek.lowcost=0; /* 頂點(diǎn)k并入U(xiǎn) */ /*新頂點(diǎn)并入U(xiǎn)后，重選最小代價(jià)邊*/ for(v=1;vvtxnum;v+) if(gnkv0) * / int minimum(closedge) int min,h,k; min=; h=1; for(k=1;kvtxnum;k+) if (closedgek.lowcost!=0 & closedgek

35、.lowcost0 V-U closedgek.vex U 而而 k V-U63 例子： V VClosedgeClosedge1 1 2 23 3 4 4 5 5 6 6U UV-UV-UTETEVEXVEXLOWCOSTLOWCOST0 06 61 15 5112,3,4,5,62,3,4,5,60 05 5 5 50 05 5 5 56 6 6 64 4 4 41,31,32,4,5,62,4,5,61,31,30 05 5 5 50 02 26 6 6 60 01,3,61,3,62,4,52,4,5.(3,6).(3,6)0 05 5 5 50 00 06 6 6 60 01,3,6

36、,41,3,6,42,52,5.(6,4).(6,4)0 00 00 00 03 30 01,3,6,4,21,3,6,4,255.(3,2).(3,2)0 00 00 00 00 00 01,3,6,4,2,51,3,6,4,2,5.(2.5).(2.5)64克魯斯卡爾（克魯斯卡爾（Kruskal）最小生成樹(shù)算法）最小生成樹(shù)算法Kruskal 算法是逐步給生成樹(shù)T中添加不和T中的邊構(gòu)成回路的當(dāng)前最小代價(jià)邊。特點(diǎn): 以最小代價(jià)邊主。設(shè)N=（V，E）是個(gè)連通網(wǎng), 算法步驟為：1. 置生成樹(shù)T的初始狀態(tài)為T(mén)=（V，）2. 當(dāng)T中邊數(shù)0) f=arcvistedf; return f;70Void

37、kruscal_arc(Mgraph_L G,algraph gra) edg edgsmaxedgs; int i,j,k; for (i=0;i!=G.vanum;+i) for (j=0;j!=G.vanum;+j) if (G.arcsij.adj !=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; 71int x,y,m,n,buf,edf;for(i=0,i!=gra.arcnum;+i) arcvistedi=0;for(j=0,j!=gra.arcnum;+j) m=10000; for (i=0;

38、i!=G.vanum;+i) if (edgsk.weightm) x=edgsi.pre; y=edgsi.bak; m=edgsi.weight; n=i; buf = find(arcvisted,x) ; edf = find(arcvisted,y) ; dgsn.weight=10000; if (buf !=edf) arcvistedbuf=edf; printf(“(%d,%d) %dn”,x,y,n) 72n拓?fù)渑判蛲負(fù)渑判騿?wèn)題提出：學(xué)生選修課程問(wèn)題頂點(diǎn)表示課程有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無(wú)矛盾、順利地完成學(xué)

39、業(yè)拓?fù)渑判蚨x AOV網(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) 若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼 AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件拓?fù)渑判虻姆椒?在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之 從圖中刪除該頂點(diǎn)和所有以它為尾的弧 重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止73例課程代號(hào) 課程名稱 先修棵C1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C

40、9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言語(yǔ)言的設(shè)計(jì)計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C1274C1C2C3C4C5C6C7C8C9C10C11C12拓?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)的拓?fù)湫蛄胁皇俏ㄒ坏?5C1C2C3C4C5C6C7C8C9C10C11C1276C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）C3C4C5C6C7C8C9C10C11C

41、12拓?fù)湫蛄校篊1-C2（2）77C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3（3）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4（4）78C6C8C10C11C12拓?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（5）C6C8C9C10C11C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7（6）79C6C8C12拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9 -C10-C11（9）

42、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）80n算法實(shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至?？諡橹?。若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤呧徑颖斫Y(jié)點(diǎn)：typedef struct node int

43、 vex; /頂點(diǎn)域 struct node *next; /鏈域JD;表頭結(jié)點(diǎn)：typedef struct tnode int in; /入度域 struct node *link; /鏈域TD;TD gM; /g0不用8132104算法描述例1234560122inlink 5 5 4 3vex next3 2 5 2 40123456Ch6_40.ctop16toptop820122inlink 5 5 4 3vex next3 2 5 2 40123456輸出序列：63210416toptop830122inlink 5 5 4 3vex next3 2 5 2 40123456輸出

44、序列：6321041topp840122inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6321041topp850122inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6321041topp860112inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6321041topp870112inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6321041topp=NULL880112inlink 5 5 4 3vex next2 2 5 2 40123

45、456輸出序列：6 1321041toptop890112inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104topp900102inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104topp4910102inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top920102inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top930002inlink 5 5 4 3vex next2

46、2 5 2 40123456輸出序列：6 132104p4top3940002inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top3950002inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top3960001inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p4top3970001inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 132104p=NULL4top3980001inli

47、nk 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 1 3321044top3990001inlink 5 5 4 3vex next2 2 5 2 40123456輸出序列：6 1 3321044topp1000001inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044topp1010001inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044topp1020000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6

48、1 3321044topp21030000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044topp21040000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3321044top2p=NULL1050000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3 2321044top2p=NULL1060000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3 2321044topp=NULL1070

49、000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3 2 4321044top1080000inlink 5 5 4 3vex next1 2 5 2 40123456輸出序列：6 1 3 2 432104topp1090000inlink 5 5 4 3vex next0 2 5 2 40123456輸出序列：6 1 3 2 432104topp51100000inlink 5 5 4 3vex next0 2 5 2 40123456輸出序列：6 1 3 2 432104topp=NULL51110000inlink 5 5 4 3vex

50、next0 2 5 2 40123456輸出序列：6 1 3 2 4 532104top51120000inlink 5 5 4 3vex next0 2 5 2 40123456輸出序列：6 1 3 2 4 532104topp=NULL113n4.4.3 關(guān)鍵路徑問(wèn)題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開(kāi)始例 設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件事件 V1表示整個(gè)工程開(kāi)始事件V9表示整個(gè)工程結(jié)束問(wèn)題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？ （2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1

51、a5=1a6=2a7=9a8=7a9=4a10=2a11=4114定義 AOE網(wǎng)(Activity On Edge)也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間 路徑長(zhǎng)度路徑上各活動(dòng)持續(xù)時(shí)間之和 關(guān)鍵路徑路徑長(zhǎng)度最長(zhǎng)的路徑叫 Ve(j)表示事件Vj的最早發(fā)生時(shí)間 Vl(j)表示事件Vj的最遲發(fā)生時(shí)間 e(i)表示活動(dòng)ai的最早開(kāi)始時(shí)間 l(i)表示活動(dòng)ai的最遲開(kāi)始時(shí)間 l(i)-e(i)表示完成活動(dòng)ai的時(shí)間余量 關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)叫，即l(i)=e(i)的活動(dòng)115問(wèn)題分析 如何找e(i)=l(i)的關(guān)鍵活動(dòng)？設(shè)活動(dòng)ai用弧表示

52、，其持續(xù)時(shí)間記為：dut()則有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut()jkaiv如何求如何求Ve(j)Ve(j)和和Vl(j)Vl(j)？事件的最早、最遲發(fā)生時(shí)間事件的最早、最遲發(fā)生時(shí)間(1)從Ve(1)=0開(kāi)始向前遞推為頭的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei2 ,),()()(2)從Vl(n)=Ve(n)開(kāi)始向后遞推為尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11 ,),()()(116求關(guān)鍵路徑步驟 求Ve(i) 求Vl(j) 求e(i) 求l(i) 計(jì)算l(i)-e(i)987645321a2=4a3=

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

54、表 計(jì)算每個(gè)頂點(diǎn)的入度 對(duì)其進(jìn)行拓?fù)渑判騦 排序過(guò)程中求頂點(diǎn)的Veil 將得到的拓?fù)湫蛄羞M(jìn)棧 按逆拓?fù)湫蛄星箜旤c(diǎn)的Vli 計(jì)算每條弧的ei和li,找出ei=li的關(guān)鍵活動(dòng)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4119987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4in firstarcvexnextvexdataweight123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 94120鄰接表（鄰接表

55、（adjacency list）typedef struct arcnode int adjvex; /鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置 struct node *next; /鏈域，指示下一條邊或弧 int weight; /該弧信息 arcnode;typedef struct Vnode int vexdata; /存放頂點(diǎn)信息 int indegree; /頂點(diǎn)的入度 struct node *firstarc; /指示第一個(gè)鄰接點(diǎn)vnode,adjlist;adjvexnextarcweighttypedef struct adjlist verticesmaxnode

56、； /圖的鄰接鏈表 int vexnum,arcnum； /圖的頂點(diǎn)數(shù)目、邊的數(shù)目algraph;vexdatafirstarcindegree121in firstarcvexnextvexdataweight123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 94Typedef struct vextype vexsmaxnode; /*頂點(diǎn)信息頂點(diǎn)信息*/ int vexsnomaxnode; /*頂點(diǎn)在頂點(diǎn)表中的下標(biāo)信息頂點(diǎn)在頂點(diǎn)表中的下標(biāo)信息*/ topo122int criticalpath(algraph *pao

57、e) int i,j,k; int evvexnum,lvvexnum,larcnum,earcnum; acrnode *p; Topo topo; if (topsort(paoe,&topo)=0) return 0; /求拓?fù)渑判蚯笸負(fù)渑判?for (i=0;ivexnum;i+) evi=0; for (k=0;kvexnum;k+) i=topo.vexsnok; p=paoe-verticei.firstarc; while (p!=NULL) j=p-adjvex; if (evi+p-weightevj) evj=evj+p-weight; p=p-nextarc; /下一頁(yè)

58、代碼接這里下一頁(yè)代碼接這里123 for (i=0;ivexnum;i+) lvi=evpaoe-vexnum-l; /*事件事件vi允許最遲出現(xiàn)時(shí)間允許最遲出現(xiàn)時(shí)間lvj*/ for (k=paoe-vexnum;k=0;k-) i=topo.vexsnok; p=paoe-verticesi.firstarc; while (p!=NULL) j=p-adjvex; if (lvj-p-weight)weight; p=p-nextarc; 124k=0;for (i=0;ivexnum;i+) /*求活動(dòng)求活動(dòng)ak最早開(kāi)始時(shí)間最早開(kāi)始時(shí)間e(k)，最遲開(kāi)始時(shí)間，最遲開(kāi)始時(shí)間l(k)*/

59、p=paoe-verticesi.firstarc; while (p!=NULL) j=p-adjvex; ek=evi; lk= lvj-p-weight; if (ek=lk) printf (“n”,i,j); k+; p=p-nextarc; printf(“/n”);return 1;125n4.4.4 最短路徑問(wèn)題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問(wèn)題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中， 各邊上權(quán)值之和最小的一條路徑最短路徑從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑51643208

60、562301371732913長(zhǎng)度最短路徑813192120126n迪杰斯特拉迪杰斯特拉(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)一個(gè)距離值 S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長(zhǎng)度 T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間 頂點(diǎn)的最短路徑長(zhǎng)度依據(jù)：依據(jù)：可以證明可以證明V0到到T中頂點(diǎn)中頂點(diǎn)Vk的最短路徑，或是從的