《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》d

第7章圖編輯ppt第2

頁7.1圖的術(shù)語與定義圖的定義圖(Graph)——圖G是由兩個(gè)集合V(G)和E(G)組成的，記為G=(V,E)其中：V(G)是頂點(diǎn)的非空有限集

E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?。圖的分類有向圖無向圖編輯ppt第3

頁7.1圖的術(shù)語與定義圖的定義有向圖——有向圖G是由兩個(gè)集合V(G)和E(G)組成的。

其中：

V(G)是頂點(diǎn)的非空有限集。

E(G)是有向邊（也稱?。┑挠邢藜希∈琼旤c(diǎn)的有序?qū)?，記?/p>

<v,w>，v、w是頂點(diǎn)，v為弧尾，w為弧頭。編輯ppt第4

頁7.1圖的術(shù)語與定義例如：G1=<V1,E1>V1={A,B,C,D,E}E1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,

<D,A>,<E,C>}EACBD編輯ppt第5

頁7.1圖的術(shù)語與定義圖的定義無向圖——無向圖G是由兩個(gè)集合V(G)和E(G)組成的。 其中： V(G)是頂點(diǎn)的非空有限集。

E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記?/p>

(v,w)或

(w,v)，并且

(v,w)=(w,v)。編輯ppt第6

頁7.1圖的術(shù)語與定義例如：G2=<V2,E2>

V2={v0,v1,v2,v3,v4}

E2={(v0,v1),(v0,v3),(v1,v2),(v1,v4),

(v2,v3),(v2,v4)}V0V4V3V1V2編輯ppt網(wǎng)(Network)弧或邊帶權(quán)(Weight)的圖分別稱有向網(wǎng)和無向網(wǎng)ABCDE1341423906617.1圖的術(shù)語與定義編輯ppt第8

頁7.1圖的術(shù)語與定義圖的應(yīng)用舉例 例1.交通圖（公路、鐵路）

頂點(diǎn)：地點(diǎn) 邊：連接地點(diǎn)的路 例2.電路圖

頂點(diǎn)：元件 邊：連接元件之間的線路 例3.通訊線路圖

頂點(diǎn)：通訊站點(diǎn)

邊：站點(diǎn)間的連線 例4.各種流程圖 如產(chǎn)品的生產(chǎn)流程圖。

頂點(diǎn)：工序 邊：各道工序之間的順序關(guān)系編輯ppt第9

頁7.1圖的術(shù)語與定義圖的基本術(shù)語鄰接點(diǎn)及關(guān)聯(lián)邊 鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn)互為鄰接點(diǎn) 關(guān)聯(lián)邊：若邊e=(v,u),則稱頂點(diǎn)v、u關(guān)連邊e。頂點(diǎn)V的度

=與V相關(guān)聯(lián)的邊的數(shù)目eV0V4V3V1V2編輯ppt第10

頁7.1圖的術(shù)語與定義頂點(diǎn)的度、入度、出度

在有向圖中：

頂點(diǎn)V的出度

=以V為起點(diǎn)的有向邊數(shù)

頂點(diǎn)V的入度

=以V為終點(diǎn)的有向邊數(shù)

頂點(diǎn)V的度

=V的出度+V的入度

ABCDE設(shè)圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e

圖的所有頂點(diǎn)的度數(shù)和=2*e編輯ppt假設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則

含有e=n(n-1)/2條邊的無向圖稱作完全圖(Completedgraph)

含有e=n(n-1)

條弧的有向圖稱作有向完全圖

若邊或弧的個(gè)數(shù)e<nlogn，則稱作稀疏圖(Sparsegraph)，否則稱作稠密圖(Densegraph).BADEC7.1圖的術(shù)語與定義編輯ppt第12

頁7.1圖的術(shù)語與定義路徑、回路

假設(shè)v1,v2,…,vk為圖G=（V，E）的頂點(diǎn)序列，若G為無向圖，則有(vi,vi+1)E；或者G為有向圖，則有<vi,vi+1>E；其中(1≤i=1<k)，v=v1,u=vk，則稱該序列是從頂點(diǎn)v到頂點(diǎn)u的路徑；路徑上邊的數(shù)目稱作路徑長度。

若第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則稱該序列為回路。

序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑定義為簡單路徑

構(gòu)成回路的簡單路徑稱其為簡單回路編輯ppt第13

頁7.1圖的術(shù)語與定義例如 在圖G1中，V0,V1,V2,V3是V0到V3的路徑，而且是簡單路徑；V0,V1,V2,V3,V0是簡單回路。無向圖G1有向圖G2V0V4V3V1V2V0V1V2V3 在圖G2中，V0,V2,V3是V0到V3的簡單路徑；V0,V2,V3,V0是簡單回路。編輯ppt第14

頁7.1圖的術(shù)語與定義連通圖 在無向圖G=<V,E>中，若對任何兩個(gè)頂點(diǎn)v、u都存在從v到u的路徑，則稱G是連通圖。

G2:非連通圖G1:連通圖V0V2V3V1V5V4V0V4V3V1V2編輯ppt第15

頁7.1圖的術(shù)語與定義子圖 設(shè)有兩個(gè)圖G=(V，E)，G1=(V1，E1)，若V1

V且E1

E，則稱G1是G的子圖。例(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2

(b)、(c)

是(a)

的子圖編輯ppt第16

頁7.1圖的術(shù)語與定義若無向圖為非連通圖，則各個(gè)極大連通子圖稱作此圖的連通分量。

極大連通子圖含義：該子圖是G的連通子圖，將G的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通。連通分量非連通圖V0V2V3V1V5V4編輯ppt第17

頁7.1圖的術(shù)語與定義強(qiáng)連通圖

在有向圖G=<V,E>中，若對任何兩個(gè)頂點(diǎn)v、u都存在從v到u的路徑，則稱G是強(qiáng)連通圖。強(qiáng)連通圖非強(qiáng)連通圖V0V1V2V3V0V1V2V3編輯ppt第18

頁7.1圖的術(shù)語與定義若有向圖為非強(qiáng)連通圖，它的各個(gè)極大強(qiáng)連通子圖稱為它的強(qiáng)連通分量。

極大強(qiáng)連通子圖含義：該子圖是D的強(qiáng)連通子圖，將D的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)連通的。強(qiáng)連通分量

V0

V2

V3

V1V0V1V2V3編輯ppt第19

頁7.1圖的術(shù)語與定義生成樹

連通圖G中，包含所有頂點(diǎn)的極小連通子圖稱為G的生成樹。

極小連通子圖含義：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。

若T是G的生成樹當(dāng)且僅當(dāng)T滿足如下條件： T包含G的所有頂點(diǎn) T是G的連通子圖

T中無回路連通圖G1G1的生成樹V0V4V3V1V2V0V4V3V1V2編輯ppt207.1圖的基本操作1、結(jié)構(gòu)的建立和銷毀2、對頂點(diǎn)的訪問操作3、對鄰接點(diǎn)的操作4、插入或刪除頂點(diǎn)5、插入和刪除弧6、遍歷編輯ppt217.1圖的基本操作結(jié)構(gòu)的建立和銷毀CreatGraph(&G,V,VR):按定義(V,VR)構(gòu)造圖DestroyGraph(&G):銷毀圖對頂點(diǎn)的訪問操作LocateVex(G,u);若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中“位置”；否則返回其它信息GetVex(G,v);返回v的值PutVex(&G,v,value);對v賦值value

編輯ppt227.1圖的基本操作對鄰接點(diǎn)的操作FirstAdjVex(G,v);返回v的“第一個(gè)鄰接點(diǎn)”。若該頂點(diǎn)在G中沒有鄰接點(diǎn)，則返回“空”NextAdjVex(G,v,w);返回v的（相對于w的）“下一個(gè)鄰接點(diǎn)”。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。插入或刪除頂點(diǎn)InsertVex(&G,v);在圖G中增添新頂點(diǎn)vDeleteVex(&G,v);刪除G中頂點(diǎn)v及其相關(guān)的弧

編輯ppt237.1圖的基本操作插入和刪除弧DeleteVex(&G,v);刪除G中頂點(diǎn)v及其相關(guān)的弧DeleteArc(&G,v,w);在G中刪除弧<v,w>若G是無向的，則還刪除對稱弧<w,v>遍歷DFSTraverse(G,v,Visit());從頂點(diǎn)v起深度優(yōu)先遍歷圖G并對每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次BFSTraverse(G,v,Visit());從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次編輯ppt247.2圖的存儲(chǔ)表示

1、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示2、圖的鄰接表存儲(chǔ)表示3、有向圖的十字鏈表存儲(chǔ)表示4、無向圖的鄰接多重表存儲(chǔ)表示編輯ppt第25

頁7.2圖的存儲(chǔ)結(jié)構(gòu)一、數(shù)組表示法（鄰接矩陣表示）

鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：A[i][j]=1若(vi,vj)E或<vi,vj>E0否則01010010101011010001100在數(shù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系011000000001000V1V2V3V4V1V5V4V2V3vi的度？第i

行(列)1的個(gè)數(shù)。vi的出度?第i

行1的個(gè)數(shù)第i列1的個(gè)數(shù)。vi

的入度？編輯ppt第26

頁7.2圖的存儲(chǔ)結(jié)構(gòu)二、鄰接表

鄰接表是圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 1、無向圖的鄰接表

頂點(diǎn)：通常按編號(hào)順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在一維數(shù)組中；

邊節(jié)點(diǎn)：對于每個(gè)頂點(diǎn)，用線性邊節(jié)點(diǎn)鏈表存儲(chǔ)關(guān)聯(lián)鄰接點(diǎn)編號(hào)。

01234m-1V1V2V3V4V513V1V5V4V2V30241340212鄰接點(diǎn)的位置共有多少邊節(jié)點(diǎn)？2*e編輯ppt第27

頁7.2圖的存儲(chǔ)結(jié)構(gòu)typedefstructArcNode//邊結(jié)點(diǎn)定義 {intadjvex;//鄰接點(diǎn)域，//存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置

structArcNode*next;//鏈域，下一條邊或弧

}

ArcNode;adjvexnextvexdatafirstarctypedefstructtnode//頂點(diǎn)結(jié)點(diǎn)定義 {intvexdata;//存放頂點(diǎn)信息

ArcNode*firstarc;//指向第一個(gè)邊或弧

}

VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//圖的定義 { AdjListvertices; int vexnum,arcnum;//頂點(diǎn)數(shù)和弧數(shù) int kind;//圖的種類 }編輯ppt第28

頁7.2圖的存儲(chǔ)結(jié)構(gòu)無向圖的鄰接表的特點(diǎn)

1）頂點(diǎn)v的度：等于v對應(yīng)線性鏈表的長度；

2）判定兩頂點(diǎn)v，u是否鄰接：要看v對應(yīng)線性鏈表中是否存在u。

3）在G中增減邊：要在兩個(gè)單鏈表插入、刪除結(jié)點(diǎn)；

4）設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為m（m圖的頂點(diǎn)數(shù)n），圖的邊數(shù)為

e，G占用存儲(chǔ)空間為：m個(gè)點(diǎn)+2*e個(gè)表節(jié)點(diǎn)。G占用存儲(chǔ)空間與G的頂點(diǎn)數(shù)、邊數(shù)均有關(guān)；適用于邊稀疏的圖。編輯ppt第29

頁7.2圖的存儲(chǔ)結(jié)構(gòu)二、鄰接表 2、有向圖的鄰接表 頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序） 以同一頂點(diǎn)為起點(diǎn)的?。河镁€性出邊節(jié)點(diǎn)鏈表存儲(chǔ)弧頭位置1234v1v3v4v2vexdatafirstarc

3

2

4

1^^^^adjvexnextV1V2V3V4弧頭的位置頂點(diǎn)i

的出度?頂點(diǎn)i的出邊表長度共有多少邊節(jié)點(diǎn)？e出邊表編輯ppt第30

頁7.2圖的存儲(chǔ)結(jié)構(gòu)二、鄰接表 3、有向圖的逆鄰接表 頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序） 以同一頂點(diǎn)為終點(diǎn)的?。河糜涗浕∥参恢玫木€性入邊節(jié)點(diǎn)鏈表存儲(chǔ)。1234v1v3v4v2vexdatafirstarc

4

1

1

3^^^^V1V2V3V4弧尾的位置頂點(diǎn)i

的入度?頂點(diǎn)i的入邊表長度共有多少邊節(jié)點(diǎn)？e入邊表編輯ppt第31

頁7.2圖的存儲(chǔ)結(jié)構(gòu)三、有向圖的十字鏈表表示法弧結(jié)點(diǎn)：typedefstructArcBox{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置

structarcnode*hlink；//指向弧頭相同的下一條弧

structarcnode*tlink;//指向弧尾相同的下一條弧}ArcBox;tailvexheadvexhlinktlink頂點(diǎn)結(jié)點(diǎn)：typedefstructVexNode{VertexTypedata;//存與頂點(diǎn)有關(guān)信息

ArcBox*firstin；//指向以該頂點(diǎn)為弧頭的第1個(gè)弧結(jié)點(diǎn)

ArcBox*firstout;//指向以該頂點(diǎn)為弧尾的第1個(gè)弧結(jié)點(diǎn)}VexNode;VexNodeOLGraph[M];datafirstinfirstout編輯ppt第32

頁7.2圖的存儲(chǔ)結(jié)構(gòu)三、有向圖的十字鏈表表示法例bdacabcd123413123431434241^^^^^^^^相同弧尾相同弧頭編輯ppt第33

頁7.2圖的存儲(chǔ)結(jié)構(gòu)四、無向圖的鄰接多重表表示法頂點(diǎn)結(jié)點(diǎn)：typedefstructVexBox{VertexTypedata;//存與頂點(diǎn)有關(guān)的信息

EBox*firstedge;//指向第一條依附于該頂點(diǎn)的邊}

VexBox;VexBoxAMLGraph[M];datafirstedge邊結(jié)點(diǎn)：typedefstructnode{VisitIfmark;//標(biāo)志域，記錄是否已經(jīng)搜索過

intivex,jvex;//該邊依附的兩個(gè)頂點(diǎn)在表頭數(shù)組中位置

structEBox*ilink,*jlink;//分別指向依附于ivex和jvex的下一條邊}

EBox;markivexilinkjvexjlink編輯ppt第34

頁7.2圖的存儲(chǔ)結(jié)構(gòu)四、無向圖的鄰接多重表表示法例aecbd1234acdb5e

12

14

34

3235

52^^^^^編輯ppt第35

頁7.3圖的遍歷圖的遍歷

訪遍圖中所有的頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次。遍歷實(shí)質(zhì)

遍歷所有連通分量，

對于連通子圖：根據(jù)鄰接關(guān)系遍歷所有頂點(diǎn)。

設(shè)置數(shù)組visited[0,…n]區(qū)分未訪問的子圖信息搜索路徑深度優(yōu)先遍歷（DFS）廣度優(yōu)先遍歷（BFS）編輯ppt第36

頁7.3圖的遍歷圖的深度遍歷（DFS）

深度優(yōu)先遍歷連通圖的過程類似于樹的先根遍歷，從圖中某個(gè)頂點(diǎn)V出發(fā)，訪問此頂點(diǎn)，然后依次從V的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V有路徑相通的頂點(diǎn)都被訪問到Vw1SG1SG2w2w3w2…V編輯ppt第37

頁7.3圖的遍歷圖的深度遍歷（DFS）例：achdekfachdkfeachkfed訪問次序bg編輯ppt第38

頁7.3圖的遍歷圖的深度遍歷（DFS）例：bgabchdekfachdkfeachkfedbg訪問次序bg編輯ppt第39

頁7.3圖的遍歷圖的深度遍歷（DFS）V1V2V4V5V3V7V6V8例1深度遍歷1：V1V2V4V8V5V6V3V7由于沒有規(guī)定訪問鄰接點(diǎn)的順序，所以深度優(yōu)先序列不惟一。深度遍歷2：V1V3V7V8V6V5V2V4編輯ppt第40

頁7.3圖的遍歷圖的深度遍歷（DFS）——算法7.4和7.5開始標(biāo)志數(shù)組初始化V=0V訪問過?DFS(g,v)V=V+1V<VexNum結(jié)束NYYNDFS開始訪問V,置標(biāo)志求V鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)W訪問過結(jié)束NYNYDFS(G,w)編輯ppt第41

頁7.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法voidDFSTrav(GraphG,Void(*Visit)(VertexTypee)){

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v,Visit);}//DFSTrav訪問標(biāo)志數(shù)組：intvisited[]

全局變量，初始時(shí)所有分量全為FALSE編輯ppt第42

頁7.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法voidDFS(GraphG,intv,void(*Visit)(VertexTypee)){

/*從v出發(fā)（v是頂點(diǎn)位置），深度優(yōu)先遍歷v所在的連通分量*/visited[v]=TRUE;

Visit(v);//先根遍歷for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w,Visit(w));}//DFS編輯ppt第43

頁7.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V7V6V2V5V8V4編輯ppt第44

頁7.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法V1V2V4V5V3V7V6V8例12341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^深度遍歷：V1V3V7V6V2V4V8V5編輯ppt第45

頁7.3圖的遍歷深度優(yōu)先遍歷的時(shí)間復(fù)雜度 DFS對每一條邊處理一次（無向圖的每條邊從兩個(gè)方向處理），每個(gè)頂點(diǎn)訪問一次。鄰接表表示總代價(jià)為：O(點(diǎn)數(shù)n+邊數(shù)e)鄰接矩陣表示查詢單個(gè)頂點(diǎn)的所有鄰接點(diǎn)信息，需要O(n)的時(shí)間，所以總代價(jià)為O(n2)。編輯ppt第46

頁7.3圖的遍歷圖的廣度遍歷（BFS） 從圖中某頂點(diǎn)v出發(fā)： 1)訪問頂點(diǎn)v； 2)訪問v所有未被訪問的鄰接點(diǎn)w1,w2,…wk； 3)依次從這些鄰接點(diǎn)出發(fā)，訪問其所有未被訪問的鄰接點(diǎn)。依此類推，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。編輯ppt第47

頁7.3圖的遍歷圖的廣度遍歷（BFS）例：abchdekfgacdefhkachkfed訪問次序編輯ppt第48

頁7.3圖的遍歷圖的廣度遍歷（BFS）——遞歸算法開始標(biāo)志數(shù)組初始化V=0V訪問過BFSV=V+1V<Vexnum結(jié)束NYYN編輯ppt第49

頁7.3圖的遍歷圖的廣度遍歷（BFS）——遞歸算法voidBFSTraverse(GraphG,void(*Visit)(VertexType)){//本算法對圖G進(jìn)行廣度優(yōu)先遍歷

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標(biāo)志數(shù)組初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])BFS(G,v,Visit);}//BFSTraverse編輯ppt第50

頁7.3圖的遍歷圖的廣度遍歷（BFS）——算法7.6開始訪問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ì)NY編輯ppt第51

頁7.3圖的遍歷voidBFS(GraphG,intv,void(*Visit)(VertexTypee)){//從第v個(gè)頂點(diǎn)出發(fā)

InitQueue(Q);//建立輔助空隊(duì)列Q

Visit(v);visited[v]=TRUE;

//訪問u，訪問標(biāo)志數(shù)組EnQueue(Q,v);//v入隊(duì)

while(!QueueEmpty(Q)){DeQueue(Q,u);//隊(duì)頭元素出隊(duì)，并賦值給ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){Visit(w);visited[w]=TRUE;

//訪問uEnQueue(Q,w);}}//while}//BFS編輯ppt第52

頁7.3圖的遍歷圖的廣度遍歷（BFS）例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

20123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：143編輯ppt第53

頁7.3圖的遍歷圖的廣度遍歷（BFS）例14235012345432fr遍歷序列：1432012345

32fr遍歷序列：1432012345

325fr遍歷序列：1432512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2編輯ppt第54

頁7.3圖的遍歷圖的廣度遍歷（BFS）/p>

25fr遍歷序列/p>

5fr遍歷序列/p>

fr遍歷序列：1432512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2編輯ppt第55

頁7.3圖的遍歷遍歷的應(yīng)用 求兩個(gè)頂點(diǎn)之間的最短路徑長度

廣度優(yōu)先搜索訪問頂點(diǎn)的次序是按“路徑長度”漸增的次序。求路徑長度最短的路徑可以基于廣度優(yōu)先搜索遍歷進(jìn)行。abchdekfg編輯ppt第56

頁7.4圖的最小生成樹生成樹

包含無向圖G所有頂點(diǎn)的極小連通子圖稱為G生成樹，它只有n-1條邊，可以構(gòu)成一棵樹。

極小連通子圖含義：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。

生成樹T的特點(diǎn)：

T是G的連通子圖

T包含G的所有頂點(diǎn) T中有n-1條邊T中無回路

連通圖G1G1的生成樹V0V4V3V1V2V0V4V3V1V2編輯ppt第57

頁7.4圖的最小生成樹問題提出

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？問題分析和數(shù)學(xué)建模：

頂點(diǎn)——表示城市

權(quán)——城市間建立通信線路所需花費(fèi)代價(jià)

希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小——最小代價(jià)生成樹MST(MinimumcostSpanningTree)

編輯ppt7.4圖的最小生成樹最小生成樹(Leastweightedspanningtree)：權(quán)（之和）最小的生成樹。V3V1V4V6V5V23652165546V3V1V4V6V5V22415V3V1V4V6V5V2編輯ppt第59

頁7.4圖的最小生成樹最小生成樹的MST性質(zhì) 若U集是V的一個(gè)非空子集，若在所有聯(lián)接U和V-U的邊中，(u,v)權(quán)值最小，其中uU，vV-U；則：必有一棵最小生成樹包含(u,v)。典型算法普里姆(Prim)算法將頂點(diǎn)歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)?？唆斔箍?Kruskal)算法將邊歸并，適于求稀疏網(wǎng)的最小生成樹。編輯ppt60基本思想：從初始點(diǎn)u0開始將u0作為當(dāng)前的最小生成樹：T向T中增加一個(gè)節(jié)點(diǎn)：從與T的節(jié)點(diǎn)相連的所有邊中（不包含兩個(gè)頂點(diǎn)都在T內(nèi)的邊），找到最短的邊，將該邊及相應(yīng)節(jié)點(diǎn)加入T中直到所有的節(jié)點(diǎn)都加入T中為止7.4圖的最小生成樹編輯ppt第61

頁7.4圖的最小生成樹普里姆算法（Prim）

設(shè)G=(V,GE)為一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U,TE)為生成樹。

(1)初始時(shí)，U={u0}，TE=；

(2)在所有uU且vV-U的邊(u,v)中選擇一條權(quán)值最小的邊，不妨設(shè)為(u,v)；

(3)(u,v)加入TE，同時(shí)將v加入U(xiǎn)；

(4)重復(fù)(2)(3)，直到U=V為止；編輯ppt第62

頁7.4圖的最小生成樹普魯姆算法（Prim）——教材P175V3V1V4V6V5V23652165546V3V1V4V6V5V212V3V1V4V6V5V214V3V1V4V6V5V2142V3V1V4V6V5V21452V3V1V4V6V5V21453U={V1}U={V1,V3}U={V1,V3,V6}U={V1,V3,V6,V4}U={V1,V3,V6,V4,V2}U={V1,V3,V6,V4,V2,V5}編輯ppt第63

頁7.4圖的最小生成樹輔助數(shù)組closedge[]對不在生成樹中的每個(gè)頂點(diǎn)，記錄其和生成樹頂點(diǎn)相關(guān)聯(lián)且代價(jià)最小的邊：struct{VertexTypeAdjvex;//相關(guān)頂點(diǎn)VRTypelowcost;//最小邊的權(quán)值}closedge[MAX_VERTEX_NUM];

closedge.Adjvex[v]：

頂點(diǎn)v到子集U中權(quán)最小邊(v,u)相關(guān)聯(lián)的頂點(diǎn)u

closedge.lowcost[v]：

頂點(diǎn)v到子集U權(quán)最小邊

(v,u)的權(quán)值(距離)編輯ppt第64

頁7.4圖的最小生成樹

V1V1V1

V10

6

1

5

maxmax

0(V1)

1(V2)

2(V3)3(V4)4(V5)5(V6)

closedge.Adjvexclosedge.Lowcost

3652165546V6V5V4V3V2V1

V1V3V1

V1V3V3

0

5

0

5

64

0(V1)

1(V2)

2(V3)3(V4)4(V5)5(V6)

closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V2V1編輯ppt第65

頁7.4圖的最小生成樹

V3V1V1V3V30

5

0

564

0(V1)

1(V2)

2(V3)3(V4)4(V5)

5(V6)

closedge.Adjvexclosedge.Lowcost

0(V1)

1(V2)

2(V3)3(V4)4(V5)

5(V6)

V3V1V6V3V30

5

0

260closedge.Adjvexclosedge.Lowcost

3652165546V6V5V4V3V26V5V4V3V2V1編輯ppt第66

頁7.4圖的最小生成樹

V3V1

V6V3V30

5

00

6

0

0(V1)

1(V2)

2(V3)

3(V4)4(V5)

5(V6)

closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V2V1

V3

V1

V6

V3V30

5

0

0

6

0

0(V1)

1(V2)

2(V3)

3(V4)4(V5)

5(V6)closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V2V1編輯ppt第67

頁7.4圖的最小生成樹

V3V1V6

V3

V30000

3

0

0(V1)1(V2)2(V3)3(V4)

4(V5)

5(V6)

closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V26V5V4V3V2V1

V3

V1

V6

V3V30

5

0

0

6

0

0(V1)

1(V2)

2(V3)

3(V4)4(V5)

5(V6)closedge.Adjvexclosedge.Lowcost編輯ppt第68

頁7.4圖的最小生成樹

V3V1V6V3V3000000

0(V1)1(V2)2(V3)3(V4)4(V5)5(V6)closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V26V5V4V3V2V1編輯ppt第69

頁7.4圖的最小生成樹voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹

k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)closedge[j]={u,G.arcs[k][j]};closedge[k].Lowcost=0;//初始，U＝{u}for(i=1;i<G.vexnum;++i){}繼續(xù)向生成樹上添加頂點(diǎn);編輯ppt第70

頁7.4圖的最小生成樹

k=minimum(closedge);

//求出加入生成樹的下一個(gè)頂點(diǎn)(k)printf(closedge[k].Adjvex,G.vexs[k]);

//輸出生成樹上一條邊

closedge[k].Lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集

for(j=0;j<G.vexnum;++j)//修改其它頂點(diǎn)到生成樹的最小邊

if(G.arcs[k][j]<closedge[j].Lowcost)closedge[j]={G.vexs[k],G.arcs[k][j]};

編輯ppt第71

頁7.4圖的最小生成樹普里姆算法的性能 設(shè)n是圖的頂點(diǎn)數(shù)，普魯姆算法的時(shí)間復(fù)雜度為O(n2)。 與邊數(shù)無關(guān)，適用于求邊稠密的網(wǎng)的最小生成樹。編輯ppt第72

頁7.4圖的最小生成樹克魯斯卡爾(Kruskal)算法 設(shè)連通網(wǎng)N=(V,{E})。

1)初始時(shí)最小生成樹只包含圖的n個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)為一棵子樹； 2)選取權(quán)值較小且所關(guān)聯(lián)的兩個(gè)頂點(diǎn)不在同一子樹的邊，將此邊加入到最小生成樹中；

3)重復(fù)2）n-1次，即得到包含n個(gè)頂點(diǎn)和n-1條邊的最小生成樹。編輯ppt第73

頁7.4圖的最小生成樹克魯斯卡爾(Kruskal)算法566154V3V1V4V6V5V2365216543212345編輯ppt7.4克魯斯卡爾算法構(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++;}編輯ppt123456第75

頁7.4圖的最小生成樹克魯斯卡爾(Kruskal)算法16543212345datajihe124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222采用邊集數(shù)組的形式保存圖：566154V3V1V4V6V5V23652編輯ppt第76

頁7.4圖的最小生成樹克魯斯卡爾的性能 設(shè)圖的邊數(shù)是e，克魯斯卡爾算法的時(shí)間復(fù)雜度為O(eloge)。

適用于求邊稀疏的網(wǎng)的最小生成樹。編輯ppt第77

頁7.4圖的最小生成樹兩種算法比較普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍編輯ppt7.5重連通圖和關(guān)節(jié)點(diǎn)定義：若從一個(gè)連通圖中刪去一個(gè)頂點(diǎn)及其相關(guān)聯(lián)的邊，連通圖成為兩個(gè)或多個(gè)連通分量，則該點(diǎn)稱為關(guān)節(jié)點(diǎn)。定義：若從一個(gè)連通圖中刪去任意一個(gè)頂點(diǎn)及其相關(guān)聯(lián)的邊，它仍為一個(gè)連通圖的話，則該連通圖被稱為重（雙）連通圖。ahgcbfde雙連通圖中沒有關(guān)節(jié)點(diǎn)沒有關(guān)節(jié)點(diǎn)的連通圖為雙連通圖編輯ppt7.5重連通圖和關(guān)節(jié)點(diǎn)abcdefgh對G進(jìn)行深度優(yōu)先遍歷，得到深度優(yōu)先生成樹T虛線表示回邊：即在G中但不在T中的邊,是遍歷時(shí)選擇

已訪問的鄰接點(diǎn)ahgcbfde編輯ppt關(guān)節(jié)點(diǎn)的特征特征1：若生成樹的根結(jié)點(diǎn)，有兩個(gè)或兩個(gè)以上的分支，則此頂點(diǎn)(生成樹的根)必為關(guān)節(jié)點(diǎn)；ahgcbfdeabcdefgh編輯ppt特征2：對生成樹上的任意一個(gè)“頂點(diǎn)”，若某棵子樹的根或子樹中的其它“頂點(diǎn)”沒有和其祖先相通的回邊，則該“頂點(diǎn)”必為關(guān)節(jié)點(diǎn)。如何判斷節(jié)點(diǎn)滿足特征2？ahgcbfde關(guān)節(jié)點(diǎn)的特征abcdefgh編輯pptabcdefgh23456783311111設(shè)置visited[v]:頂點(diǎn)在DFS中的序號(hào)；設(shè)置low[v]:頂點(diǎn)v在DFS中所能訪問到的的節(jié)點(diǎn)最小序號(hào)(包括回邊)1low[v]＝Min{visited[v],low[w],visited[k]}w是頂點(diǎn)v在DFS樹上的子節(jié)點(diǎn)；k是頂點(diǎn)v在DFS樹上回聯(lián)的祖先節(jié)點(diǎn)；如何判斷節(jié)點(diǎn)滿足特征2？ahgcbfde編輯ppt如何判斷節(jié)點(diǎn)滿足特征2？條件：1)頂點(diǎn)v存在孩子節(jié)點(diǎn)w;2)visited[v]<=low[w];ahgcbfdeabcdefgh234567833111111編輯ppt第84

頁7.5有向無環(huán)圖——拓?fù)渑判蛴邢驘o環(huán)圖(DAG) 沒有回路的有向圖。含有公共子式的表達(dá)式

(a+b)*(e/f)-(a+b)-a+b*/efa+b-a+b*/ef編輯ppt第85

頁7.5有向無環(huán)圖——拓?fù)渑判騿栴}提出：學(xué)生選修課程問題 頂點(diǎn)——表示課程 有向弧——表示先決條件，若課程i

是

課程j

的先決條件，則圖中有弧<i,j>。

學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判颉?/p>

很顯然，不能出現(xiàn)回路。編輯ppt第86

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C12課程代號(hào)課程名稱先修課C1程序設(shè)計(jì)基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1,C2C4匯編語言C1C5語言的設(shè)計(jì)和分析C3,C4C6計(jì)算機(jī)原理C11C7編譯原理C3.C5C8操作系統(tǒng)C3,C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C1,C9,C10編輯ppt第87

頁7.5有向無環(huán)圖——拓?fù)渑判蛴邢驘o環(huán)圖(DAG)某工程可分為7個(gè)子工程，工程流程圖。V4V3V2V6V5V1V7編輯ppt第88

頁7.5有向無環(huán)圖——拓?fù)渑判蚨x

AOV網(wǎng)——用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)（ActivityOnVertexnetwork），簡稱AOV網(wǎng)。

若

<vi,vj>是圖中有向邊，則

vi

是

vj

的直接前驅(qū)；vj

是

vi

的直接后繼。 AOV網(wǎng)中不允許有回路，因?yàn)榛芈芬馕吨稠?xiàng)活動(dòng)以自己為先決條件。編輯ppt第89

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?/p>

把AOV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程。

檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)。編輯ppt第90

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判虻姆椒?/p>

在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之。

從圖中刪除該頂點(diǎn)和所有以它為尾的弧。

重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。編輯ppt第91

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(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ù)湫蛄胁皇俏ㄒ坏木庉媝pt第92

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1編輯ppt第93

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1編輯ppt第94

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2編輯ppt第95

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2編輯ppt第96

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3編輯ppt第97

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3編輯ppt第98

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4編輯ppt第99

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4編輯ppt第100

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5編輯ppt第101

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5編輯ppt第102

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7編輯ppt第103

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7編輯ppt第104

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽6C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9編輯ppt第105

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽6C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9編輯ppt第106

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10編輯ppt第107

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判駽6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8編輯ppt第108

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判蛩惴▽?shí)現(xiàn) 以鄰接表作存儲(chǔ)結(jié)構(gòu)。 把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧。 棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼

Vk，把

Vk的入度

減1；若

Vk的入度為

0

則進(jìn)棧。

重復(fù)上述操作直至?？諡橹?。

若棧空時(shí)輸出的頂點(diǎn)個(gè)數(shù)不是

n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤叀?（實(shí)現(xiàn)過程見教材P182）編輯ppt第109

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?2104例1234560122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^top16toptop編輯ppt第110

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416toptopp2編輯ppt第111

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416topp21編輯ppt第112

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416P=NULL21top1編輯ppt第113

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416P20top1編輯ppt第114

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210446P20top1編輯ppt第115

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210446P20top10編輯ppt第116

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210443P20top10編輯ppt第117

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210443P20top101P=NULL編輯ppt第118

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210443P10top1013編輯ppt第119

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210443P10top1003編輯ppt第120

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210442P10top1003P=NULL編輯ppt第121

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321044210top1003P=NULL2編輯ppt第122

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104400top1003P24編輯ppt第123

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104500top1003P24編輯ppt第124

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104500top1003P=NULL24編輯ppt第125

頁7.5有向無環(huán)圖——拓?fù)渑判蛲負(fù)渑判?111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：63210400top1003P=NULL245編輯ppt第126

頁7.5有向無環(huán)圖——關(guān)鍵路徑問題提出： 1）工程能否順序進(jìn)行，即工程流程是否“合理”

2）完成整項(xiàng)工程至少需要多少時(shí)間，哪些子工程是影響工程進(jìn)度的關(guān)鍵子工程？V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1頂點(diǎn)表示事件邊表示活動(dòng)事件Vj發(fā)生表示

ak已結(jié)束ak

VjVi事件Vi發(fā)生表示

ak可以開始

AOE網(wǎng)編輯ppt第127

頁7.5有向無環(huán)圖——關(guān)鍵路徑AOE網(wǎng)

AOE——用邊表示活動(dòng)的網(wǎng)。它是有一個(gè)帶權(quán)的有向無環(huán)圖。 頂點(diǎn)——表示事件，弧——表示活動(dòng)， 權(quán)值——活動(dòng)持續(xù)的時(shí)間。

路徑長度——路徑上各活動(dòng)持續(xù)時(shí)間之和

關(guān)鍵路徑——路徑長度最長的路徑叫關(guān)鍵路徑編輯ppt第128

頁7.5有向無環(huán)圖——關(guān)鍵路徑AOV網(wǎng)和AOE網(wǎng)的區(qū)別 都能用來表示工程中的各子工程的流程： 一個(gè)用頂點(diǎn)表示活動(dòng)， 一個(gè)用邊表示活動(dòng)， 但AOV網(wǎng)側(cè)重表示活動(dòng)的前后次序，AOE網(wǎng)除表示活動(dòng)先后次序，還表示了活動(dòng)的持續(xù)時(shí)間等。 因此可利用AOE網(wǎng)解決工程所需最短時(shí)間及哪些子工程拖延會(huì)影響整個(gè)工程按時(shí)完成等問題。編輯pptabcdefghk64521182446147“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加將使有向圖上的最長路徑的長度增加。整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑。源點(diǎn)匯點(diǎn)77.5有向無環(huán)圖——關(guān)鍵路徑編輯ppt如何求關(guān)鍵活動(dòng)？“活動(dòng)(弧)”的最早開始時(shí)間e(i)“活動(dòng)(弧)”的最遲開始時(shí)間l(i)關(guān)鍵活動(dòng)：e(i)＝l(i)“事件(頂點(diǎn))”的最早發(fā)生時(shí)間ve(j)“事件(頂點(diǎn))”的最遲發(fā)生時(shí)間vl(k)活動(dòng)(弧)發(fā)生時(shí)間的計(jì)算公式假設(shè)第i條弧為<j,k>，則對第i項(xiàng)活動(dòng)言e(i)=ve(j)；l(i)=vl(k)–dut(<j,k>)；jkiabce641161編輯ppt事件(頂點(diǎn))發(fā)生時(shí)間的計(jì)算公式最早開始時(shí)間：ve(源點(diǎn))=0；ve(k)=Max{ve(j)+dut(<j,k>)}最遲開始時(shí)間：vl(匯點(diǎn))=ve(匯點(diǎn))；vl(j)=Min{vl(k)–dut(<j,k>)}如何求關(guān)鍵活動(dòng)？abce641161jki編輯ppt13200000000064571157151418181818181818181818161486610807拓?fù)溆行蛐蛄?a-d-f-c-b-e-h-g-k如何求關(guān)鍵活動(dòng)？abcdefghk64521182447編輯ppt1330645771514181814161078660000645777151414160236688710e(i)=ve(j)；l(i)=vl(k)–dut(<j,k>)；編輯ppt134算法的