《數(shù)據(jù)結(jié)構(gòu)用C語言描述》第七部分jsp課程 文檔預(yù)覽

圖的基本概念圖的存儲結(jié)構(gòu)圖的遍歷圖的連通性問題最小生成樹最短路徑活動(dòng)網(wǎng)絡(luò)第七章

圖圖的基本概念·

圖定義圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)其中

V

=

{

x|

x

某個(gè)數(shù)據(jù)對象}是頂點(diǎn)的有窮非空集合；

E1={(x,y)|

x,y或

E2

=

{<x,

y>

|

x,

yV

}V

&&

Path

(x,

y)}其中，E1是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合，此時(shí)的圖稱為無向圖。E2

表示從x到y(tǒng)的一條弧，且稱x為弧尾，y為弧頭，這樣的圖稱為有向圖。有向圖與無向圖在有向圖中，頂點(diǎn)對<x,y>是有序的。在無向圖中，頂點(diǎn)對(x,y)是無序的。完全圖若有n個(gè)頂點(diǎn)的無向圖有n(n-1)/2

條邊,則此圖為無向完全圖。有n個(gè)頂點(diǎn)的有向圖有

n(n-1)條邊,則此圖為有向完全圖。00

0

0

111221223

4

5

63鄰接頂點(diǎn)如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點(diǎn)。子圖

設(shè)有兩個(gè)圖G＝(V,

E)

和G‘＝(V’,V

且E‘

E,

則稱圖G’

權(quán)

某些圖的邊具有與它相關(guān)的數(shù),

稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。E‘)。若V’是圖G的子圖。0子圖0

0

01

221

2

13

3

3

3

頂點(diǎn)的度一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作D(v)。在有向圖中,頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。

頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的

條數(shù),記作ID(v);頂點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù),記作OD(v)。

路徑 在圖G＝(V,

E)

中,

若從頂點(diǎn)vi

出發(fā),沿一些邊經(jīng)過一些頂點(diǎn)

vp1,

vp2,

…,

vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi

vp1

vp2

...

vpm

vj)

為從頂點(diǎn)vi

到頂點(diǎn)

vj

的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。頂點(diǎn)的出度: 以頂點(diǎn)v為弧尾的弧的數(shù)目;頂點(diǎn)的入度: 以頂點(diǎn)v為弧頭的弧的數(shù)目。ABEC

F有向圖例如:頂點(diǎn)的度D=出度(OD)+入度(ID)D(B)=OD(B)+2ID(B)=3

路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑若路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡單路徑。

簡單回路若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合,則稱這樣的路徑為回路或環(huán)。120

0

02

1

2

13

3

3ABECF如:從A到F長度為

3的路徑{A,B,C,F}

連通圖與連通分量

在無向圖中,

若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,

則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的,

則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。

強(qiáng)連通圖與強(qiáng)連通分量 在有向圖中,若對于每一對頂點(diǎn)vi和vj,

都存在一條從vi到vj和從vj到vi的路徑,

則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。若無向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。B無向圖,若圖中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖;ACDFEBACDFE有向圖,若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量。AE

B

EF

C

F生成樹:假設(shè)一個(gè)連通圖有

n

個(gè)頂點(diǎn)和

e

條邊，其中

n-1

條邊和

n

個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。在極小連通子圖中增加一條邊，則一定有環(huán)。在極小連通子圖中去掉一條邊，則成為非連通圖。BACDFEBACDFE有n個(gè)頂點(diǎn)，n-1條邊的圖必定是生成樹嗎？對非連通圖，則稱由各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林。BACDFEBACDFE圖的存儲結(jié)構(gòu)鄰接矩陣(Adjacency

Matrix)

在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。

設(shè)圖A=(V,E)是一個(gè)有n個(gè)頂點(diǎn)的圖,圖的鄰接矩陣是一個(gè)二維數(shù)組A.edge[n][n]，定義：0123012無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。

在有向圖中,統(tǒng)計(jì)第i行1的個(gè)數(shù)可得頂點(diǎn)

i的出度，統(tǒng)計(jì)第j列1的個(gè)數(shù)可得頂點(diǎn)j的入度。在無向圖中,統(tǒng)計(jì)第i行(列)1的個(gè)數(shù)可得頂點(diǎn)i的度。186329542031網(wǎng)絡(luò)的鄰接矩陣#define

e

8#define

n

6//邊條數(shù)//頂點(diǎn)個(gè)數(shù)typedef

char

Vextype;typedef

float

adjtype;//頂點(diǎn)數(shù)據(jù)類型//邊上權(quán)值類型typedef

struct

{Vextype

vexs[n];//頂點(diǎn)表adjtype

arcs[n][n];//鄰接矩陣,可視為邊之間的關(guān)系}

graph;用鄰接矩陣表示的結(jié)構(gòu)定義下面給出建立一個(gè)無向網(wǎng)絡(luò)的算法CREATGRAPH(

graph

*ga

){

int

i,

j,

k

;

float

w

;for

(

i=0

;

i<n

;

i++

)ga->vexs[i]=getchar(

);for

(

i=0

;

i<n

;

i++

)for

(

j=0

;

j<n

;

j++

)ga->arcs[i][j]=0

;for

(

k=0

;

k<e

;

k++

){scanf(“%d%d%f”,&I,&j,&w);ga->arcs[i][j]=w;

ga->[j][i]=w;

}}鄰接表(Adjacency

List)·

鄰接表:是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)?！?/p>

弧的結(jié)點(diǎn)結(jié)構(gòu)adjvex;//該弧所指向的頂點(diǎn)的位置nextarc;//指向下一條弧指針info;//該弧相關(guān)信息的指針adjvex

nextarc

info·頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)data

firstarcdata;//頂點(diǎn)信息firstarc;//指向第一條依附該頂點(diǎn)的弧·無向圖的鄰接表同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn)),結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)dest和指針link。ABCDABCD0123data

link

dest

link

dest

link321010·

有向圖的鄰接表和逆鄰接表ABCdata

adjABC012dest

linkdest

linkdata

adjC0

A1

B2鄰接表(出邊表)dest

link逆鄰接表(入邊表)10

2101B

C網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表69A

D58ABCD02

123data

adj

dest

cost

link1

5

3

62

83

21

9(出邊表)(頂點(diǎn)表)圖的鄰接表存儲表示#define

MAX_VERTEX_NUM

20typedef

struct

Node

{int adjvex;

//

該弧所指向的頂點(diǎn)的位置struct

Node

*next;//

指向下一條弧指針I(yè)nfoType

*info;

//

該弧相關(guān)信息的指針}

edgeNode;typedef

struct{

Vextype

vertex;//頂點(diǎn)信息edgeNode

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

VexNode;

VexNode[MAX_VERTEX_NUM];鄰接表的構(gòu)造算法void

CREATADJLIST(vexnode

ga[

]){

int

i,

j,

k

;

edgenode

*s

;//輸入頂點(diǎn)信息for

(

i

=

0;

i

<

n;

i++){

ga[i].vertex=getchar(

);ga[i].link

=

NULL;}//逐條邊輸入for

(

k

=

0;

k

<

e;

k++){

scanf(“%d%d”,&i,&j);s=malloc(sizeof(edgenode));s->adjvex=

j;

s->next

=

ga[i].link;ga[i]->link

=

s;s=malloc(sizeof(edgenode));s->adjvex

=

i;s->next=

ga[j].link;ga[j]->link

=

s;}}圖的遍歷

從圖中某一頂點(diǎn)出發(fā)訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，這一過程就

叫做圖的遍歷(Traversing

Graph)。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。

為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited[]。

輔助數(shù)組visited[]的初始狀態(tài)為0,在圖的遍歷過程中,一旦某一個(gè)頂點(diǎn)i被訪問,

就立即讓visited[i]為1,防止它被多次訪問。兩種圖的遍歷方法:深度優(yōu)先搜索DFS

(Depth

First

Search)廣度優(yōu)先搜索BFS

(Breadth

First

Search)深度優(yōu)先搜索DFS(Depth

First

Search)深度優(yōu)先搜索過程6C7

DGFCG1A2B3E45I91A2B3E456

F7

DH8I9H8前進(jìn)回退深度優(yōu)先生成樹

DFS

在訪問圖中某一起始頂點(diǎn)v

后,

由v

出發(fā),

訪問它的任一鄰接頂點(diǎn)w1;

再從w1

出發(fā),訪問與w1鄰接但還沒有訪問過的頂點(diǎn)w2;然后再從w2

出發(fā),

進(jìn)行類似的訪問,

…

如此進(jìn)行下去, 直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn)u

為止。接著, 退回一步, 退到前一次剛訪問過的頂點(diǎn), 看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有, 則訪問此頂點(diǎn),

之后再從此頂點(diǎn)出發(fā), 進(jìn)行與前述類似的訪問;

如果沒有,

就再退回一步進(jìn)行搜索。重復(fù)上述過程,

直到連通圖中所有頂點(diǎn)都被訪問過為止。圖的深度優(yōu)先搜索算法int

visited[n];

graph

g;void

DFS

(

int

i

){

int

j

;for

(

j

=

0;

j<

n;

j++

)visited

[j]

=

0;//訪問數(shù)組visited初始化printf(“node:%c\n”,g.vexs[i]);visited[i]=1;for

(

j=0;

j<n;

j++

)if

((g.arcs[i][j]==1&&(

!

visited[j]

))DFS

(

j

);//從頂點(diǎn)j出發(fā)開始搜索}void

DFSL

(

int

i

){

int

j;

edgenode

*p;

printf(“node:%c\n”,g1[i].vertex);

//訪ivisited[i]

=

1;p=g1[i].link;//頂點(diǎn)v作訪問標(biāo)記//取i的第一個(gè)鄰接頂點(diǎn)pwhile

(

p

!=

NULL

)//若鄰接頂點(diǎn)存在{

if

(

!visited[p->adjvex]

)DFSL

(p->adjvex);//若頂點(diǎn)p未訪問過,遞歸訪問頂點(diǎn)pp=p->next;//取頂點(diǎn)i排在p后的下一個(gè)鄰接頂點(diǎn)}}廣度優(yōu)先搜索BFS(Breadth

First

Search)廣度優(yōu)先搜索過程CGFCG1A2B34

D5E67H8I91A2B34

D5E6

F7H8廣度優(yōu)先生成樹I9

BFS在訪問了起始頂點(diǎn)v之后,由v出發(fā),依次訪問v的各個(gè)未被訪問過的鄰接頂點(diǎn)w1,

w2,…,wt,然后再順序訪問w1,w2,…,wt

的所有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點(diǎn)，…如此做下去，直到圖中所有頂點(diǎn)都被訪問到為止。

廣度優(yōu)先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點(diǎn),不像深度優(yōu)先搜索那樣有往回退的情況。因此,廣度優(yōu)先搜索不是一個(gè)遞歸的過程。

為了實(shí)現(xiàn)逐層訪問,算法中使用了一個(gè)隊(duì)列,以記憶正在訪問的這一層和下一層的頂點(diǎn),以便于向下一層訪問。

為避免重復(fù)訪問,需要一個(gè)輔助數(shù)組visited[]，給被訪問過的頂點(diǎn)加標(biāo)記。圖的廣度優(yōu)先搜索算法void

DFS(

int k

){

int

i

,j

;

SETNULL(Q);printf(“%c\n”,g.vexs[k]);visited[k]=1;

ENQUEUE(Q,k);while

(

!

EMPTY(Q)

){i=DEQUEUE(Q);for(j=0

;j<

n

;

j++

)if

((

g.arcs[i][j]==1)&&

(

!visited[j]

)){printf(“%c\n”,g.vexs[j]);visited[j]=1;ENQUEUE

(

Q,j);}}}void

DFSL(

int k

){

int

i

;

edgenode

*p

;

SETNULL(Q);printf(“%c\n”,g1[k].vertex);visited[k]=1;

ENQUEUE(Q,k);while

(

!EMPTY(Q)){

i=DEQUEUE(Q);

p=g1[i].link;while(

p!=NULL){

if(!visited[p->adjvex]){printf(“%c\n”,g1[p->adjvex].vertex);visited[p->sdjvex]=1;ENQUEUE(Q,p->adjvex);}p=p->next;}}}連通分量(Connected

component)

當(dāng)無向圖為非連通圖時(shí),從圖中某一頂點(diǎn)出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn),只能訪問到該頂點(diǎn)所在的最大連通子圖(連通分量)的所有頂點(diǎn)。

若從無向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷,可求得無向圖的所有連通分量。圖的連通性問題

求連通分量的算法需要對圖的每一個(gè)頂點(diǎn)進(jìn)行檢測：若已被訪問過，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個(gè)連通分量。

對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。AEIB

C

DFHL

M

NKAJ

O非連通無向圖的三個(gè)連通分量KEB

C

DFOG

JNI

L

M非連通圖的連通分量的極小連通子圖非連通圖的遍歷算法TRAVER（

）{

int

i；for

(i=0;

i<n;

i++

)visited[i]=FALSE;for

(i=0;

i<n;

i++

){

if

(!visited[i]

)DFS(

i

);printf

(

“comp

end

\n”

);}}重連通分量(Biconnected

Component)

在無向連通圖G中,當(dāng)且僅當(dāng)刪去G中的頂點(diǎn)v及所有依附于v的所有邊后,可將圖分割成兩個(gè)或兩個(gè)以上的連通分量，則稱頂點(diǎn)v為關(guān)節(jié)點(diǎn)。沒有關(guān)節(jié)點(diǎn)的連通圖叫做重連通圖。

在重連通圖上,任何一對頂點(diǎn)之間至少存在有兩條路徑,在刪去某個(gè)頂點(diǎn)及與該頂點(diǎn)相關(guān)聯(lián)的邊時(shí),也不破壞圖的連通性。

一個(gè)連通圖G如果不是重連通圖，那么它可以包括幾個(gè)重連通分量。

在一個(gè)無向連通圖G中,重連通分量可以利用深度優(yōu)先生成樹找到。

在圖中各頂點(diǎn)旁標(biāo)明的深度優(yōu)先數(shù),給出進(jìn)行深度優(yōu)先搜索時(shí)各頂點(diǎn)訪問的次序。

深度優(yōu)先生成樹的根是關(guān)節(jié)點(diǎn)的充要條件是它至少有兩個(gè)子女。AIJBCEDFHGAIJ3A9IJ10BH關(guān)2B16H8CEDFG節(jié)點(diǎn)4C5EDFG7關(guān)節(jié)點(diǎn)關(guān)節(jié)點(diǎn)根有兩個(gè)子女ABCED

FGHIJABHID

FBCDEFGH連通圖和它的連通分量最小生成樹(minimum

cost

spanning

tree)

使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。

按照生成樹的定義，n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹有n個(gè)頂點(diǎn)、n-1條邊。構(gòu)造最小生成樹的準(zhǔn)則

必須使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達(dá)到最小。普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡(luò)N

=

{

V,

E

}中的某一頂點(diǎn)u0

出發(fā),

選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊

(

u0,v

),

將其頂點(diǎn)加入到生成樹頂點(diǎn)集合U中。以后每一步從一個(gè)頂點(diǎn)在U中,而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合U中。如此繼續(xù)下去,直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。采用鄰接矩陣作為圖的存儲表示。01328105251462442204130412原圖(a)3(b)43(d)(e)

(f)432242201010101010114165625625622525122512322(c)161010218

125625256在構(gòu)造過程中，還設(shè)置了兩個(gè)輔助數(shù)組：lowcost[]

存放生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)到0

1生成樹外各頂點(diǎn)的各邊上的當(dāng)前最小權(quán)值；

nearvex[]

記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近(即權(quán)值最小)。例子28105251462442218316212

若選擇從頂點(diǎn)0出發(fā)，即u0

=0，則兩個(gè)輔助數(shù)組的初始狀態(tài)為：然后反復(fù)做以下工作：

在lowcost[]中選擇nearvex[i]-1

&&

lowcost[i]最小的邊,用v標(biāo)記它。則選中的權(quán)值最小的邊為(nearvex[v],v),相應(yīng)的權(quán)值為lowcost[v]。0

0

0

0

0

00

1

2

3

4

5

6lowcost

0

28

10nearvex

-1將nearvex[v]

改為-1, 表示它已加入生成樹頂點(diǎn)集合。將邊(nearvex[v],

v,

lowcost[v]

) 加入生成樹的邊集合。取lowcost[i]=min{lowcost[i],Edge[v]}，即用生成樹頂點(diǎn)集合外各頂點(diǎn)i到剛加入該集合的新頂點(diǎn)v的距離Edge[v][i]與原來它們到生成樹頂點(diǎn)集合中頂點(diǎn)的最短距離lowcost[i]做比較,取距離近的作為這些集合外頂點(diǎn)到生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)的最短距離。

如果生成樹頂點(diǎn)集合外頂點(diǎn)i到剛加入該集合的新頂點(diǎn)v的距離比原來它到生

成樹頂點(diǎn)集合中頂點(diǎn)的最短距離還要近，則修改nearvex[i]:nearvex[i]=v。表示生成樹外頂點(diǎn)i到生成樹內(nèi)頂點(diǎn)v當(dāng)前距離最近。0123

456lowcost

02810nearvex

-1000

000選v=5選邊(0,5)頂點(diǎn)v=5加入生成樹頂點(diǎn)集合：0

1

2

3

4

5

6lowcost

0

28

25

10nearvex

-10

0

0

5

-1

0選v=4

選邊(5,4)01281052514624422183原圖邊(0,5,10)加入生成樹162120614

3210525頂點(diǎn)v=4加入生成樹頂點(diǎn)集合：0

1

2

3

4

5

6lowcost

0

28

22

25

10

24nearvex

-10

0

4

-1

-1

4選v=3

選邊(4,3)01281052514624422183原圖邊(5,4,25)加入生成樹1621260

14

321052522頂點(diǎn)v=3加入生成樹頂點(diǎn)集合：0

3

-1

-1

-1

30

1

2

3

4

5

6lowcost

0

28

12

22

25

10

18nearvex

-1選v=2

選邊(3,2)0281052514624422183原圖邊(4,3,22)加入生成樹162121

0614

31052522212頂點(diǎn)v=2加入生成樹頂點(diǎn)集合：0

1

2

3

4

5

6lowcost

0

16

12

22

2510

18nearvex

-1

2-1

-1

-1

-1

30選v=12811052514624422183原圖邊(3,2,12)加入生成樹1621213選邊(2,1)01052542216212頂點(diǎn)v=1加入生成樹頂點(diǎn)集合：10

14-1

-1

-1

-1

1nearvex

-1

-10

1

2

3

4

5

6lowcost

0

16

12

22

25選v=6選邊(1,6)01281052514624422183原圖邊(2,1,16)加入生成樹16212014

3105251462216212頂點(diǎn)v=6加入生成樹頂點(diǎn)集合：0

1

2

3

4

5

6lowcost

0

16

12

22

2510

14nearvex

-1

-1-1

-1

-1

-1

-10

1281014622525

24

184

3原圖邊(1,6,14)加入生成樹162120

14

3105251462216212最后生成樹中邊集合里存入得各條邊為：(0,5,10),(5,4,25),(4,3,22),(3,

2,

12),

(2,

1,

16),

(1,

6,

14)利用普里姆算法建立最小生成樹voidPrim

(

Graph

G,

MST&

T,

int

u

)

{float

*

lowcost

=

new

float[NumVertices];int

*

nearvex

=

new

int[NumVertices];

for

(

int

i

=

0;

i

<

NumVertices;

i++

)

{lowcost[i]

=

G.Edge[u][i];//Vu到各點(diǎn)代價(jià)nearvex[i]

=

u;//及最短帶權(quán)路徑}nearvex[u]

=

-1;//加到生成樹頂點(diǎn)集合int

k

=

0;//存放最小生成樹結(jié)點(diǎn)的變量for

(

i

=

0;

i

<

G.n;

i++

)if

(

i

!=

u

)

{//循環(huán)n-1次,加入n-1條邊EdgeData

min

=

MaxValue;

int

v

=

0;for

(

int

j

=

0;

j

<

NumVertices;

j++

)if

(

nearvex[j]

!=

-1

&&//=-1不參選lowcost[j]

<

min

){

v

=

j;

min

=

lowcost[j];

}//求生成樹外頂點(diǎn)到生成樹內(nèi)頂點(diǎn)具有最//小權(quán)值的邊,v是當(dāng)前具最小權(quán)值的邊if

(

v

)

{//v=0表示再也找不到要求頂點(diǎn)T[k].tail=nearvex[v];//選邊加入生成樹T[k].head

=

v;T[k++].cost

=

lowcost[v];nearvex[v]=-1;

//該邊加入生成樹標(biāo)記for

(

j

=

0;

j

<

G.n;

j++

)if

(

nearvex[j]

!=

-1

&&G.Edge[v][j]

<

lowcost[j]

)

{//修改lowcost[j]

=

G.Edge[v][j];nearvex[j]

=

v;}}}

//循環(huán)n-1次,加入n-1條邊}

分析以上算法,設(shè)連通網(wǎng)絡(luò)有n個(gè)頂點(diǎn),則該算法的時(shí)間復(fù)雜度為O(n2),它適用于邊稠密的網(wǎng)絡(luò)。

注意：當(dāng)各邊有相同權(quán)值時(shí)，由于選擇的隨意性，產(chǎn)生的生成樹可能不唯一。當(dāng)各邊的權(quán)值不相同時(shí)，產(chǎn)生的生成樹是唯一的。

計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。

例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程

可以并行地學(xué)習(xí)?；顒?dòng)網(wǎng)絡(luò)(Activity

Network)用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV網(wǎng)絡(luò))C1高等數(shù)學(xué)C2C3程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)C1,C2C4C5

C6數(shù)據(jù)結(jié)構(gòu)高級語言程序設(shè)計(jì)編譯方法C3,C2

C5,C2C4C7C8操作系統(tǒng)普通物理C4,C1C9C9計(jì)算機(jī)原理C8課程代號課程名稱先修課程C8C5學(xué)生課程學(xué)習(xí)工程圖C3C4C9C6C7C1C2

可以用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊<Vi,

Vj>表示活動(dòng)Vi

必須先于活動(dòng)Vj

進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò)(Activity

On

Vertices)。

在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路, 即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。

因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。

檢測有向環(huán)的一種方法是對AOV網(wǎng)絡(luò)構(gòu)造

它的拓?fù)溆行蛐蛄?。即將各個(gè)頂點(diǎn)(代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列，使得

AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系

都能得到滿足。

這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判颉?/p>

如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂

點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄?則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。C5C3C4

如果AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。

例如, 對學(xué)生選課工程圖進(jìn)行拓?fù)渑判?

得到的拓?fù)溆行蛐蛄袨镃1

,

C2

,

C3

,

C4

,

C5

,

C6

,

C8

,

C9

,

C7或

C1

,

C8

,

C9

,

C2

,

C5

,

C3

,

C4

,

C7

,

C6C8

C9C6C7C1C2拓?fù)渑判虻姆椒á佥斎階OV網(wǎng)絡(luò)。令n為頂點(diǎn)個(gè)數(shù)。②在AOV網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn),并輸出之;③從圖中刪去該頂點(diǎn),同時(shí)刪去所有它發(fā)出的有向邊;④重復(fù)以上②、③步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿?；或圖中還有未輸出的頂點(diǎn),但已跳出處理循環(huán)。說明圖中還剩下一些頂點(diǎn),它們都有直接前驅(qū)。這時(shí)網(wǎng)絡(luò)中必存在有向環(huán)。C0

C1C2C3C4C5拓?fù)渑判虻倪^程(a)有向無環(huán)圖C2C5C1C0C1C2C5C3(c)輸出頂點(diǎn)C0C3

C4(b)輸出頂點(diǎn)C4C0C2C5C1C3(d)輸出頂點(diǎn)C3C1C2C5(e)輸出頂點(diǎn)C2C5C1(f)輸出頂點(diǎn)C1C5(g)輸出頂點(diǎn)C5最后得到的拓?fù)溆行蛐蛄袨镃4,C0,C3,C2

,C1

,C5。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系對于本來沒有這種關(guān)系的頂點(diǎn)，如C4和C2，也

排出了先后次序關(guān)系。(h)拓?fù)渑判蛲瓿葾OV網(wǎng)絡(luò)及其鄰接表表示C3C4C5C0012345count

data

adj130103dest

link13

0C15C2150C30C4C500C01C15C20

在鄰接表中增設(shè)一個(gè)數(shù)組count[]，記錄各頂點(diǎn)入度。入度為零的頂點(diǎn)即無前驅(qū)頂點(diǎn)。

在輸入數(shù)據(jù)前,頂點(diǎn)表VexList[]和入度數(shù)組

count[]全部初始化。在輸入數(shù)據(jù)時(shí),每輸入一條邊<j,k>,就需要建立一個(gè)邊結(jié)點(diǎn),并將它鏈入相應(yīng)邊鏈表中,統(tǒng)計(jì)入度信息：EdgeNode

*

p

=

new

EdgeNode;p->dest

=

k;//建立邊結(jié)點(diǎn)p->link

=

G.VexList[j].firstAdj;VexList[j].firstAdj

=

p;//鏈入頂點(diǎn)

j的邊鏈表的前端count[k]++;//頂點(diǎn)

k入度加一

在算法中,使用一個(gè)存放入度為零的頂點(diǎn)的鏈?zhǔn)綏?供選擇和輸出無前驅(qū)的頂點(diǎn)。拓?fù)渑判蛩惴擅枋鋈缦拢航⑷攵葹榱愕捻旤c(diǎn)棧;當(dāng)入度為零的頂點(diǎn)棧不空時(shí),重復(fù)執(zhí)行從頂點(diǎn)棧中退出一個(gè)頂點(diǎn),并輸出之;從AOV網(wǎng)絡(luò)中刪去這個(gè)頂點(diǎn)和它發(fā)出的邊,邊的終頂點(diǎn)入度減一;如果邊的終頂點(diǎn)入度減至0,則該頂點(diǎn)進(jìn)入度為零的頂點(diǎn)棧;

如果輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù),則報(bào)告網(wǎng)絡(luò)中存在有向環(huán)。拓?fù)渑判虻乃惴╲oid

TopologicalSort

(AdjGraph

G)

{Stack

S;

StackEmpty(S);

int

j;//入度為零的頂點(diǎn)棧初始化for

(

int

i

=

0;

i

<

n;

i++

)//入度為零頂點(diǎn)if

(

count[i]

==

0

)

Push(S,

i);//進(jìn)for(i=0;i<n;i++)

//期望輸出n個(gè)頂點(diǎn)if(StackEmpty(S)){

//中途?？?轉(zhuǎn)出

cout<<“網(wǎng)絡(luò)中有回路！"<<endl;return;}else

{Pop(

S,

j

);//繼續(xù)拓?fù)渑判?/退棧//輸出cout

<<

j

<<

endl;EdgeNode

*

p

=

VexList[j].firstAdj;while

(

p

!=

NULL

)

{int

k

=

p->dest;//掃描出邊表//另一頂點(diǎn)//頂點(diǎn)入度減一if

(

--count[k]

==

0

)Push(

S,

k

);//頂點(diǎn)的入度減至零,進(jìn)棧p

=

p->link;}}}用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE網(wǎng)絡(luò))如果在無有向環(huán)的帶權(quán)有向圖中,用有向邊表示一個(gè)工程中的活動(dòng)(Activity),

用邊上權(quán)值表示活動(dòng)持續(xù)時(shí)間(Duration),

用頂點(diǎn)表示事件(Event),

則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò),簡稱AOE(Activity

OnEdges)網(wǎng)絡(luò)。

AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?從源點(diǎn)到各個(gè)頂點(diǎn),以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同,但只有各條路徑上所有活動(dòng)都完成了,整個(gè)工程才算完成。

因此,完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長路徑長度,即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(Critical

Path)。411a

=82

5810a

=12a8=187a9=65a

=28a6=867a

=6a

=143a4=10a2=12

3

要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng),即不按期完成就會影響整個(gè)工程完成的活動(dòng)。

關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。因此,只要找到了關(guān)鍵活動(dòng),就可以找到關(guān)鍵路徑。例如,下圖就是一個(gè)AOE網(wǎng)。定義幾個(gè)與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量：①事件Vi

的最早可能開始時(shí)間Ve(i)是從源點(diǎn)V0

到頂點(diǎn)Vi

的最長路徑長度。②事件Vi

的最遲允許開始時(shí)間Vl[i]是在保證匯點(diǎn)Vn-1

在Ve[n-1]時(shí)刻完成的前提下，事件Vi

的允許的最遲開始時(shí)間。③活動(dòng)ak

的最早可能開始時(shí)間e[k]設(shè)活動(dòng)ak

在邊<Vi

,Vj

>上,則e[k]是從源點(diǎn)V0到頂點(diǎn)Vi

的最長路徑長度。因此,e[k]=Ve[i]。④活動(dòng)ak

的最遲允許開始時(shí)間l[k]l[k]是在不會引起時(shí)間延誤的前提下,該活動(dòng)允許的最遲開始時(shí)間。l[k]=Vl[j]-dur(<i,j>)。其中,dur(<i,j>)是完成ak

所需的時(shí)間。時(shí)間余量l[k]-e[k]表示活動(dòng)ak

的最早可能開始時(shí)間和最遲允許開始時(shí)間的時(shí)間余量。l[k]==e[k]表示活動(dòng)ak

是沒有時(shí)間余量的關(guān)鍵活動(dòng)。

為找出關(guān)鍵活動(dòng),需要求各個(gè)活動(dòng)的e[k]與

l[k]，以判別是否l[k]==e[k]。

為求得e[k]與l[k], 需要先求得從源點(diǎn)V0

到各個(gè)頂點(diǎn)Vi

的Ve[i]

和Vl[i]。求Ve[i]的遞推公式從Ve[0]=0

開始，向前遞推<

Vj,

Vi

>

S2,

i

=

1,

2,

,

n-1S2

是所有指向Vi

的有向邊<Vj

,Vi

>的集合。從Vl[n-1]=Ve[n-1]開始，反向遞推<

Vi,

Vj

>

S1,

i

=

n-2,

n-3,

,

0S1是所有源自Vi的有向邊<Vi

,Vj

>的集合。

這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚣澳嫱負(fù)溆行虻那疤嵯逻M(jìn)行。

設(shè)活動(dòng)ak

(k=1,2,…,e)在帶權(quán)有向邊<Vi,Vj>上,其持續(xù)時(shí)間用dur(<Vi

,Vj

>)表示,則有e[k]

=

Ve[i]；l[k]=Vl[j]-dur(<Vi

,Vj

>)；k=1,2,…,這樣就得到計(jì)算關(guān)鍵路徑的算法?！榱撕喕惴?假定在求關(guān)鍵路徑之前已經(jīng)對各頂點(diǎn)實(shí)現(xiàn)了拓?fù)渑判?并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)行了編號。241a2=125810a

=12a8=187a9=65a

=28a6=867a

=63a1=8

a

=1443a

=101

2

3

4

5

6

7

8Ve

0

8

12

22

28

40

46

58Vl

0

8

12

22

28

40

46

5812

12

22

22

28

40

4612

12

32

22

28

40

461

2

3

4

5

6

7

8

9

10e

0

0

8l

0

0

8事件Ve[i]Vl[i]V000V166V246V358V477V5710V61616V71414V81818邊

<0,1><0,2><0,3><1,4><2,4><3,5><4,6><4,7><5,7><6,8><7,8>活動(dòng)

a1

a2

a3

a4

a5

a6

a7

a8

a9a10

a11e0006457771614l02366877101614l

-

e02302300300關(guān)鍵是是是

是是

是利用關(guān)鍵路徑法求AOE網(wǎng)的各關(guān)鍵活動(dòng)void

graph::CriticalPath

(){//在此算法中需要對鄰接表中單鏈表的結(jié)點(diǎn)加以//修改,在各結(jié)點(diǎn)中增加一個(gè)int域cost,記錄該結(jié)//點(diǎn)所表示的邊上的權(quán)值。int

i,

j;

int

p,

k;

int

e,

l;Ve

=

new

int[n];

Vl

=

new

int[n];for

(i=0;i<n;i++)Ve[i]=0;//初始化for

(i=0;i<n;i++){//順向計(jì)算事件最早允許開始時(shí)間Edge<int>*p=NodeTable[i].adj;//該頂點(diǎn)邊鏈表鏈頭指針p

while

(p

!=NULL

){//找所有后繼鄰接頂點(diǎn)k

=p→dest;//i的后繼鄰接頂點(diǎn)kif

(

Ve[i]

+

p→cost

>

Ve[k]

)Ve[k]

=

Ve[i]

+

p→cost;p=p→link;//找下一個(gè)后繼}}for

(i=0;i<n;i++)Vl[i]=Ve[n-1];//逆向計(jì)算的最遲開始時(shí)間for

(i=n-2;i;i--){//按逆拓?fù)溆行蝽樞蛱幚韕=NodeTable[i].adj;//該頂點(diǎn)邊鏈表鏈頭指針pwhile

(

p

!=

NULL

)

{k

=p→dest;//i的后繼鄰接頂點(diǎn)kif

(

Vl[k]

-

p→cost

<

Vl[i])Vl[i]=Vl[k]-p→cost;p

=p→link;//找下一個(gè)后繼}}for

(i=0;i<n;i++){//逐個(gè)頂點(diǎn)求各活動(dòng)的e[k]和l//該頂點(diǎn)邊鏈表鏈頭指針pp

=

NodeTable[i].adj;while

(

p

!=

NULL

)

{k

=

p→dest;//k是i的后繼鄰接頂點(diǎn)e=Ve[i];

l=Vl[k]-p→cosif

(l==e

)//關(guān)鍵活動(dòng)cout

<<

"<"

<<

i

<<

","

<<

k<<“>”<<“是關(guān)鍵活動(dòng)”<<endl;p

=p→link;//找下一個(gè)后繼}}}注意在拓?fù)渑判蚯骎e[i]和逆拓?fù)溆行蚯骎l[i]時(shí),

所需為O(n+e),

求各個(gè)活動(dòng)的e[k]和l[k]時(shí)所需時(shí)間為O(e),

總共花費(fèi)時(shí)間仍然是O(n+e)。所有頂點(diǎn)按拓?fù)溆行虻拇涡蚓幪杻H計(jì)算Ve[i]和Vl[i]是不夠的，還須計(jì)算

e[k]和l[k]。不是任一關(guān)鍵活動(dòng)加速一定能使整個(gè)工程提前。想使整個(gè)工程提前，要考慮各個(gè)關(guān)鍵路徑上所有關(guān)鍵活動(dòng)。最短路徑(Shortest

Path)

最短路徑問題：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。問題解法邊上權(quán)值非負(fù)情形的單源最短路徑問題—

Dijkstra算法邊上權(quán)值為任意值的單源最短路徑問題Bellman和Ford算法所有頂點(diǎn)之間的最短路徑Floyd算法邊上權(quán)值非負(fù)情形的單源最短路徑問題

問題的提法：給定一個(gè)帶權(quán)有向圖D與源點(diǎn)v，求從v到D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。

為求得這些最短路徑,

Dijkstra提出按路徑長度的遞增次序,

逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。舉例說明Dijkstra逐步求解的過程43210150200

10030

1060源點(diǎn)終點(diǎn)最短路徑路徑長度v0v1(v0,v1)10v2v3(v