操作系統(tǒng)-第七章

※教學(xué)內(nèi)容：圖的基本概念；圖的

結(jié)構(gòu)；圖的遍歷；最小生成樹；最短路徑；拓?fù)渑判蚝完P(guān)鍵路徑※

教學(xué)重點(diǎn)：圖的各種

結(jié)構(gòu);遍歷圖的遞歸和非遞歸算法；應(yīng)用圖的遍歷算法求各種簡單路徑問題，比如，最小生成樹﹑最短路徑﹑拓?fù)渑判颟p關(guān)鍵路徑等?！虒W(xué)難點(diǎn)：圖的遍歷算法，構(gòu)造最小生成樹的算法7.1圖的定義圖的

表示圖的遍歷最小生成樹兩點(diǎn)之間的最短路徑問題拓?fù)渑判蜿P(guān)鍵路徑第七章

圖7.1

圖的定義一、圖的結(jié)構(gòu)定義:圖是由一個頂點(diǎn)集V

和一個弧集VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu)G

=

(V

,

VR

)其中，VR＝{<v,w>|

v,w∈V

且P(v,w)}<v,w>表示從v

到w

的一條弧，并稱v

為弧尾，w

為弧頭。謂詞

P(v,w)定義了弧<v,w>的意義或信息。ABECD例如:G1

=

(V1,

VR1)有向圖由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。其中V

={A,

B,

C,

D,

E}1VR1={<A,B>,

<A,E>,<B,C>,

<C,D>,<D,B>,

<D,A>,<E,C>

}無向圖:若<v,

w>VR

必有<w,

v>VR,即VR是對稱的，則以無序?qū)?v,w)代替這兩個有序?qū)Γ硎卷旤c(diǎn)v

和頂點(diǎn)w之間的一條邊。由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向圖。例如:G2=(V2,VR2)B

CDFEV2={A,

B,

C,

D,

E,

F}VR2={(

A,B

),

(

A,E

),(

B,E

),

(

C,D

),

A(

D,F

),

(

B,F

),(

C,F

)

}名詞和術(shù)語網(wǎng)、子圖完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹、生成森林ABECF1597211132網(wǎng):有時圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)。這些權(quán)可以表示從一個頂點(diǎn)到另一個頂點(diǎn)的距離或耗費(fèi)?；』蜻厧?quán)的圖分別稱為網(wǎng)(有向網(wǎng)、無向網(wǎng))。子圖:假設(shè)有兩個圖G=(V,{VR})ABECF圖GAEFBBC圖G‘和

G=(V,{VR})如果VV,VRVR，則稱G

為G

的子圖。完全圖、稀疏圖和稠密圖：假設(shè)圖中有n

個頂點(diǎn)，e

條邊，則:含有e=n(n-1)/2

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

條弧的有向圖稱作有向完全圖；若邊或弧的個數(shù)e<nlogn，則稱作稀疏圖，否則稱作稠密圖。鄰接點(diǎn)和度假若頂點(diǎn)v和頂點(diǎn)w

之間存在一條邊，則稱頂點(diǎn)v

和w

互為鄰接點(diǎn)；邊(v,w)和頂點(diǎn)v和w相關(guān)聯(lián)；和頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目定義為頂點(diǎn)v的度。例如:TD(B)

=3TD(A)

=2ADFEB

C入度和出度對有向圖來說，頂點(diǎn)v的出度:頂點(diǎn)v的入度:以頂點(diǎn)v為弧尾的弧的數(shù)目；以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)AECF例如:BID(B)

=2TD(B)

=3OD(B)

=1路徑設(shè)圖G=(V,{VR})中的一個頂點(diǎn)序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR

1≤j≤m,則稱從頂點(diǎn)u到頂點(diǎn)w之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長度。E如:長度為3的路徑{A,B,C,F}

ABC

F簡單路徑:序列中頂

點(diǎn)不重復(fù)出現(xiàn)的路徑?；芈?序列中第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑。若圖G中任意兩個頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖；否則，稱之為非連通圖。BACDEF連通圖BACDFE非連通圖BACDFECDF若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BAE對有向圖來說，若任意兩個頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。ABEC

F強(qiáng)連通圖ABECFBECF否則，其各個強(qiáng)連通子圖稱作它的強(qiáng)連通分量。ABCFAE假設(shè)

通圖有

n

個頂點(diǎn)和

e

條邊，其中n-1

條邊和

n

個頂點(diǎn)構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。BACDC

BD

AE

FEF連通圖連通圖的生成樹BA

CFB對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。ACDFE

DE一個有向圖及其生成森林二、抽象數(shù)據(jù)類型圖的定義ADT

Graph{數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R:R={VR}VR={<v,w>|

v,w∈v且P(v,w)，<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息?；静僮鱌:}ADT

Graph結(jié)構(gòu)的建立和銷毀對頂點(diǎn)的

操作??或刪除頂點(diǎn)和刪除弧對鄰接點(diǎn)的操作遍歷基本操作CreateGraph(&G,

V,

VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷毀圖結(jié)構(gòu)的建立和銷毀對頂點(diǎn)的

操作LocateVex(G,

u);//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在//圖中“位臵”；否則返回其它信息。GetVex(G,

v);//返回

v

的值。PutVex(&G,v,

value);//對v

賦值value。對鄰接點(diǎn)的操作AdjVex(G,

v);//返回v

的“第一個鄰接點(diǎn)”。若該頂點(diǎn)NextA//d在jVGex(沒中G有,v鄰,w接)點(diǎn);，則返回“空”。//返回v

的(相對于w

的)―下一個鄰接點(diǎn)”。//若w是v的最后一個鄰接點(diǎn)，則返回“空”。或刪除頂點(diǎn)InsertVex(&G,

v);//在圖G中增添新頂點(diǎn)v。DeleteVex(&G,

v);//刪除G中頂點(diǎn)v及其相關(guān)的弧。和刪除弧InsertArc(&G,

v,

w);//在G中增添弧<v,w>，若G是無向的，//則還增添對稱弧<w,v>。DeleteArc(&G,

v,

w);//在G中刪除弧<v,w>，若G是無向的，//則還刪除對稱弧<w,v>。遍

歷DFSTraverse(G,

v,

Visit());//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對每//個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,

v,

Visit());//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對每//個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。7.2

圖的

表示一、圖的數(shù)組(鄰接矩陣)

表示二、圖的鄰接表

表示三、有向圖的

鏈表

表示一、圖的數(shù)組(鄰接矩陣)表示鄰接矩陣:表示頂點(diǎn)間相鄰關(guān)系的矩陣，用一個二維數(shù)組來表示集合VR。此二維數(shù)組稱為鄰接矩陣。若G是一個具有n個頂點(diǎn)的圖，其鄰接矩陣是一個n階方陣。(1)無向圖的鄰接矩陣定義設(shè)G=(V,VR)是有n(n≥1)個頂點(diǎn)的無向圖，則G的鄰接矩陣是一個n×n

矩陣:A[i,j]=A[j,i]=1

(vi,vj)VR0

(vi,vj)VRV1V2V3V4V510100011000

1

0

1

01

0

1

0

10

1

0

1

1特點(diǎn):無向圖的鄰接矩陣為對稱方陣；鄰接矩陣第i行（或第i列）的元

和則是頂點(diǎn)Vi的度。定義設(shè)G=(V,VR)是有n(n≥1)個頂點(diǎn)的有向圖，G的鄰接矩陣是具有如下性質(zhì)的n×n方陣:A[i,j]=(2)有向圖的鄰接矩陣1

當(dāng)<vi,vj>

E0

當(dāng)<vi,vj>

E有向圖的鄰接矩陣為非對稱矩陣；和為頂點(diǎn)Vi的鄰接矩陣第i行的元出鄰度接；矩陣第j列的元的入度。和為頂點(diǎn)VjV1V2V3V40

1

1

00

0

0

00

0

0

11

0

0

0定義設(shè)G=(V,VR)是有n(n≥1)個頂點(diǎn)的有向網(wǎng)，G的鄰接矩陣是具有如下性質(zhì)的n×n方陣:A[i,j]=wij當(dāng)<vi,vj>

E∞

當(dāng)<vi,vj>

E(3)

網(wǎng)的鄰接矩陣V1V3V6V5V4V23548715695∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞8

∞

∞ ∞

∞

9∞

∞

5

∞

∞

6∞

∞

∞

5

∞

∞3

∞

∞

∞

1

∞網(wǎng)N網(wǎng)N的鄰接矩陣#define

INFINITY

INF_MAX//最大值∞#define

MAX_VERTEX_NUM

20//最大頂點(diǎn)個數(shù)Typedef

enum

{DG,DN,UDG,UDN}GraphKind;//{有向圖，有向網(wǎng)，無向圖，無向網(wǎng)}圖的鄰接矩陣表示：typedef

struct

ArcCell

{//弧的定義VRType

adj;

//VRType是頂點(diǎn)關(guān)系類型，//對無權(quán)圖，用1或0表示相鄰否，//對帶權(quán)網(wǎng)，則為權(quán)值類型InfoType

*info;//該弧相關(guān)信息的指針}

ArcCell,

AdjMatrix

[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef

struct{//圖的定義VertexType

vexs[MAX_VERTEX_NUM];//頂點(diǎn)向量AdjMatrix

arcs;int

vexnum,

um;GraphKind

kind;}

MGraph;//鄰接矩陣//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)//圖的種類標(biāo)志優(yōu)點(diǎn)：借助于鄰接矩陣，容易判定任意兩個頂點(diǎn)之間是否有邊（或?。┫噙B，并容易求得各個頂點(diǎn)的度。對于無向圖，頂點(diǎn)Vi

的度是鄰接矩陣第i

行（或第i列）的元和。對于有向圖，第i

行的元和為頂點(diǎn)Vi

的出度；第j

列的元和為頂點(diǎn)Vj的入度。缺點(diǎn)：占用的單元個數(shù)只與圖中頂點(diǎn)個數(shù)有關(guān)，而與邊的數(shù)目無關(guān)。adivexinfonextarc鄰接表是圖的一種鏈?zhǔn)酱尜A結(jié)構(gòu)。在鄰接表中，對圖的每個頂點(diǎn)建立一個單鏈表，第i

個單鏈表中的結(jié)點(diǎn)表示頂點(diǎn)i

的所有鄰接頂點(diǎn)。鏈表中每個結(jié)點(diǎn)由三個域組成：表結(jié)點(diǎn)–adivex

—頂點(diǎn)vi的鄰接點(diǎn)–info

—存貯與邊和弧相關(guān)的權(quán)值–nextarc—指向vi下一個鄰接點(diǎn)的指針二、圖的鄰接表

表示在每個鏈表上附設(shè)一個表頭結(jié)點(diǎn)，由兩個域組成：datafristarc–data

—存貯與頂點(diǎn)vi有關(guān)信息的數(shù)據(jù)；–fristarc—指向vi的第一個鄰接點(diǎn)的指針。表頭結(jié)點(diǎn)通常以順序結(jié)構(gòu)的形式

，以便隨機(jī)

任一頂點(diǎn)的鄰接點(diǎn)鏈表。頭結(jié)點(diǎn)V1V2V3V4V5301234在無向圖的鄰接表中，頂點(diǎn)Vi的度恰為第i個鏈表中的表結(jié)點(diǎn)數(shù).V1V2V4V3V5無向圖的鄰接表21

30V1V2V3V40123有向圖的鄰接表中，第i個鏈表中的表結(jié)點(diǎn)個數(shù)是頂點(diǎn)Vi的出度。在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。有向圖的鄰接表V1V2V3V4V1V2V3V40

2

3

0

0123有向圖的逆鄰接表在有向圖的逆鄰接表中，對每個頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。V1

V2V3V4有向圖的逆鄰接表中，第i個鏈表中的表結(jié)點(diǎn)個數(shù)是頂點(diǎn)Vi的入度。typedef

structint

adjvex;ode

{//該弧所指向的頂點(diǎn)的位臵structode

*nextarc;//指向下一條弧的指針I(yè)nfoType

*info;ode;}//該弧相關(guān)信息的指針adjvexnextarcinfo弧的結(jié)點(diǎn)結(jié)構(gòu)(表結(jié)點(diǎn))圖的鄰接表

表示：typedef

struct

VNode

{//頂點(diǎn)信息VertexType

data;ode

*arc;//指向第一條依附該頂點(diǎn)的弧}

VNode,

AdjList[MAX_VERTEX_NUM];dataarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)(頭結(jié)點(diǎn))typedef

struct

{AdjList

vertices;//表頭結(jié)點(diǎn)向量int

vexnum,

um;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)//圖的種類標(biāo)志int

kind;}

ALGraph;圖的結(jié)構(gòu)定義優(yōu)點(diǎn)：當(dāng)邊數(shù)<<頂點(diǎn)個數(shù)的平方(m<<n2)時，節(jié)省

空間；運(yùn)算方便，容易找到任意頂點(diǎn)的第一個鄰接點(diǎn)和下一個鄰接點(diǎn)。缺點(diǎn)：要判定任意兩個頂點(diǎn)之間是否有邊或弧相連時，則需掃描第i個或第j個鏈表，不及鄰接矩陣方便。三、有向圖的

鏈表

表示鏈表是圖的另一種鏈?zhǔn)酱尜A結(jié)構(gòu)，可以看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。在十字鏈表中，對應(yīng)于有向圖的每個頂點(diǎn)和每一條弧都有一個結(jié)點(diǎn)。//弧的結(jié)構(gòu)表示typedef

struct

ArcBox

{int

tailvex,

headvex;InfoType

*info;struct

ArcBox

*tlink,

*hlink;}

ArcBox;弧的結(jié)點(diǎn)結(jié)構(gòu)(弧結(jié)點(diǎn))弧尾頂點(diǎn)位臵弧頭頂點(diǎn)位臵弧的相關(guān)信息指向下一個有相同弧尾的結(jié)點(diǎn)指向下一個有相同弧頭的結(jié)點(diǎn)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)(頂點(diǎn)結(jié)點(diǎn))頂點(diǎn)信息數(shù)據(jù)指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧typedef

struct

VexNode

{//頂點(diǎn)的結(jié)構(gòu)表示VertexType

data;ArcBox

*

in,*

out;}

VexNode;typedef

struct

{VexNode

xlist[MAX_VERTEX_NUM];//頂點(diǎn)結(jié)點(diǎn)(表頭向量)int

vexnum,um;//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}

OLGraph;有向圖的結(jié)構(gòu)表示(鏈表)V1V2V3V4V1V2V3V42030323優(yōu)點(diǎn)：容易找到以Vi為尾的弧，也容易找到以Vi

為頭的弧，因而容易求得頂點(diǎn)的出度和入度。7.3

圖的遍歷從圖中某個頂點(diǎn)出發(fā)，訪遍圖中其余頂點(diǎn)，并且使圖中的每個頂點(diǎn)僅被訪問一次的過程，叫做圖的遍歷。V1V2V3V4V5V6

V7V8圖的遍歷要比樹的遍歷復(fù)雜得多。因?yàn)閳D中任一頂點(diǎn)都可能和其余的頂點(diǎn)相鄰接。所以，在

了某個頂點(diǎn)之后，可能沿著某條搜索路徑又回到該頂點(diǎn)上。為了避免同一頂點(diǎn)被多次記下每個已為此，，在遍歷圖的過程中，必須過的頂點(diǎn)?？稍O(shè)一個輔助數(shù)組visited[0..n-1]，它的初始值臵為“假”或者“0‖，一旦“真”或者被了頂點(diǎn)Vi，便臵visited[i]為時的次序號。通常有兩條遍歷圖的路徑：深度優(yōu)先搜索（縱向優(yōu)先搜索）廣度優(yōu)先搜索（橫向優(yōu)先搜索）連通圖的深度優(yōu)先搜索遍歷從圖中某個頂點(diǎn)V0出發(fā)，此頂點(diǎn)然后依次從V0的各個未被的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和

V0有路徑相通的頂點(diǎn)都被到。一、深度優(yōu)先搜索遍歷圖Vw1SG1SG2SG3W1、W2和W3

均為V

的鄰接點(diǎn)，SG1、SG2

和頂點(diǎn)V;for(W1、W2、W3

)若該鄰接點(diǎn)W未被，則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。w3

SG3

分別為含頂點(diǎn)W1、W2和W3

的子圖。w2V1V2V3V4V5V6

V7V8深度優(yōu)先搜索結(jié)果：V1

→

V2→

V4→

V8

→

V5→

V3→

V6

→

V7從上頁的圖解可見:深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；如何判別V的鄰接點(diǎn)是否被

？解決的辦法是：為每個頂點(diǎn)設(shè)立一個

“標(biāo)志visited[w]”。void

DFS(Graph

G,

int

v)

{//從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖GVisitFunc(v);//

第v

個結(jié)點(diǎn)visited[v]

=

TRUE;for(w=

AdjVex(G,

v);//調(diào)用基本操作w!=0;

w=NextAdjVex(G,v,w))if

(!visited[w]) DFS(G,

w);//

對v的尚未

的鄰接頂點(diǎn)w,遞歸調(diào)用DFS}

//

DFS首先將圖中每個頂點(diǎn)的

標(biāo)志設(shè)為FALSE,之后，從圖中某個頂點(diǎn)v0出發(fā)，此頂點(diǎn)，然后依次從v0的未被

的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v0有路徑相通的頂點(diǎn)都被到為止；若此時圖中尚有頂點(diǎn)未被，則另選圖中一個未曾的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被到為止。非連通圖的深度優(yōu)先搜索遍歷0(a)1(b)2(c)3(d)4(e)5(f)6(g)7(h)8(k)TTTTTTTTTachdkfebg標(biāo)志:次序:例如:achkfedbgvoid

DFSTraverse(Graph

G,Status

(*Visit)(int

v))

{//對圖G

作深度優(yōu)先遍歷。VisitFunc

=

Visit;//使用全局變量，使DFS不必設(shè)函數(shù)指針參數(shù)for

(v=0;

v<G.vexnum;

++v)visited[v]

=

FALSE;//

標(biāo)志數(shù)組初始化for

(v=0;

v<G.vexnum;

++v)if

(!visited[v]) DFS(G,

v);//對尚未的頂點(diǎn)調(diào)用DFS}二、廣度優(yōu)先搜索遍歷圖從圖中的某個頂點(diǎn)V0出發(fā)，并在

此頂點(diǎn)之后依次

V0的所有未被

過的鄰接點(diǎn)，之后按這些頂點(diǎn)被 的先后次序依次

它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的

頂點(diǎn)都被

到。若此時圖中尚有頂點(diǎn)未被，則另選圖中一個未曾被

的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被到為止。對連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。其中，V->w1,V->w2,V->w8的路徑長度為1；V->w

,

V->w

,

V->w7

3

5的路徑長度為2；V->w6,

V->w4的路徑長度為3。w3w5w4w1Vw2w7w6w8廣度優(yōu)先搜索結(jié)果：V->w1->w2->w8

->w7->w3->w5

-

>w6->w4V1V2V3V4V5V6

V7V8廣度優(yōu)先搜索結(jié)果：V1

→

V2

→

V3

→

V4

→

V5→

V6

→

V7

→

V8廣度優(yōu)先搜索圖的過程是以v為起始點(diǎn)，由近至遠(yuǎn)，依次

和v有路徑相通且路徑長度為1，2，……的頂點(diǎn)。類似于樹的按層次遍歷過程。和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個

標(biāo)志數(shù)組。并且，為了順次路徑長度為2、3、…的頂點(diǎn)，需附設(shè)隊(duì)列以存儲以被

的路徑長度為1，2，…的頂點(diǎn)。void

BFSTraverse(Graph

G,Status

(*Visit)(int

v))

//對圖G

作廣度優(yōu)先遍歷{for

(v=0;

v<G.vexnum;

++v)visited[v]

=

FALSE;InitQueue(Q);//

初始化

標(biāo)志//臵空的輔助隊(duì)列Qfor

(

v=0;

v<G.vexnum;

++v

)if

(

!visited[v])

{……}}

//

BFSTraverse//v

尚未visited[v]

=

TRUE;

Visit(v);EnQueue(Q,

v);//

v//v入隊(duì)列while

(!QueueEmpty(Q))

{//循環(huán)結(jié)束時整個連通子圖DeQueue(Q,

u);//隊(duì)頭元素出隊(duì)并臵為ufor(w=AdjVex(G,

u);

w!=0;w=NextAdjVex(G,u,w))if

(

!

visited[w])

{visited[w]=TRUE;

Visit(w);EnQueue(Q,

w);}

//

if}

//

while//

的頂點(diǎn)w入隊(duì)列三、遍歷應(yīng)用舉例求一條從頂點(diǎn)i

到頂點(diǎn)s

的簡單路徑求兩個頂點(diǎn)之間的一條路徑長度最短的路徑1.

求一條從頂點(diǎn)

i

到頂點(diǎn)

s

的簡單路徑abcdeh

kfg例如:求從頂點(diǎn)

b

到頂點(diǎn)k

的一條簡單路徑。從頂點(diǎn)b

出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。假設(shè)找到的第一個鄰接點(diǎn)是c，則得到的結(jié)點(diǎn)序列為:b

c

h

d

a

e

k

f

g，假設(shè)找到的第一個鄰接點(diǎn)是a，則得到的結(jié)點(diǎn)序列為:

b

a

d

h

c

e

k

f

g。結(jié)論:從頂點(diǎn)i

到頂點(diǎn)s

,若存在路徑，則從頂點(diǎn)i

出發(fā)進(jìn)行深度優(yōu)先搜索，必能搜索到頂點(diǎn)s

。遍歷過程中搜索到的頂點(diǎn)不一定是路徑上的頂點(diǎn)。由它出發(fā)進(jìn)行的深度優(yōu)先遍歷已經(jīng)完成的頂點(diǎn)不是路徑上的頂點(diǎn)。void

DFSearch(

int

v,

int

s,

char

*PATH)

{//從第v個頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G，求得一條從v到s的簡單路徑，并記錄在PATH中visited[v]

=

TRUE;Append(PATH,

getVertex(v));//

第v

個頂點(diǎn)//第v個頂點(diǎn)加入路徑for

(w=AdjVex(v); w!=0

&&

!found;w=NextAdjVex(v,w)

)if

(w=s)

{

found

=

TRUE;

Append(PATH,

w);

}else

if

(!visited[w])

DFSearch(w,

s,

PATH);if

(!found) Delete(PATH);//沒有到S的路徑，刪除}2.

求兩個頂點(diǎn)之間的一條路徑長度最短的路徑若兩個頂點(diǎn)之間存在多條路徑，則其中必有一條路徑長度最短的路徑。如何求得這條路徑?（這兒只考慮兩頂點(diǎn)之間所含邊的數(shù)目最少）abchdekfg因此，求路徑長度最短的路徑可以基于廣度優(yōu)先搜索遍歷進(jìn)行。深度優(yōu)先搜索

頂點(diǎn)的次序取決于圖的結(jié)構(gòu)，而廣度優(yōu)先搜索頂點(diǎn)的次序是按“路徑長度”漸增的次序。例如:求下圖中頂點(diǎn)3

至頂點(diǎn)5

的一條最短路徑。假設(shè)使用鏈隊(duì)列，需要修改鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)及其入隊(duì)列和出隊(duì)列的算法3275

Q.front

Q.rear將鏈隊(duì)列的結(jié)點(diǎn)改為“雙鏈”結(jié)點(diǎn)。即結(jié)點(diǎn)中包含next

和prior兩個指針；修改入隊(duì)列的操作。新的隊(duì)尾結(jié)點(diǎn)時，令其prior域的指針指向剛剛出隊(duì)列的結(jié)點(diǎn)，即當(dāng)前的隊(duì)頭指針?biāo)附Y(jié)點(diǎn)；修改出隊(duì)列的操作。出隊(duì)列時，僅移動隊(duì)頭指針，而不將隊(duì)頭結(jié)點(diǎn)從鏈表中刪除。typedef

DuLinkList

QueuePtr;void

InitQueue(LinkQueue&

Q)

{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));Q.front->next

=

Q.rear->next

=

NULL}void

EnQueue(

LinkQueue&

Q,

QelemType

e

)

{p

=

(QueuePtr)

malloc

(sizeof(QNode));p->data

=

e;

p->next

=

NULL;p->prior

=

Q.frontQ.rear->next

=

p; Q.rear

=

p;}void

DeQueue(

LinkQueue&

Q,

QelemType&

e

)

{Q.front

=

Q.front->next; e

=

Q.front->data}7.4

圖的連通性和生成樹1、連通圖V1V2V3從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，V4便可遍歷完圖中所有頂點(diǎn)，這個圖就是連通圖。V5V6

V7V82、圖的生成樹設(shè)G=(V,E)是個連通圖，而E(G)為連通

圖中所有邊的集合，若從圖中任一頂點(diǎn)開始作一次搜索過程，則將E(G)分成兩個集合：

T(G)和B(G)。

T(G)是遍歷圖時走過的邊的

集合，

B(G)是剩余邊的集合，

T(G)和圖中

所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通

，稱為圖G的生成樹。圖的生成樹不唯一，從不同結(jié)點(diǎn)出發(fā)進(jìn)行搜索，可以得到不同的生成樹。深度優(yōu)先生成樹：由深度優(yōu)先搜索得到的生成樹。廣度優(yōu)先生成樹：由廣度優(yōu)先搜索得到的生成樹。1234

5

6

78無向圖深度優(yōu)先生成樹廣度優(yōu)先生成樹1234

5

6

781234

5

6

783、最小代價生成樹任何具有n個頂點(diǎn)的連通圖，至少有n-1條邊，而且所有具有n-1條邊的連通圖都是樹。若在連通圖的各條邊上賦以權(quán)值即網(wǎng)絡(luò)表示相應(yīng)的代價，那么，則從連通圖中選擇一棵總代價最小的樹，即為最小代價生成樹。假設(shè)要在n

個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n

個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個通訊網(wǎng)？4、最小代價生成樹的應(yīng)用問題的提出：在每兩個城市之間都可以設(shè)臵一條線路，相應(yīng)地都要付出一定的經(jīng)濟(jì)代價。n個城市

之間，最多可能設(shè)臵

n(n-1)/2

條線路，那么，如何在這些可能的線路中選擇

n-1

條，以使5總的耗費(fèi)最少呢？66

36可以用連通網(wǎng)來表示n個城市以及n

個城市之間可能設(shè)臵的通信線路，其中，網(wǎng)的頂點(diǎn)表示城市，邊表示兩城市之間的線路，賦予邊的權(quán)值表示相應(yīng)的代價。對于n個頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個通訊網(wǎng)?，F(xiàn)在，

要選擇這樣一棵生成樹，也就是總的耗費(fèi)最少。構(gòu)造網(wǎng)的一棵最小生成樹，即：在e

條帶權(quán)的邊中選取n-1

條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法一： 姆

(Prim)

法算法二：克魯斯卡爾(Kruskal)法基本思想：按權(quán)值非遞減次序構(gòu)造最小代價生成樹。該問題等價于：取圖中任意一個頂點(diǎn)v

作為生成樹的根，之后往生成樹上添加新的頂點(diǎn)w。在添加的頂點(diǎn)w和已經(jīng)在生成樹上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v

和w

之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有n個頂點(diǎn)為止。（1）

姆算法的基本思想例如:191827ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:在生成樹的構(gòu)造過程中，圖中n

個頂點(diǎn)分屬兩個集合：已落在生成樹上的頂點(diǎn)集U

和尚未落在生成樹上的頂點(diǎn)集V-U

，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。U

V-U設(shè)臵一個輔助數(shù)組，對當(dāng)前V－U集中的每個頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價最小的邊：struct

{VertexType

adjvex;

//U集中的頂點(diǎn)序號VRType

lowcost;//邊的權(quán)值}

closedge

[MAX_VERTEX_NUM];56636195ec3b7da18gclosedge0(a)1(b)2(c)3(d)4(e)5(f)6(g)AdjvexcdeadeLowcost538142116例如:fabdegf51416821c3void

MiniSpanTree_P(MGraph

G,

VertexType

u)

{//用 姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹k

=

LocateVex

(

G,

u

);for

(

j=0;

j<G.vexnum;

++j

)if

(j!=k)}//輔助數(shù)組初始化closedge[j]

=

{

u,

G.arcs[k][j].adj

};//

{adjvex,

lowcost}closedge[k].lowcost

=

0;//初始，U＝{u}for

(i=1;

i<G.vexnum;

++i)

{//選擇其余N-1個頂點(diǎn)……繼續(xù)向生成樹上添加頂點(diǎn);}k=minimum(closedge);//求出加入生成樹的下一個頂點(diǎn)(k)//此時closedge[k].lowcost=//MIN{closedge[vi

].lowcost|closedge[vi].lowcost>0,

Vi∈V-U}printf(closedge[k].adjvex,

G.vexs[k]);//輸出生成樹上一條邊的兩個頂點(diǎn)closedge[k].lowcost

=

0;//第k頂點(diǎn)并入U集for

(j=0;

j<G.vexnum;

++j)//修改其它頂點(diǎn)的最小邊if

(G.arcs[k][j].adj

<

closedge[j].lowcost)//新頂點(diǎn)并入U后重新選擇最小邊closedge[j]

=

{

G.vexs[k],

G.arcs[k][j].adj

};1951627821ec314

12

b7da18gclosedge0(a)1(b)2(c)3(d)4(e)5(f)6(g)AdjvexcdeadeLowcost000002116fa

b

c

d

e

f

ga

∞

19

∞ ∞

14

∞

18b

19

∞

5

7

12

∞

∞c

∞

5

∞

3

∞

∞

∞d

∞

7

3

∞

8

21

∞e

14

12

∞

8

∞ ∞

16f

∞

∞

∞ 21

∞

∞

27g

18

∞

∞ ∞

16

27

∞考慮問題的出發(fā)點(diǎn):為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。具體做法:先構(gòu)造一個只含

n

個頂點(diǎn)的子圖

SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG

上加上這條邊，如此重復(fù)，直至加上n-1

條邊為止。（2）克魯斯卡爾算法的基本思想27edcgf148531621例如:71218a

19

babdegf51416821c3算法描述:構(gòu)造非連通圖ST=(

V,{});//v表示頂點(diǎn)的集合，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++;}姆算法

克魯斯卡爾算法時間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍（3）比較兩種算法7.5

兩點(diǎn)之間的最短路徑問題求從某個源點(diǎn)到其余各點(diǎn)的最短路徑每一對頂點(diǎn)之間的最短路徑1、從某個源點(diǎn)到其余各點(diǎn)的最短路徑V0V1V251010V5305060V420V3100始點(diǎn) 終點(diǎn) 最短路徑 路徑長度V0

V1V2V3V4V5帶權(quán)有向圖中從V0到其余各頂點(diǎn)之間的最短路徑：(V

,V

)0

4(V0,V4,V3,V5)無(V0,

V2)

10(V0,V4,V3)

503060如何求從源點(diǎn)到其余各點(diǎn)的最短路徑？算法的基本思想:按路徑長度遞增的次序產(chǎn)生最短路徑源點(diǎn)v1V3…vn其中，從源點(diǎn)到頂點(diǎn)v1的最短路徑是所有最短路徑中長度最短者。下一條最短路徑呢？再下一條最短路徑呢？v2路徑長度最短的最短路徑的特點(diǎn)：在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小，不妨設(shè)(V0,Vi)。下一條路徑長度次短的最短路徑的特點(diǎn)：它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)，不妨設(shè)(V0,Vj)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)vi，再到達(dá)該頂點(diǎn)(由兩條弧組成)(V0,Vi

,Vj)。V0V1V2V351010V5305060V420100再下一條路徑長度次短的最短路徑的特點(diǎn):它可能有三種情況：或者是直接其余最短路徑的特點(diǎn)：它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。從源點(diǎn)到該點(diǎn)(只含一條弧)，不妨設(shè)0

k

i(V,V

)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v

，再到達(dá)該頂點(diǎn)(由兩條弧組成)(V0,Vi

,Vk)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)vj，再到達(dá)該頂點(diǎn)(V0,Vj,Vk)。V5V0V1V2V351010305060V420100一般情況下，假設(shè)S為已求得最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為x）或者是弧(v,x)，或者是中間只經(jīng)過S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)x的路徑。反證法來證明：假設(shè)此路徑上有一個頂點(diǎn)不在S中，則說明存在一條終點(diǎn)不在S而長度比此路徑短的路徑。但是，這是不可能的。因?yàn)?/p>

是按路徑長度遞增的次序來產(chǎn)生各最短路徑的，故長度比此路徑短的所有路徑均已產(chǎn)生，它們的終點(diǎn)必定在S中，即假設(shè)不成立。求最短路徑的迪杰斯特拉算法：設(shè)臵輔助數(shù)組Dist，其中每個分量Dist[k]表示當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)

k

的最短路徑。一般情況下，Dist[k]=<源點(diǎn)到頂點(diǎn)k

的弧上的權(quán)值>或者=<源點(diǎn)到其它頂點(diǎn)的路徑長度>+<其它頂點(diǎn)到頂點(diǎn)k

的弧上的權(quán)值>。1)

在所有從源點(diǎn)v0（v0∈S)

出發(fā)的弧中選取一條權(quán)值最小的弧(v0,u)，即為第一條最短路徑。Dist[k]

G.arcs[v0][k]其中的最小值即為最短路徑的長度。將該最小值所對應(yīng)的頂點(diǎn)j加入到S集中（S=S∪{j}）。S集是已求得最短路徑的頂點(diǎn)的集合.修改其它各頂點(diǎn)的Dist[k]值。假設(shè)求得最短路徑的頂點(diǎn)為j，若Dist[j]+G.arcs[j][k]<Dist[k]則將Dist[k]改為Dist[j]+G.arcs[j][k]。重復(fù)操作1）2)

共n-1次。由此求得其余各頂點(diǎn)的最短路徑是依路徑長度遞增的序列。INFINITYV0和k之間存在弧V0和k之間不存在弧V0V1V251010V5305060V420V3100∞∞10∞30100∞∞5∞∞∞∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞鄰接矩陣終點(diǎn)從V0到各終點(diǎn)的D值和最短路徑的求解過程i=1i=2i=3i=4i=5V1∞∞∞∞∞無V210(V0,

V2)V3∞60(V0,

V2,

V3)50(V0,

V4,

V3)V430(V0,

V4)30(V0,

V4)V5100(V0,

V5)100(V0,

V5)90(V0,

V4,

V5)60(V0,

V4,

V3,

V5)VjV2V4V3V5S{V0,

V2}{V0,

V2,

V4}{V0,

V2,

V3,

V4}{V0,

V2,

V3,

V4,

V5}2、求每一對頂點(diǎn)之間的最短路徑方法1：每次以一個頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行迪杰斯特拉算法n次。這樣，便可求得每一對頂點(diǎn)之間的最短路徑。方法2：弗洛伊德算法弗洛伊德算法的基本思想是：從

vi

到

vj

的所有可能存在的路徑中，選出一條長度最短的路徑。V0V1V251010V5305060V420V3100若<vi,vj>存在，則存在路徑{vi,vj}//路徑中不含其它頂點(diǎn)若<vi,v1>,<v1,vj>存在，則存在路徑{vi,v1,vj}//路徑中所含頂點(diǎn)序號不大于1若{vi,…,v2},{v2,…,vj}存在，則存在一條路徑{vi,…,v2,…vj}//路徑中所含頂點(diǎn)序號不大于2…依次類推，則vi

至vj

的最短路徑應(yīng)是上述這些路徑中，路徑長度最小者。1、拓?fù)渑判蚪o出有向圖G=(V,E)，V里的頂點(diǎn)的線性序列

(Vi1, Vi2

,…,Vin)若滿足如下條件：若在有向圖G中從頂點(diǎn)Vi到頂點(diǎn)Vj有一條路徑，則在序列中頂點(diǎn)Vi必在頂點(diǎn)Vj之前，則頂點(diǎn)的線性序列(Vi1, Vi2

,…,Vin)稱作一個拓?fù)湫蛄?。求有向圖中頂點(diǎn)的拓?fù)湫蛄械倪^程，稱作拓?fù)渑判颉?.6

拓?fù)渑判蚶纾?/p>

專業(yè)學(xué)生必須學(xué)

系列基本課程課程課程名稱先決條件C1程序設(shè)計(jì)基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，

C2C4匯編語言C1C5語言的設(shè)計(jì)與分析C3，

C4C6計(jì)算機(jī)原理C11C7編譯原理C5

，C3C8操作系統(tǒng)C3，

C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9，C10，C1課程之間的優(yōu)先關(guān)系可以用有向圖表示：C1C9C3C12C10C11C4C5C2C7C6C8一個有向圖可用來表示工程的施工圖，產(chǎn)品的生產(chǎn)流程圖，學(xué)生的課程安排圖等。

有向圖的頂點(diǎn)對應(yīng)一項(xiàng)子工程或一門課程等；有向邊<Vi,Vj>表示子工程或課程Vi必須在Vj之前完成。對有向圖的頂點(diǎn)進(jìn)行拓?fù)渑判颍?/p>

對應(yīng)于這些實(shí)際問題就是對各項(xiàng)子工程或各

門課程排出一個線性的順序關(guān)系。如果條件

限制這些工作必須串行的話，那就應(yīng)該按拓

撲排序安排執(zhí)行的先后順序。設(shè)有一項(xiàng)工程，有六項(xiàng)子工程第一項(xiàng)：無條件；第二項(xiàng)：在第一、三項(xiàng)完成之后；第三項(xiàng)：在第一項(xiàng)之后；第四項(xiàng)：在第一、六項(xiàng)之后；第五項(xiàng)：在第三、四、六項(xiàng)之后；第六項(xiàng)：無條件；該工程的先后關(guān)系可用有向圖表示。213456拓?fù)湫蛄?6，1，4，3，2，51，3，2，6，4，5用頂點(diǎn)表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為AOV-網(wǎng)。在AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)榇嬖诃h(huán)意味著某項(xiàng)活動應(yīng)以自己為先決條件。顯然，這是荒謬的。因此，對給定的AOV-網(wǎng)，應(yīng)首先判定網(wǎng)中是否存在環(huán)。檢測的辦法是對有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV-網(wǎng)中必定不存在環(huán)。例如：對于下列有向圖BDAC可求得拓?fù)溆行蛐蛄校篈

B

C

D

或

A

C

B

DBDAC反之，對于下列有向圖不能求得它的拓?fù)溆行蛐蛄小Ｒ驗(yàn)閳D中存在一個回路{B,

C,

D}如何進(jìn)行拓?fù)渑判?？?/p>

從圖中選擇一個沒有前驅(qū)的頂點(diǎn)，（即入度為零的點(diǎn)）且輸出之；⑵從圖中刪除此頂點(diǎn)及其所有由它發(fā)出的邊；⑶重復(fù)⑴、⑵兩步，直到所有的頂點(diǎn)均已輸出，整個拓?fù)渑判蛲瓿?；或者直到剩下的圖中再也沒有入度為零的頂點(diǎn)，說明此圖是有環(huán)圖，拓?fù)渑判虿荒茉龠M(jìn)行下去了。BDACa

b

h

c

d

g

f

e在算法中需要用定量的描述替代定性的概念沒有前驅(qū)的頂點(diǎn)

入度為零的頂點(diǎn)刪除頂點(diǎn)及其發(fā)出的邊

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

在鄰接矩陣上的實(shí)現(xiàn)選入度為零的點(diǎn)——011100000000010010000010000000000110刪除某頂點(diǎn)的所有出邊——

對應(yīng)行臵為全零；21

34

56拓?fù)渑判虻膶?shí)現(xiàn)找全零的列；⑵在鄰接表上的實(shí)現(xiàn)212V1V2V3V4V5V63032

54

indegree在表頭結(jié)點(diǎn)中增加一個存放頂點(diǎn)入度的域。在拓?fù)渑判蜻^程中，當(dāng)某頂點(diǎn)的入度為零時，輸出此頂點(diǎn)，并將由此頂點(diǎn)發(fā)出的有向邊所指的頂點(diǎn)的入度減1。為了避免重復(fù)檢測入度為零的頂點(diǎn)，需另設(shè)一個棧，用以存放入度為零的頂點(diǎn)。在鄰接表上實(shí)現(xiàn)的拓?fù)渑判蛩惴ǎ孩?/p>

輸入有向邊序列，建立鄰接表；⑵

查找鄰接表中入度為零的頂點(diǎn)，把入度為零的頂點(diǎn)壓入棧；⑶

當(dāng)棧不空時，使用退棧操作，取得棧頂元素v，并輸出v

;在鄰接表中查找v

的所有鄰接點(diǎn)w，將w

的入度減1，若w

的入度變成零，則w

進(jìn)棧，再轉(zhuǎn)⑶；⑷

當(dāng)?？諘r，若有向圖的所有頂點(diǎn)都已輸出，則拓?fù)渑判蜻^程正常結(jié)束；否則說明有向圖中存在有向回路。//有向圖采用鄰接表 結(jié)構(gòu)。若G無回路，則輸出G的頂點(diǎn)的一個拓?fù)湫蛄胁⒎祷豋K，否則ERRORFindInDegree(G,indegree);//對各頂點(diǎn)求入度,放到indegree數(shù)組InitStack(S);for

(

i=0;

i<G.vexnum;

++i)if

(!indegree[i]) Push(S,

i);//入度為零的頂點(diǎn)入棧TopologicalSort(ALGraph

G)

{count=0;//對輸出頂點(diǎn)計(jì)數(shù)while

(!EmptyStack(S))

{Pop(S,

v);

++count;

printf(v);for

(w=

Adj(G,v);

w!=0;

w=NextAdj(G,v,w)){

--indegree[w];//弧頭頂點(diǎn)的入度減1if

(!indegree[w]) Push(S,

w);//新產(chǎn)生的入度為零的頂點(diǎn)入棧}}if

(count<G.vexnum)

printf(“圖中有回路ERROR”)else

return

OK;}//

TopologicalSort7.7

關(guān)鍵路徑AOE-網(wǎng)(Active

On

Edge)：用頂點(diǎn)表示事件，弧表示活動，弧上權(quán)值表示活動持續(xù)時間的帶權(quán)有向無環(huán)圖稱為AOE-網(wǎng)。AOE-網(wǎng)可用來估算工程的完成時間。abcdeghk64521187244f源點(diǎn)匯點(diǎn)例如：有11項(xiàng)活動（?。∩蠙?quán)值表示完成此項(xiàng)活動所需時間。

9

個事件（頂點(diǎn)）。每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始。問題:①完成整項(xiàng)工程至少需要多少時間？②哪些活動是影響工程進(jìn)度的關(guān)鍵？即：哪些子工程項(xiàng)將影響整個工程的完成期限。由于整個工程只有一個開始點(diǎn)和一個完成點(diǎn)，故在正常情況（無環(huán)）下，網(wǎng)中只有一個入度為零的點(diǎn)（稱作源點(diǎn)）和一個出度為零的點(diǎn)（稱作匯點(diǎn)）。完成工程的最短時間：從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑的長度。（路徑上各活動持續(xù)時間之和，不是路徑上弧的數(shù)目。）關(guān)鍵路徑：路徑長度最長的路徑，叫做關(guān)鍵路徑。關(guān)鍵活動：關(guān)鍵路徑上的活動為關(guān)鍵活動。（該弧上的權(quán)值增加將使有向圖上的最長路徑的長度增加。）例如:源點(diǎn)匯點(diǎn)abcdeghk4521824f6174如何求關(guān)鍵活動？―事件(頂點(diǎn))‖的最早發(fā)生時間ve(j)ve(j)

=從源點(diǎn)到頂點(diǎn)j

的最長路徑長度；這個時間決定了所有以j

為尾的弧所表示的活動的最早開始時間。―事件(頂點(diǎn))‖的最遲發(fā)生時間vl(k)vl(k)=從頂點(diǎn)k到匯點(diǎn)的最短路徑長度。即在不推遲整個工程完2bcdgh成的前提下，所有以k為尾

6的弧所表示的活動的最遲

a

4開始時間。51e12k4f874事件發(fā)生時間的計(jì)算公式：“事件(頂點(diǎn))‖的最早發(fā)生時間ve(k):ve(源點(diǎn))=0；ve(k)

=

Max{ve(j)

+

dut(<j,

k>)}―事件(頂點(diǎn))‖的最遲發(fā)生時間vl(j):vl(匯點(diǎn))=ve(匯點(diǎn))；vl(j)

=

Min{vl(k)

–

dut(<j,

k>)}假設(shè)第i條弧為<j,

k>kj dut(<j,

k>)

假設(shè)第i條弧為<j,

k>，則對第i

項(xiàng)活動而言，“活動(弧)‖的最早開始時間

e(i)e(i)

=

ve(j)；“活動(弧)‖的最遲開始時間

l(i)即:在不推遲整個工程完成的前提下,活動i最遲必須開始進(jìn)行的時間l(i)

=

vl(k)

–

dut(<j,k>)；j

i

k2bcd6a

451e12k48

g7hf

4兩者之差

l

(

i

)

- e(

i

)

意味著完成活動i

的時間余量，

把

l(

i)

=

e(

i

)

的活動叫做關(guān)鍵活動abcdefghk64521187244abcdefghkve064577151418vl0668710161418拓?fù)溆行蛐蛄?a

-

d

-

f

-

c

-

b

-

e

-

h

-

g

-

kabcdefghkve064577151418vl0668710161418弧abacadbecedfegehfhgkhk權(quán)64511287424e0006457771514l02366887101614abek源點(diǎn)匯點(diǎn)6174h關(guān)鍵活動為<a,b><b,e>

<e,h><h,k>關(guān)鍵路徑為(a,b,e,h,k)用AOE網(wǎng)來估算工程完成的時間是非常有用的提高非關(guān)鍵活動的速度一般不會加快工程進(jìn)度。提高關(guān)鍵活動的速度有助于加快工程進(jìn)度。但關(guān)鍵活動的速度提高是有限度的，只有在不改變網(wǎng)的關(guān)鍵路徑的前提下，提高關(guān)鍵活動的速度才有效。若網(wǎng)中有幾條關(guān)鍵路徑，那么，單提高一條關(guān)鍵路徑上的關(guān)鍵活動的速度，不能導(dǎo)致整個工程縮短工期，而必須提高同時在幾條關(guān)鍵路徑上的活動的速度。求關(guān)鍵路徑的算法:⑴輸入

e

條弧<j,k>,

建立AOE-網(wǎng)的

結(jié)構(gòu);⑵從源點(diǎn)v0出發(fā),令ve[0]=0,按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時間ve[i](1≤i

≤n-1).如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n