本章說(shuō)明7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4生成樹(shù)7.5拓?fù)渑判?.6最短路徑

本章小結(jié)數(shù)據(jù)結(jié)構(gòu)返回主目錄本章說(shuō)明數(shù)據(jù)結(jié)構(gòu)返回主目錄學(xué)習(xí)目標(biāo)領(lǐng)會(huì)圖的類(lèi)型定義。熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其選用原則。熟練掌握?qǐng)D的兩種遍歷算法。理解各種圖的應(yīng)用問(wèn)題的算法。本章說(shuō)明學(xué)習(xí)目標(biāo)本章說(shuō)明重點(diǎn)和難點(diǎn)圖的應(yīng)用極為廣泛，而且圖的各種應(yīng)用問(wèn)題的算法都比較經(jīng)典，因此本章重點(diǎn)在于理解各種圖的算法及其應(yīng)用場(chǎng)合。知識(shí)點(diǎn)圖的類(lèi)型定義、圖的存儲(chǔ)表示、圖的深度優(yōu)先搜索遍歷和圖的廣度優(yōu)先搜索遍歷、無(wú)向網(wǎng)的最小生成樹(shù)、最短路徑、拓?fù)渑判?、關(guān)鍵路徑本章說(shuō)明重點(diǎn)和難點(diǎn)本章說(shuō)明7.1圖的定義和術(shù)語(yǔ)

圖(Graph)——圖G是由兩個(gè)集合V和VR組成的，記為G=(V,VR)其中：V是頂點(diǎn)的有窮非空有限集VR是兩個(gè)頂點(diǎn)之間關(guān)系的有限集合，即邊集合，邊是頂點(diǎn)的無(wú)序?qū)蛴行驅(qū)?/p>

有向圖——有向圖G是由兩個(gè)集合V和VR組成的其中：V是頂點(diǎn)的有窮非空有限集VR是有向邊（也稱(chēng)?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記?lt;v,w>，v,w是頂點(diǎn)，v為弧尾，w為弧頭7.1圖的定義和術(shù)語(yǔ)圖(Graph)——圖G是由兩個(gè)集7.1圖的定義和術(shù)語(yǔ)例如:G1=(V1,VR1)其中V1={1,2,3,4}VR1={<1,2>,<1,3>,<3,4>,<4,1>}有向圖G124137.1圖的定義和術(shù)語(yǔ)例如:G1=(V1,VR1)其7.1圖的定義和術(shù)語(yǔ)無(wú)向圖——由頂點(diǎn)集和邊集構(gòu)成的圖。若<v,w>VR必有<w,v>VR,則稱(chēng)(v,w)為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}無(wú)向圖G2251437.1圖的定義和術(shù)語(yǔ)無(wú)向圖——由頂點(diǎn)集和邊集構(gòu)成的圖。7.1圖的定義和術(shù)語(yǔ)有向完全圖——有n個(gè)頂點(diǎn)，n(n-1)弧的有向圖

無(wú)向完全圖——有n個(gè)頂點(diǎn)，n(n-1)/2條邊的無(wú)向圖例有向完全圖無(wú)向完全圖1232317.1圖的定義和術(shù)語(yǔ)有向完全圖——有n個(gè)頂點(diǎn)，n(n-7.1圖的定義和術(shù)語(yǔ)稀疏圖——有很少條邊和弧(e<nlogn)的圖稠密圖——與稀疏圖相反

權(quán)——與圖的邊或弧相關(guān)的數(shù)網(wǎng)——帶權(quán)的圖有向網(wǎng)——弧帶權(quán)的圖無(wú)向網(wǎng)——邊帶權(quán)的圖ABEC1圖的定義和術(shù)語(yǔ)稀疏圖——有很少條邊和弧(e<nl

子圖——如果圖G(V，E)和圖G′(V′，E′)，滿(mǎn)足：V′

V且E′E，則稱(chēng)G′為G的子圖鄰接點(diǎn)——在無(wú)向圖中一條邊連起來(lái)的兩個(gè)頂點(diǎn)(v,v′)，互稱(chēng)鄰接點(diǎn)，稱(chēng)邊(v,v′)依附于頂點(diǎn)v和v′7.1圖的定義和術(shù)語(yǔ)BBCAEFC子圖——如果圖G(V，E)和圖G′(V′，E′)，滿(mǎn)足：7.1圖的定義和術(shù)語(yǔ)ABECF頂點(diǎn)的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3頂點(diǎn)的度無(wú)向圖中頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù)有向圖中頂點(diǎn)的度為:入度：以該頂點(diǎn)為頭的弧的數(shù)目出度：以該頂點(diǎn)為尾的弧的數(shù)目7.1圖的定義和術(shù)語(yǔ)ABECF頂點(diǎn)的度(TD)=例如:I7.1圖的定義和術(shù)語(yǔ)路徑——路徑是一個(gè)頂點(diǎn)的序列V={Vi,0,Vi,1,……Vi,n}，滿(mǎn)足(Vi,j-1,Vi,j)E或<Vi,j-1,Vi,j>E,(1<jn)路徑上邊的數(shù)目稱(chēng)作“路徑長(zhǎng)度”回路（環(huán)）——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑簡(jiǎn)單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑簡(jiǎn)單回路——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路7.1圖的定義和術(shù)語(yǔ)路徑——路徑是一個(gè)頂點(diǎn)的序列V={7.1圖的定義和術(shù)語(yǔ)連通——從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說(shuō)V和W是連通的連通圖——圖中任意個(gè)頂點(diǎn)都是連通的例G1245136路徑：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例連通圖2451367.1圖的定義和術(shù)語(yǔ)連通——從頂點(diǎn)V到頂點(diǎn)W有一條路徑，連通分量——指的是無(wú)向圖中的極大連通子圖強(qiáng)連通圖——有向圖中，如果對(duì)每一對(duì)Vi,VjV,Vi

Vj,從Vi到Vj

和從Vj到Vi都存在路徑強(qiáng)連通分量——指的是有向圖中的極大強(qiáng)連通子圖7.1圖的定義和術(shù)語(yǔ)強(qiáng)連通圖356例例245136非連通圖連通分量——指的是無(wú)向圖中的極大連通子圖7.1圖的定義和7.1圖的定義和術(shù)語(yǔ)生成樹(shù)——是連通圖的一個(gè)極小連通子圖，它含有圖的全部頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的n-1條邊生成森林——對(duì)非連通圖，各個(gè)連通分量的生成樹(shù)的集合ABCDEFCDABEF一個(gè)有向圖及其生成森林7.1圖的定義和術(shù)語(yǔ)生成樹(shù)——是連通圖的一個(gè)極小連通子圖7.2圖的存儲(chǔ)結(jié)構(gòu)圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示無(wú)向圖的鄰接多重表存儲(chǔ)表示7.2圖的存儲(chǔ)結(jié)構(gòu)圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示圖7.2圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示7.2圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣7.2圖的存儲(chǔ)結(jié)構(gòu)

有向圖G1v2v4v1v3無(wú)向圖G2v2v5v1v4v37.2圖的存儲(chǔ)結(jié)構(gòu)有7.2圖的存儲(chǔ)結(jié)構(gòu)特點(diǎn)：無(wú)向圖的鄰接矩陣對(duì)稱(chēng)，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱(chēng)；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中:頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和網(wǎng)的鄰接矩陣可定義為：7.2圖的存儲(chǔ)結(jié)構(gòu)特點(diǎn)：7.2圖的存儲(chǔ)結(jié)構(gòu)

例23753186421457.2圖的存儲(chǔ)結(jié)構(gòu)例237531867.2圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的創(chuàng)建、銷(xiāo)毀、查找頂點(diǎn)v和返回v的值操作。容易判定頂點(diǎn)間有無(wú)邊（?。菀子?jì)算頂點(diǎn)的度（出度、入度）

缺點(diǎn)：所占空間只和頂點(diǎn)個(gè)數(shù)有關(guān)，和邊數(shù)無(wú)關(guān)，在邊數(shù)較少時(shí)，空間浪費(fèi)較大鄰接矩陣的存儲(chǔ)表示#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,AG,AN}GraphKind;

//{有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng)}7.2圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣的優(yōu)缺點(diǎn)鄰接矩陣的存儲(chǔ)表示7.2圖的存儲(chǔ)結(jié)構(gòu)typedefstructArcCell{//鄰接矩陣VRTypeadj;//頂點(diǎn)關(guān)系類(lèi)型InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)向量AdjMatrixarcs;//弧的信息intvexnum,arcnum;//頂點(diǎn)數(shù)和弧數(shù)GraphKindkind;//圖的種類(lèi)}MGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)typedefstructArcC7.2圖的存儲(chǔ)結(jié)構(gòu)建立無(wú)向圖鄰接矩陣的算法

算法中：G.vexs[]，一維，頂點(diǎn)向量.arcs[][]，二維，鄰接矩陣.vexnum，頂點(diǎn)數(shù).arcnum，邊數(shù)7.2圖的存儲(chǔ)結(jié)構(gòu)建立無(wú)向圖鄰接矩陣的算法7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示

鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，為依附每個(gè)頂點(diǎn)的邊（或?。┙⒁粋€(gè)單鏈表頂點(diǎn)結(jié)構(gòu)

adjvexnextarcinfo表結(jié)點(diǎn)datafirstarc頭結(jié)點(diǎn)頂點(diǎn)位置下一條弧相關(guān)信息頂點(diǎn)數(shù)據(jù)第一條弧7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示鄰接表是圖的一V1V2

V3V40123V1V2V3V4V5012347.2圖的存儲(chǔ)結(jié)構(gòu)有向圖G12413無(wú)向圖G22514312

3

0

31

420

431

20

21

V1V2V3V40V1V2V3V4V507.2圖的存儲(chǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示

#defineMAX_VERTEX_NUM20TypedefstructArcNode//表結(jié)點(diǎn){intAdjvex;//與vi鄰接的頂點(diǎn)的下標(biāo)位置structArcNode*nextarc;//與vi鄰接的下一個(gè)頂點(diǎn)InfoType*info;}//ArcNode;TypedefstructVnode//頭結(jié)點(diǎn){VertexTypedata;ArcNode*firstarc;}Vnode,AdjList[MAX_VERTEX_NUM];Typedefstruct//圖{AdjListvertices;intvexnum,arcnum,kind;}ALGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示#define7.2圖的存儲(chǔ)結(jié)構(gòu)鄰接表是頂點(diǎn)的向量結(jié)構(gòu)和邊（弧）的單鏈表結(jié)構(gòu)每個(gè)頂點(diǎn)結(jié)點(diǎn)包括兩個(gè)域，將n個(gè)頂點(diǎn)放在一個(gè)向量中（稱(chēng)為順序存儲(chǔ)的結(jié)點(diǎn)表）；一個(gè)頂點(diǎn)的所有鄰接點(diǎn)鏈接成單鏈表，該頂點(diǎn)在向量中有一個(gè)指針域指向其第一個(gè)鄰接點(diǎn)。鄰接表的優(yōu)缺點(diǎn)空間較?。粺o(wú)向圖容易求各頂點(diǎn)的度；表中結(jié)點(diǎn)個(gè)數(shù)是邊的兩倍；有向圖容易求頂點(diǎn)的出度；不容易求頂點(diǎn)的入度，要遍歷整個(gè)表。為了求頂點(diǎn)的入度，有時(shí)可設(shè)逆鄰接表（指向某頂點(diǎn)的鄰接點(diǎn)鏈接成單鏈表）7.2圖的存儲(chǔ)結(jié)構(gòu)鄰接表是頂點(diǎn)的向量結(jié)構(gòu)和邊（?。┑膯?.2圖的存儲(chǔ)結(jié)構(gòu)建立鄰接表的算法有向圖G12413V1V2V3V43

0

0

2

逆鄰接表第i(下標(biāo)i-1)鏈表的結(jié)點(diǎn)個(gè)數(shù)即為Vi頂點(diǎn)的入度。7.2圖的存儲(chǔ)結(jié)構(gòu)建立鄰接表的算法有向圖G127.2圖的存儲(chǔ)結(jié)構(gòu)有向圖的十字鏈表存儲(chǔ)表示十字鏈表結(jié)點(diǎn)結(jié)構(gòu)tailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)datafirstinfirstout頂點(diǎn)結(jié)點(diǎn)弧尾位置弧頭位置弧尾相同的下一條弧指針弧相關(guān)信息的指針弧頭相同的下一條弧指針指向該頂點(diǎn)第一條入弧指向該頂點(diǎn)第一條出弧7.2圖的存儲(chǔ)結(jié)構(gòu)有向圖的十字鏈表存儲(chǔ)表示十字鏈7.2圖的存儲(chǔ)結(jié)構(gòu)例v2v4v1v302012320323130^v1v2v3v40123^^^^^^^7.2圖的存儲(chǔ)結(jié)構(gòu)例v2v4v1v3020127.2圖的存儲(chǔ)結(jié)構(gòu)有向圖十字鏈表存儲(chǔ)表示#defineMAX_VERTEX_NUM20typedefstructArcBox//弧結(jié)點(diǎn){inttailvex,hesdvex;structArcBox*hlink,*tlink;infoType*info;}ArcBox;TypedefstructVexNode//頂點(diǎn)結(jié)點(diǎn){VertexTypedata;ArcBox*firstin,*firstout;}VexNode;Typedefstruct{//頂點(diǎn)表VexNodexlist[MAX_VERTEX_NUM];//表頭向量intvexnum,arcnum;}OLGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)有向圖十字鏈表存儲(chǔ)表示#define7.2圖的存儲(chǔ)結(jié)構(gòu)建立有向圖十字鏈表算法

思想：（1）初始化表頭向量、數(shù)據(jù)、指針（2）輸入一條弧，確定在G中位置，申請(qǐng)結(jié)點(diǎn)空間，賦值（3）插入到十字鏈表中（4）若InInfo=1，輸入其信息（5）重復(fù)（2）至（4），直到所有弧輸入完為止。7.2圖的存儲(chǔ)結(jié)構(gòu)建立有向圖十字鏈表算法7.2圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖的鄰接多重表存儲(chǔ)表示鄰接多重表結(jié)點(diǎn)結(jié)構(gòu)markivexilinkjvexinfo邊結(jié)點(diǎn)jlinkdatafirstedge頂點(diǎn)結(jié)點(diǎn)i頂點(diǎn)下一個(gè)依附于i頂點(diǎn)的邊j頂點(diǎn)下一個(gè)依附于j頂點(diǎn)的邊第1個(gè)依附于該頂點(diǎn)的邊7.2圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖的鄰接多重表存儲(chǔ)表示鄰接多7.2圖的存儲(chǔ)結(jié)構(gòu)例v1v2v4v5v30123v1v3v4v24v5010323212441^^^^^指向下一個(gè)依附于v1的邊指向下一個(gè)依附于v2的邊7.2圖的存儲(chǔ)結(jié)構(gòu)例v1v2v4v5v30123v1v37.2圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖鄰接多重表存儲(chǔ)表示#defineMAX_VERTEX_NUM20Typedefemnu{unvisited,visited}VisitIf;typedefstructArcBox//弧結(jié)點(diǎn){VisitIfmark;intivex,jvex;structEBox*ilink,*jlink;infoType*info;}EBox;TypedefstructVexBox//頂點(diǎn)結(jié)點(diǎn){VertexTypedata;EBox*firstedge;//指向第1條依附該頂點(diǎn)的邊}VexBox;Typedefstruct{//頂點(diǎn)表VexBoxadjlist[MAX_VERTEX_NUM];intvexnum,arcnum;}AMLGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖鄰接多重表存儲(chǔ)表示#defin7.3圖的遍歷從圖的某頂點(diǎn)出發(fā)，對(duì)圖中的每個(gè)頂點(diǎn)進(jìn)行一次訪(fǎng)問(wèn)且使每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次的過(guò)程。深度優(yōu)先遍歷廣度優(yōu)先遍歷7.3圖的遍歷從圖的某頂點(diǎn)出發(fā)，對(duì)圖中的7.3圖的遍歷思想：（1）從圖的某一頂點(diǎn)V0出發(fā)，訪(fǎng)問(wèn)該頂點(diǎn)；然后依次從V0的未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪(fǎng)問(wèn)到；（2）若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)為止

深度優(yōu)先遍歷7.3圖的遍歷思想：深度優(yōu)先遍歷7.3圖的遍歷V1V2V4V5V3V7V6V8例1深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V87.3圖的遍歷V1V2V4V5V3V7V6V8例1深度遍7.3圖的遍歷例2V1V2V4V5V3V7V6V8例3V1V2V4V5V3V7V6V8例2：V1V2V4V8V5V6V3V7例3：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例4例4：V1V2V4V8V3V6V7V57.3圖的遍歷例2V1V2V4V5V3V7V6V8例3V7.3圖的遍歷從上面例可見(jiàn):1.從深度優(yōu)先搜索遍歷連通圖的過(guò)程類(lèi)似于樹(shù)的先根遍歷;解決的辦法是:為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪(fǎng)問(wèn)標(biāo)志visited[w]”;2.如何判別V的鄰接點(diǎn)是否被訪(fǎng)問(wèn)？7.3圖的遍歷從上面例可見(jiàn):1.從深度優(yōu)先搜索遍歷連通7.3圖的遍歷開(kāi)始訪(fǎng)問(wèn)標(biāo)志初始化i=1Vi訪(fǎng)問(wèn)過(guò)DFSi=i+1i==Vexnums結(jié)束NNYY深度優(yōu)先遍歷算法開(kāi)始訪(fǎng)問(wèn)V,置標(biāo)志求V鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)W訪(fǎng)問(wèn)過(guò)結(jié)束NYNYDFSwV07.3圖的遍歷開(kāi)始訪(fǎng)問(wèn)標(biāo)志初始化i=1Vi訪(fǎng)問(wèn)過(guò)DFSi7.3圖的遍歷abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg訪(fǎng)問(wèn)標(biāo)志:訪(fǎng)問(wèn)次序:例如:achdkfe7.3圖的遍歷abchdekfg812345670F7.3圖的遍歷

廣度優(yōu)先搜索思想（1）從圖的某一頂點(diǎn)V0出發(fā)，訪(fǎng)問(wèn)該頂點(diǎn)后，依次訪(fǎng)問(wèn)V0的各個(gè)未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪(fǎng)問(wèn)到（2）若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)為止7.3圖的遍歷廣度優(yōu)先搜索思想7.3圖的遍歷V1V2V4V5V3V7V6V8例1廣度遍歷：V1V2V3V4V5V6V7V8V1V4V5V3V7V8V2V67.3圖的遍歷V1V2V4V5V3V7V6V8例1廣度遍7.3圖的遍歷例2V1V2V4V5V3V7V6V8例3V1V2V4V5V3V7V6V8例2：V1V2V3V4V5V6V7V8例3：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例4例4：V1V2V3V4V6V7V8V57.3圖的遍歷例2V1V2V4V5V3V7V6V8例3V7.3圖的遍歷廣度優(yōu)先遍歷算法思想：借助隊(duì)列開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪(fǎng)問(wèn)過(guò)BFSVi=Vi+1Vi==Vexnums結(jié)束NNYY7.3圖的遍歷廣度優(yōu)先遍歷算法開(kāi)始標(biāo)志數(shù)組初始化Vi=7.3圖的遍歷開(kāi)始訪(fǎng)問(wèn)V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V下一鄰接點(diǎn)ww訪(fǎng)問(wèn)過(guò)結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪(fǎng)問(wèn)w,置標(biāo)志w入隊(duì)NY7.3圖的遍歷開(kāi)始訪(fǎng)問(wèn)V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V7.4生成樹(shù)生成樹(shù)最小生成樹(shù)構(gòu)造最小生成樹(shù)7.4生成樹(shù)生成樹(shù)最小生成樹(shù)構(gòu)造最小生成樹(shù)7.4生成樹(shù)生成樹(shù)定義：所有（n個(gè)）頂點(diǎn)均由邊（n-1個(gè)）連接在一起，但不存在回路的圖深度優(yōu)先生成樹(shù)：由深度優(yōu)先遍歷得到的生成樹(shù)廣度優(yōu)先生成樹(shù)：由廣度優(yōu)先遍歷得到的生成樹(shù)生成森林：非連通圖每個(gè)連通分量的生成樹(shù)一起組成非連通圖7.4生成樹(shù)生成樹(shù)7.4生成樹(shù)說(shuō)明一個(gè)圖可以有許多棵不同的生成樹(shù)所有生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹(shù)是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n-1條邊生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹(shù)中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)7.4生成樹(shù)說(shuō)明7.4生成樹(shù)V5V1V2V4V3V7V6V8例深度：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹(shù)廣度：V1V2V3V4V5V6V7V8V5V1V2V4V3V7V6V8V5V1V2V4V3V7V6V87.4生成樹(shù)V5V1V2V4V3V7V6V8例深度：V17.4生成樹(shù)例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林7.4生成樹(shù)例ABLMCFDEGHKIJABLMCFJD7.4生成樹(shù)最小生成樹(shù)問(wèn)題提出

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線(xiàn)路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？頂點(diǎn)——表示城市權(quán)——城市間建立通信線(xiàn)路所需花費(fèi)代價(jià)

最?。ù鷥r(jià)）生成樹(shù)：希望找到一棵生成樹(shù)，它的每條邊上的權(quán)值之和即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小7.4生成樹(shù)最小生成樹(shù)7.4生成樹(shù)問(wèn)題分析

n個(gè)城市間，最多可設(shè)置n(n-1)/2條線(xiàn)路n個(gè)城市間建立通信網(wǎng)，只需n-1條線(xiàn)路該問(wèn)題等價(jià)于：構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。16543271317918127524107.4生成樹(shù)問(wèn)題分析165432713179181277.4生成樹(shù)構(gòu)造最小生成樹(shù)方法方法一：普里姆(Prim)算法（選點(diǎn)法）思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合（1）初始令U={u0},(u0V),TE=（2）在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)（3）將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)（4）重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹(shù)樹(shù)存儲(chǔ)結(jié)構(gòu)：鄰接矩陣表示算法實(shí)現(xiàn)算法評(píng)價(jià)：O(n2)7.4生成樹(shù)構(gòu)造最小生成樹(shù)方法7.4生成樹(shù)例16543265135664255352461314211316131446131425246131427.4生成樹(shù)例1654326513566425535247.4生成樹(shù)方法二：克魯斯卡爾算法（選邊法）思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合（1）初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V,{})，每個(gè)頂點(diǎn)自成一個(gè)連通分（2）在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊（3）依此類(lèi)推，直至T中所有頂點(diǎn)都在同一連通分量上為止7.4生成樹(shù)方法二：克魯斯卡爾算法（選邊法）7.4生成樹(shù)例165432651356642516543265135664257.4生成樹(shù)例1654326513566425165437.4生成樹(shù)算法描述：構(gòu)造非連通圖ST=(V,{});k=i=0;//k計(jì)選中的邊數(shù)while(k<n-1){++i;檢查邊集E中第i條權(quán)值最小的邊(u,v);

若(u,v)加入ST后不使ST中產(chǎn)生回路，

則輸出邊(u,v);

且k++;}7.4生成樹(shù)算法描述：7.4生成樹(shù)普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法7.4生成樹(shù)普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)7.5拓?fù)渑判蛴邢驘o(wú)環(huán)圖拓?fù)渑判蜿P(guān)鍵路徑7.5拓?fù)渑判蛴邢驘o(wú)環(huán)圖拓?fù)渑判蜿P(guān)鍵路徑7.5拓?fù)渑判蛴邢驘o(wú)環(huán)圖：一個(gè)無(wú)環(huán)的有向圖（DAG）是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過(guò)程的有效工具。7.5拓?fù)渑判蛴邢驘o(wú)環(huán)圖：一個(gè)無(wú)環(huán)的有向圖（DAG）7.5拓?fù)渑判騿?wèn)題提出：學(xué)生選修課程問(wèn)題頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無(wú)矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判蚨xAOV網(wǎng)——用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱(chēng)為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexnetwork)，簡(jiǎn)稱(chēng)AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件7.5拓?fù)渑判騿?wèn)題提出：學(xué)生選修課程問(wèn)題7.5拓?fù)渑判蛲負(fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線(xiàn)性序列的過(guò)程檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止7.5拓?fù)渑判蛲負(fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相7.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言語(yǔ)言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線(xiàn)性代數(shù)普通物理數(shù)值分析課程代號(hào)課程名稱(chēng)先修課C1C2C3C4C5C6C7C8C9C10C11C12例7.5拓?fù)渑判駽1無(wú)程序設(shè)計(jì)基礎(chǔ)課程代號(hào)7.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C12拓?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ù)湫蛄胁皇俏ㄒ坏?.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C107.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C127.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C3C4C5C6C7C8C9C10C11C127.5拓?fù)渑判駽2C3C4C5C6C7C8C9C10C11C12C3C4C5C6C7C8C9C10C11C127.5拓?fù)?.5拓?fù)渑判駽4C5C6C7C8C9C10C11C12C5C6C7C8C9C10C11C127.5拓?fù)渑判駽4C5C6C7C8C9C10C11C12C6C8C9C10C11C127.5拓?fù)渑判駽6C7C8C9C10C11C12C6C8C10C11C12C6C8C11C12C6C8C9C10C11C127.5拓?fù)渑判駽6C7C87.5拓?fù)渑判駽6C8C12C8C12C87.5拓?fù)渑判駽6C8C12C8C12C87.5拓?fù)渑判蛩惴▽?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ù)渑判蛲戤?.5拓?fù)渑判蛩惴▽?shí)現(xiàn)554325240122inlink^^^vexnext3^^0123456^7.5拓?fù)渑判?2104例123456top16toptop算法描述入度554325240122inlink^^^v7.5拓?fù)渑判?54325240122inlink^^^vexnext3^^0123456^輸出序列：63210416toptop7.5拓?fù)渑判?54325240122i7.5拓?fù)渑判蜉敵鲂蛄校?321041topp554325240122inlink^^^vexnext3^^0123456^7.5拓?fù)渑判蜉敵鲂蛄校?321041topp557.5拓?fù)渑判?122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp7.5拓?fù)渑判?122inlink5543^^^7.5拓?fù)渑判?122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp7.5拓?fù)渑判?122inlink5543^^^7.5拓?fù)渑判?112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp7.5拓?fù)渑判?112inlink5543^^^7.5拓?fù)渑判?112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp=NULL7.5拓?fù)渑判?112inlink5543^^^7.5拓?fù)渑判?112inlink5543^^^vexnext2^25^240123456^輸出序列：61321041toptop7.5拓?fù)渑判?112inlink5543^^^7.5拓?fù)渑判?112inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp7.5拓?fù)渑判?112inlink5543^^^7.5拓?fù)渑判?102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp47.5拓?fù)渑判?102inlink5543^^^7.5拓?fù)渑判?102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top7.5拓?fù)渑判?102inlink5543^^^7.5拓?fù)渑判?102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top7.5拓?fù)渑判?102inlink5543^^^7.5拓?fù)渑判?002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top37.5拓?fù)渑判?002inlink5543^^^7.5拓?fù)渑判?002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top37.5拓?fù)渑判?002inlink5543^^^7.5拓?fù)渑判?002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top37.5拓?fù)渑判?002inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top37.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p=NULL4top37.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044top37.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044topp7.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp7.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp7.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp27.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp27.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044top2p=NULL7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044top2p=NULL7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044topp=NULL7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：61324321044top7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：6132432104topp7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext0^25^240123456^輸出序列：6132432104topp57.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext0^25^240123456^輸出序列：6132432104topp=NULL57.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext0^25^240123456^輸出序列：61324532104top57.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext0^25^240123456^輸出序列：61324532104topp=NULL7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判蛩惴ǚ治鼋ㄠ徑颖恚篢(n)=O(e)搜索入度為0的頂點(diǎn)的時(shí)間：T(n)=O(n)拓?fù)渑判颍篢(n)=O(n+e)7.5拓?fù)渑判蛩惴ǚ治鼋ㄠ徑颖恚篢(n)=O(e)7.5拓?fù)渑判騿?wèn)題提出

假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間。問(wèn)題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？1956年，美國(guó)杜邦公司提出關(guān)鍵路徑法，并于1957年首先用于1000萬(wàn)美元進(jìn)行化工廠(chǎng)建設(shè)，工期比原計(jì)劃縮短了4個(gè)月。杜邦公司在采用關(guān)鍵路徑法的一年中，節(jié)省了100萬(wàn)美元。例如：有一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件(v1--v9)v1--表示整個(gè)工程開(kāi)始v9--表示整個(gè)工程結(jié)束v9v8v7v6v4v5v3v2v1a1=6a2=4a3=5a4=1a5=1a6=2a7=8a8=7a9=4a10=2a11=47.5拓?fù)渑判騿?wèn)題提出假設(shè)以有向網(wǎng)表示一7.5拓?fù)渑判蚨xAOE網(wǎng)(ActivityOnEdge)——即邊表示活動(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)7.5拓?fù)渑判蚨x7.5拓?fù)渑判蛘麄€(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑。12345678964521187244例如:“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加

將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。源點(diǎn)匯點(diǎn)61747.5拓?fù)渑判蛘麄€(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)7.5拓?fù)渑判?/p>

如何求關(guān)鍵活動(dòng)？該活動(dòng)的最早開(kāi)始時(shí)間=該活動(dòng)的最遲開(kāi)始時(shí)間ijdut問(wèn)題分析持續(xù)時(shí)間7.5拓?fù)渑判蛉绾吻箨P(guān)鍵活動(dòng)？該活動(dòng)的最早開(kāi)始時(shí)間ij7.5拓?fù)渑判颉笆录?頂點(diǎn))”的最早發(fā)生時(shí)間ve(j)ve(j)=從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度;“事件(頂點(diǎn))”的最遲發(fā)生時(shí)間vl(k)vl(k)=從頂點(diǎn)k到匯點(diǎn)的最短路徑長(zhǎng)度;7.5拓?fù)渑判颉笆录?頂點(diǎn))”的最早發(fā)生時(shí)間ve(7.5拓?fù)渑判?/p>

假設(shè)第i條弧為<j,k>則對(duì)第i項(xiàng)活動(dòng)言“活動(dòng)(弧)”的最早開(kāi)始時(shí)間ee(i)ee(i)=ve(j);“活動(dòng)(弧)”的最遲開(kāi)始時(shí)間el(i)el(i)=vl(k)–dut(<j,k>);7.5拓?fù)渑判蚣僭O(shè)第i條弧為<j,k>7.5拓?fù)渑判?/p>

事件發(fā)生時(shí)間的計(jì)算公式:ve(源點(diǎn))=0;ve(k)=Max{ve(j)+dut(<j,k>)}vl(匯點(diǎn))=ve(匯點(diǎn));vl(j)=Min{vl(k)–dut(<j,k>)}7.5拓?fù)渑判蚴录l(fā)生時(shí)間的計(jì)算公式:7.5拓?fù)渑判?2345678964521187244拓?fù)溆行蛐蛄?1-4-6-3-2-5-8-7-9000000000645711571514181818181818181818181614866108077.5拓?fù)渑判?2345678964521187244拓7.5拓?fù)渑判?6457715141818141610786600006457771514141602366887107.5拓?fù)渑判?645771514181814161077.5拓?fù)渑判蚯箨P(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)0645771514181814161078660123456789645211872447.5拓?fù)渑判蚯箨P(guān)鍵路徑步驟064577151418187.5拓?fù)渑判蛩惴▽?shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)從源點(diǎn)V1出發(fā)，令Ve[1]=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的Ve[i]從匯點(diǎn)Vn出發(fā)，令Vl[n]=Ve[n],按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的Vl[i]根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)要點(diǎn)：顯然，求ve的順序應(yīng)該是按拓?fù)溆行虻拇涡?而求vl的順序應(yīng)該是按拓?fù)淠嫘虻拇涡?因?yàn)橥負(fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械哪嫘蛄?，因此?yīng)該在拓?fù)渑判虻倪^(guò)程中，另設(shè)一個(gè)“?！庇浵峦?fù)溆行蛐蛄小?.5拓?fù)渑判蛩惴▽?shí)現(xiàn)要點(diǎn)：顯然，求ve的順序應(yīng)該是按拓7.5拓?fù)渑判蛩惴枋鲚斎腠旤c(diǎn)和弧信息，建立其鄰接表計(jì)算每個(gè)頂點(diǎn)的入度對(duì)其進(jìn)行拓?fù)渑判蚺判蜻^(guò)程中求頂點(diǎn)的Ve[i]將得到的拓?fù)湫蛄羞M(jìn)棧按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)改寫(xiě)算法7.127.5拓?fù)渑判蛩惴枋龈膶?xiě)算法7.127.6最短路徑

每一對(duì)頂點(diǎn)之間的最短路徑從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑7.6最短路徑每一對(duì)頂點(diǎn)從某個(gè)源點(diǎn)到7.6最短路徑問(wèn)題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)圖中：頂點(diǎn)——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線(xiàn)路的長(zhǎng)度或沿此線(xiàn)路運(yùn)輸所花的時(shí)間或費(fèi)用等問(wèn)題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑7.6最短路徑問(wèn)題提出用帶權(quán)的有向圖表示一個(gè)交7.6最短路徑從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑24158639735104afedbcg2最短路徑長(zhǎng)度<a,d,g,b>22<a,c>8<a,d>15<a,c,f,e>13<a,c,f>11<a,g>197.6最短路徑從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑24157.6最短路徑求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想:依最短路徑的長(zhǎng)度遞增的次序求得各條路徑源點(diǎn)v1…其中，從源點(diǎn)到頂點(diǎn)v1的最短路徑是所有最短路徑中長(zhǎng)度最短者。v27.6最短路徑求從源點(diǎn)到其余各點(diǎn)的最短路徑的7.6最短路徑在這條路徑上，必定只含一條弧，并且