2-6圖

*圖比樹(shù)更復(fù)雜、更一般，樹(shù)是一種簡(jiǎn)單的圖。

*圖的應(yīng)用-一范圍非常廣，如語(yǔ)言學(xué)、邏輯學(xué)、數(shù)

學(xué)、物理、化學(xué)、計(jì)算機(jī)科學(xué)以及各種工程學(xué)科

領(lǐng)域。

*在圖中，結(jié)點(diǎn)之間的關(guān)系可以是任意的多對(duì)多的關(guān)

系。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

261畫(huà)的定義及基建術(shù)語(yǔ)

1.圖的定義無(wú)向圖

1)圖：由頂

G=(V,R),

其中V={V1,v2,...,vn},是頂點(diǎn)的非空有限集合;

R={<vi,Vj>},是頂點(diǎn)的有序?qū)Γ?/p>

或{(Vj,Vj)},是頂點(diǎn)的無(wú)序?qū)Α?/p>

2)無(wú)向圖：當(dāng)圖中頂點(diǎn)間的關(guān)系為無(wú)序?qū)Α?/p>

(V],V，二(vj,vj,稱為邊Eo

無(wú)向圖記作：G二(V,E),

例如上圖：G1=(V,E),V(G1)={1,2,3,4,5)

E(G1)={(1,2),(1,3),(1,4),(2,3),(3,5)}

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.6圖

261囹的定義及基建術(shù)語(yǔ)

3)有向圖：圖中頂點(diǎn)間的關(guān)系為有序?qū)?/p>

'<vi?Vj>稱為弧A,?------?

注意：<Vj,Vj>W〈Vj,V。，弧尾弧頭

有向圖記作：G二(V,A),

例如右圖：

G2=(V,A),

V(G2)={1,2,3,4,5,6)

A(G2)={<1,2>,<2,1>,<2,4>,<2,3>,<3,5>,<5,6>,<6,3>}

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.6圖

261囹的定義及基建術(shù)語(yǔ)

4）網(wǎng)：若圖中每一條邊附有反映該邊特征的數(shù)據(jù)，則

稱為網(wǎng)，與邊相關(guān)的數(shù)據(jù)稱為權(quán)。

邊上帶權(quán)的無(wú)向圖稱為無(wú)向網(wǎng)。

弧上帶權(quán)的有向圖稱為有向網(wǎng)。

有向網(wǎng)

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

261畫(huà)的定義及基中術(shù)語(yǔ)

2.圖的基本術(shù)語(yǔ)

1)子圖:兩個(gè)圖G和G',G=(V,E),G5=(V5,E5)

右'憶'=『和E'三E

則稱G，為G的子圖。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?6圖

2.6.1畫(huà)的定義及基本術(shù)語(yǔ)

2）度、入度和出度：

度：無(wú)向圖中，與某個(gè)頂點(diǎn)相連的邊的數(shù)目“

入度：有向圖中，以某個(gè)頂點(diǎn)為頭的弧的數(shù)目。

出度：以某個(gè)頂點(diǎn)為尾的弧的數(shù)目。

有向圖

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?6圖

2.6.1畫(huà)的定義及基本術(shù)語(yǔ)

例：有N個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)

多少？

2(N-1)

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

路徑：在無(wú)向圖中，從頂點(diǎn)Vp到Vq的路徑----

是頂點(diǎn)序列(Vp,Vj],V⑵…，Vjk，Vq),且(vp,Vj]),

(vn,vi2),(Vjk，Vp)均是E中的邊。

有向路徑：在有向圖中，由頂點(diǎn)的弧組成。

路徑長(zhǎng)度：路徑上邊或弧的數(shù)目。

網(wǎng)的路徑長(zhǎng)度--路徑上權(quán)值的和。

簡(jiǎn)單路徑：除第一個(gè)和最后一個(gè)頂點(diǎn)外，序列中其余

頂點(diǎn)各不相同的路徑。

簡(jiǎn)單回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的簡(jiǎn)單路徑。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.6.1畫(huà)的是G

4）連通圖和連通

連通圖（a）非連通圖（b）

在無(wú)向圖G中：

連通：若從頂點(diǎn)Vj到Vj存在路徑，則稱Vj和Vj是連通的。

連通圖：頂點(diǎn)集合V中任意兩個(gè)頂點(diǎn)Vj和Vj都連通，.

則稱G為連通圖。

連通分量：G中的極大連通子圖稱為該圖的連通分量。

如上圖，（a）為連通圖，（b）不是連通圖，但它有3個(gè)

連通分量：G］、G2>G3

注意：連通圖只有一個(gè)連通分量，即本身。

非連通圖有多個(gè)連通分量

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

261畫(huà)的定文及基中術(shù)語(yǔ)

5）強(qiáng)連通圖和強(qiáng)連通分量：（對(duì)于有向圖定義）

在有向圖G中：

連通：從頂點(diǎn)Vj到Vj有路徑，則稱從Vj到Vj是連通的。

強(qiáng)連通圖：任意兩個(gè)頂點(diǎn)Vi和Vj都連通，

則稱G為強(qiáng)連通圖。

強(qiáng)連通分量：G中的極大強(qiáng)連通子圖稱為該圖的

強(qiáng)連通分量。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

262圉的落儲(chǔ)秸構(gòu)

1.鄰接矩陣(表示頂點(diǎn)之間的關(guān)系)

有n個(gè)頂點(diǎn)的圖G二(V,E),可用nXn的矩陣來(lái)表示,

矩陣元素為：

I若(Vj,Vj)或〈Vj,Vj〉是E中的邊或弧

W]={-

I0反之

若G是網(wǎng)，則鄰接矩陣中每個(gè)元素定義為：

若(Vj,Vj)或＜Vj,Vj〉是E中的邊或弧

4比月=f-、

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

例:

有向圖無(wú)向圖有向網(wǎng)

r

1110、0270019210’080006400

0100270560110000310600

10010501000003000000

0000061000140032440000

19000070000018058

V0X1V0nJ3318

21110143300750043000

lo0001800>100006900

無(wú)向圖和無(wú)向網(wǎng)的鄰接矩陣為對(duì)稱矩陣。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

262圉的落儲(chǔ)秸構(gòu)

2.鄰接表

*鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),在鄰接表

中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，并將它

們的表頭指針用向量存儲(chǔ)（鄰接向量）。

*第i個(gè)單鏈表中的結(jié)點(diǎn)依附于頂點(diǎn)vi的邊（有

向圖為弧），故其結(jié)點(diǎn)數(shù)等于vi的度（有向圖為

出度）。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

2624的落儲(chǔ)秸構(gòu)

*鏈結(jié)點(diǎn)結(jié)構(gòu)：

表結(jié)點(diǎn)頭結(jié)點(diǎn)

adjvexdatanextarcvexdatafirarc

adjvex：鄰接域，存儲(chǔ)鄰接頂點(diǎn)

vexdata：數(shù)據(jù)域,存儲(chǔ)Vj

的序號(hào)；

信息;

data：數(shù)據(jù)域，存儲(chǔ)和邊或弧的

firarc：鏈域，指向表中

權(quán)值信息；

第一個(gè)結(jié)點(diǎn)。

nextarc：鏈域指示下一條邊或弧

公的結(jié)點(diǎn)

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2

1

2

1A

3A

4A

1A

519621A

3546

410A

310614A

633718A

211414—?533A

f

1280—?564A

2f431―?660A

3-?230A

4->232—?344A

5f170―?6180—?

6f175―?443A

7f569A

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?6圖

262圉的落儲(chǔ)秸構(gòu)

注意：'

條表頭結(jié)點(diǎn)有序，以向量存儲(chǔ)（鄰接向量）；

*無(wú)向圖的鄰接矩陣唯一，但其鄰接表不唯一

（次序與鄰接表建立時(shí)輸入次序有關(guān)）；

*對(duì)于無(wú)向圖，n個(gè)頂點(diǎn)，e條邊，有n個(gè)表頭

結(jié)點(diǎn)，2e個(gè)表結(jié)點(diǎn)，空間復(fù)雜度為O（n+e）；

*n個(gè)頂點(diǎn)的無(wú)向圖至多n（nT）/2條邊（完全

圖）。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算m

2-6圖

263囹的遍歷

從圖的某一頂點(diǎn)出發(fā)，沿某條路徑，依次對(duì)其

余頂點(diǎn)進(jìn)行訪問(wèn)，為了避免重復(fù)訪問(wèn)，設(shè)一個(gè)

輔助數(shù)組visited[n]：

felse,初值，未訪問(wèn)

visited[z]=

tureL_jUjI口J

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

2.6.3囹的遍歷

L深度優(yōu)先搜索(DFS)：樹(shù)的前序遍歷推廣

1)基本思想：從圖的某一個(gè)頂點(diǎn)V。出發(fā)進(jìn)行遍歷，

首先訪問(wèn)起始點(diǎn)V。，然后選擇V。的一個(gè)尚未訪問(wèn)過(guò)

的鄰接點(diǎn)W,從w出發(fā)繼續(xù)深度優(yōu)先搜索，即訪問(wèn)W

之后選擇W的一個(gè)尚未訪問(wèn)過(guò)的鄰接點(diǎn)作為出發(fā)點(diǎn)

繼續(xù)作深度優(yōu)先搜索，直到被訪問(wèn)的頂點(diǎn)其鄰接點(diǎn)

均被訪問(wèn)過(guò)為止，這時(shí)需要回溯到該頂點(diǎn)訪問(wèn)前的

頂點(diǎn)，繼續(xù)訪問(wèn)其尚未訪問(wèn)的鄰接點(diǎn)。這樣不斷回

溯，直到回溯到起始點(diǎn)V。，使所有和V。有路徑相通

的頂點(diǎn)都被訪問(wèn)到為止。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.6圖

2.6.3囹的遍歷

2)算法描述：以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)

DFS(A,n,v)

{

visit(v);〃訪問(wèn)頂點(diǎn)v

visited[v]<-TRUE;//置已訪問(wèn)標(biāo)志

for(j=1;j〈二n;j++)

if(A[v][j]==l&&!visited[j])

DFS(A,n,j);

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

例:

(a)(b)

圖(a)：vl,v2,v3,v5,v4v3,vl,v2,v4,v5

v2,vl,v3,v5,v4v4,vl,v2,v3,v5

圖(b)：vl,v2,v3,v6,v5,v7,v8,v4,v9

v9,v4,vl,v2,v3,v6,v5,v7,v8

v3,vl,v2,v4,v9,v6,v5,v7,v8

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

2.6.3囹的遍歷

2.廣度優(yōu)先搜索（BFS）（類似于樹(shù)的層次遍歷）

1）基本思想：訪問(wèn)了起始點(diǎn)V。之后，首先依次訪

問(wèn)V。的各個(gè)鄰接點(diǎn)，然后再依次訪問(wèn)這些頂點(diǎn)中未

被訪問(wèn)過(guò)的鄰接點(diǎn)，以此類推，直到所有被訪問(wèn)到

的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)過(guò)為止。

2）算法描述：為了搜索需要，應(yīng)設(shè)置一個(gè)循環(huán)隊(duì)

歹U,存放已被訪問(wèn)過(guò)的頂點(diǎn)。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算m

2-6圖

2.6.3囹的遍歷

BFS(AdjList,n,v)

(

訪問(wèn)頂點(diǎn)v;visited[v]=TRUE;

front=n-l;rear=O;CQ[rear]=v;

while(rear!=front){

front=(front+l)%n;v=CQ[front];

p=AdjList[v].firarc;

while(p!二NULL){

if(!visited[p->adjvex]){

訪問(wèn)p->adjvex;visited[p->adjvex]=TRUE;

rear-(rear+1)%n;CQ[rear]=p->adjvex;

)

p=p->nextarc;

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

263囹的遍歷

圖(b)：vl,v2,v3,v4,v6,v9,v5,v7,v8

v9,v4,vl,v2,v3,v6,v5,v7,v8

2-6圖

263囹的遍歷

例：

DFS：vl,v2,v3,v6,v9,v5,v8,v4,v7

BFS：vl,v2,v4,v5,v3,v7,v6,v8,v9

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.6圖

2.6.34的遍歷

3.復(fù)雜度分析

*空間復(fù)雜度：O(n)

*時(shí)間復(fù)雜度：

鄰接表：O(e),e為邊數(shù)

鄰接矩陣：。(標(biāo))

(0^第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算I<|A

2-6圖

264圉的應(yīng)用

1.單源最短路徑

1）問(wèn)題的提出

*背景：從一個(gè)給定的城市出發(fā)，能否到

達(dá)其它各城市？走哪條路花費(fèi)最少？

*數(shù)據(jù)結(jié)構(gòu)：用有向網(wǎng)表示，頂點(diǎn)表示城

市，弧代表路段，弧上的權(quán)值代表兩城市間的

距離或運(yùn)輸所需的代價(jià)。我們稱出發(fā)點(diǎn)為源點(diǎn),

其它點(diǎn)為終點(diǎn)。則問(wèn)題可描述為：從有向網(wǎng)的

源點(diǎn)到其它各終點(diǎn)有否路徑？最短路徑是什么?

最短路徑的長(zhǎng)度是多少？

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

*路徑的三種情況：

①?zèng)]有路徑；

②只有一條路徑，即為最短路徑;

③有多條路經(jīng)，存在最短的。

設(shè)頂點(diǎn)v2為源點(diǎn)，貝I」：

v2到v6：沒(méi)有路徑

v2到vl：只有一條，長(zhǎng)度35

v2到v4：有三條，最短為30

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

條定義：

給定有向圖網(wǎng)G=(V,A)和源點(diǎn)vO,求從vO到G

中其余各頂點(diǎn)的最短路徑。

例：以v6為源點(diǎn)，則各最短路

5)徑為：

v6->vl:21(v6->v2->v3->vl)

v6->v2:5

v6->v3:12(v6->v2->v3)

v6->v4:25(v6->v4)

v6->v5:無(wú)路徑

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

123456

06OO8cDOO

1807OOOO10

9OO0158OO

264圉的OO8120OOOO

OOOO480OO

2）算法月6245OO25OO0

路徑〈V0,Vk＞,從這些路徑中找出一條長(zhǎng)度最短

的路徑〈v0,u＞,然后對(duì)其余各條路徑進(jìn)行適當(dāng)

調(diào)整：若在圖中存在?。║,Vk〉,且〈U,Vk〉和

＜V0,U＞兩條弧上權(quán)之和小于弧〈V。,Vk＞的權(quán)，則

以路徑（V0,U,Vk＞代替〈V0,Vk＞。在調(diào)整后的各

條路徑中，再找長(zhǎng)度最短的路徑，以此類推。

3）過(guò)程：

二①初始化

設(shè)AS[n][n]為有向網(wǎng)的帶權(quán)鄰接矩陣，

AS[i][j]表示弧〈Vj,Vj＞上的權(quán)值，若〈Vj,V》

不存在,則為8

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

S:最短路徑的終點(diǎn)集合（初值為{v。}）

DIST[n]:各終點(diǎn)當(dāng)前找到的最短路徑的長(zhǎng)度

（初始值為DIST[i]=AS[vo][i]）

②選擇u,使得：

DIST[u]=mm{DIST[w]|w史工w￡/}

S=SU{〃}

其中憶為有向圖的頂點(diǎn)集。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?6圖

264畫(huà)的應(yīng)用

③對(duì)于所有不在S中的終點(diǎn)w,若:

DIST[u]+AS[u^]<DIST[w],則

DIST[w]=DIST[u]+AS[u][w]

④重復(fù)操作②、③共n-1次，可求得從V。到各終點(diǎn)的

最短路徑。

*幾個(gè)量的說(shuō)明：

S[n]：記錄了從源點(diǎn)出發(fā)的最短路徑的終點(diǎn)集合。

DIST[n]：記錄各終點(diǎn)當(dāng)前找到的最短路徑的長(zhǎng)度。

PATHM：PATH[i]表示從源點(diǎn)到頂點(diǎn)vi之間的最短路徑

N的前驅(qū)頂點(diǎn)，初始值為源點(diǎn)vO,若不存在，則為空?！?/p>

少第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算<

264圉的

例：

DIST[1:6]PATH[1:6]

S123456123456

{6}245OO25OO0_6666

{6,2}2351225OO026266

{6,2,3}2151225OO0_3626|6

{623,1}2151225OO036266

{6,2,334}2151225OO036266

則輸出PATH和Distant：6->l:6->2->3->l21;6->2:6->25;

6->3:6->2->312;6->4:6->425;

石、6->5:無(wú)路徑；6->6:6->60;

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

2.拓?fù)渑判颍ˋOV網(wǎng)，頂點(diǎn)表示活動(dòng)的有向網(wǎng)）

1）問(wèn)題的描述：

*用有向圖描述工程的進(jìn)行過(guò)程，子工程稱為活動(dòng)，

在圖中用頂點(diǎn)表示，兩頂點(diǎn)間的弧表示活動(dòng)間的優(yōu)先

關(guān)系，這種有向圖稱為作業(yè)活動(dòng)網(wǎng)或AOV網(wǎng)。

頂點(diǎn)i到頂點(diǎn)j有路徑，稱i是j的前驅(qū)，j是i的后繼；

若從i到j(luò)只有一條弧，則稱i是j的直接前驅(qū)，j是i的

直接后繼。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

引例：一個(gè)軟件專業(yè)學(xué)生學(xué)習(xí)課程

C1：程序設(shè)計(jì)先修無(wú)

C2：離散數(shù)學(xué)C1

C3：數(shù)據(jù)結(jié)構(gòu)ClC2

C4：匯編語(yǔ)言C1

C5：語(yǔ)言設(shè)計(jì)與分析C3C4

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

*拓?fù)溆行蛐蛄屑巴負(fù)渑判?/p>

死鎖-一在AOV網(wǎng)中不允許存在有向回路，否則

某項(xiàng)活動(dòng)的開(kāi)工將以自己工作的完成作為先決條

件，這種現(xiàn)象稱為死鎖。

拓?fù)溆行蛐蛄?-若有向圖中沒(méi)有回路出現(xiàn)，則

可構(gòu)造得到包含有向圖中全部頂點(diǎn)的序列，這種

序列稱為拓?fù)溆行蛐蛄小?/p>

拓?fù)渑判?一對(duì)AOV網(wǎng)構(gòu)造拓?fù)溆行蛐蛄械牟僮?/p>

稱為拓?fù)渑判颉?/p>

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2）拓?fù)渑判蚍椒ǎ?/p>

①在有向圖中選取一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)（入度為0）

輸出；

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

③Repeat①，②，直到全部頂點(diǎn)輸出。（答案不唯一）

（0^第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.6圖

264圉的應(yīng)用

可能的拓?fù)洌嚎赡艿耐負(fù)?

6->1->4->3->2->51->2->3->4->5

1->3->2->6->4->51->4->2->3->5

1->2->4->3->5

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

3）拓?fù)渑判虻泥徑颖砗玩湕?

頂入指

鄰接表,點(diǎn)度針

10

22A

31

AOV網(wǎng)42

53A

60

鏈棧：所有入度為零的頂點(diǎn)構(gòu)成一鏈棧

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

操作：①建立一個(gè)入度為0的頂點(diǎn)的棧；

②選取一個(gè)入度為0的頂點(diǎn)輸出；

③弧頭頂點(diǎn)的入度減1；

④Repeat①?③，直到全部頂點(diǎn)輸出

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2、0、1、3、4、50,2,1,3,4,5

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?6圖

264圉的應(yīng)用

3.關(guān)鍵路徑（以邊表示活動(dòng)的網(wǎng)：AOE）

1）問(wèn)題描述

*AOE網(wǎng)：一個(gè)帶權(quán)的有向無(wú)環(huán)圖。

頂點(diǎn)V/表示事件

Mai：表示活動(dòng)

權(quán)：表示活動(dòng)的持續(xù)時(shí)間。

源點(diǎn)：一個(gè)入度為零的點(diǎn)（工程起點(diǎn)，只有一個(gè)）

匯點(diǎn)：一個(gè)出度為零的點(diǎn)（工程結(jié)束，只有一個(gè)）

*研究的問(wèn)題

①完成整個(gè)工程需要多少時(shí)間？

、②哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算m

2-6圖

264圉的應(yīng)用

*關(guān)鍵路徑：完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最長(zhǎng)

路徑長(zhǎng)度，這條最長(zhǎng)的路徑稱作關(guān)鍵路徑。

施事件vj最早發(fā)生時(shí)間ve(j)：從ve(l)二0開(kāi)始向前遞推

ve(7)=Max{ve(z)+dut(<i〉j>)}

<i,j>eT,2<j<n

活動(dòng)aj由弧〈i,j>表示，其持續(xù)時(shí)間記為

dut?i,j?,T是所有以j為頭的弧的集合ai

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

*事件vj最遲發(fā)生時(shí)間vl(j)：從vl(n)=ve(n)

開(kāi)始向后遞推

vl(7)=Min{vl(左)一dut(<j,k>)}

<j,k>GS,1<j<n—1▲

其中s是所有以j為尾的弧的集合［T二/，

注意：以上兩個(gè)遞推公式的計(jì)算必須在拓?fù)溆行蚝湍?/p>

拓?fù)溆行虻那疤嵯逻M(jìn)行，即：ve(j)必須在Vj的所有前

驅(qū)的最早發(fā)生時(shí)間求得之后才能確定，而vl(j)必須在

:'Vj的所有后繼的最遲發(fā)生時(shí)間之后才能確定。

y第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

*活動(dòng)最早開(kāi)始時(shí)間e(i)：

e⑴二ve(j)

*活動(dòng)最遲開(kāi)始時(shí)間l(i)：活動(dòng)ai最遲必須開(kāi)

始進(jìn)行的時(shí)間。

1(i)=vl(k)-dut(<j,k?―?

*關(guān)鍵活動(dòng)：如果l(i)-e(i)=0,則稱乙為關(guān)鍵活

動(dòng)。關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

2)求解關(guān)鍵路徑過(guò)程：

①輸入e條弧，建立AOE網(wǎng)；

②從源點(diǎn)V1出發(fā)，令ve(l)=0,按拓?fù)溆行蚯笃溆喔?/p>

頂點(diǎn)的ve(j),若得到的拓?fù)溆行蛐蛄兄械捻旤c(diǎn)個(gè)數(shù)

小于網(wǎng)中頂點(diǎn)個(gè)數(shù)，說(shuō)明存在環(huán)，不能求關(guān)鍵路徑；

③從匯點(diǎn)％出發(fā)，令vl(n)=ve(n),按逆拓?fù)溆行蚯?/p>

其余各頂點(diǎn)的vl(j)；

④ve和vl值，求每條弧(每個(gè)活動(dòng))的e(i)和l(i),

找出滿足e(i)二1⑴的關(guān)鍵活動(dòng)，從而求得關(guān)鍵路徑。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2-6圖

264圉的應(yīng)用

'3)復(fù)雜度分析：

計(jì)算ve和vl的時(shí)間復(fù)雜度：0(n+e)

計(jì)算e和1的時(shí)間復(fù)雜度：0(e)

求關(guān)鍵路徑的總的時(shí)間復(fù)雜度：0(n+e)

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

例：AOE網(wǎng)采用鄰接矩陣存儲(chǔ)，其三元組表示為：

(1,2,3),(1,3,2),(2,4,2),(2,5,3),(3,4,4),(3,6,3),

(4,6,2),(5,6,1),求ve、vLe⑴、班)和關(guān)鍵路徑。

解：根據(jù)三元組表示，該AOE網(wǎng)為：

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

頂點(diǎn)vevl活動(dòng)e11-e

vl00al011

v234a2000

v322a3341

v466a4341

匯點(diǎn)v567a5220

v688a6253

a7660

a8671

得關(guān)鍵路徑：vl