數(shù)據(jù)結(jié)構(gòu)-合肥工業(yè)大學(xué) 7

第七章圖★基本術(shù)語★圖的存儲結(jié)構(gòu)★圖的遍歷★最小生成樹和最短路徑問題★AOV網(wǎng)與拓?fù)渑判颉顰OE網(wǎng)與關(guān)鍵路徑7.1基本術(shù)語

圖是由頂點(diǎn)的非空有窮集合與頂點(diǎn)之間關(guān)系(邊或弧)的集合構(gòu)成的結(jié)構(gòu),通常表示為

G=(V,E)其中,V為頂點(diǎn)集合,E為關(guān)系(邊或弧)的集合.一.圖的定義關(guān)于一條邊或弧的表示方法:vjvivjvivjvivjvi(1).用圖形:

(vi,vj)(2).用符號:(b).

這條邊依附于頂點(diǎn)vi和vj。(a).頂點(diǎn)vi與vj

是這條邊的兩個(gè)鄰接點(diǎn)。(3).用語言:v1v2v3v4

其中

V1={v1,v2,v3,v4}E1={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}G1=(V1,E1)v1v2v3v4其中

V2={v1,v2,v3,v4}E2={<v1,v2>,<v2,v1>,<v2,v3>,<v4,v3>}G2=(V2,E2)

無向圖：

有向圖：與邊有關(guān)的數(shù)據(jù)稱為權(quán),邊上帶權(quán)的圖稱為網(wǎng)絡(luò)。二.圖的分類對于（vi,vj)E,必有（vj,vi)E，并且偶對中頂點(diǎn)的前后順序無關(guān)。若<vi,vj>E是頂點(diǎn)的有序偶對。

網(wǎng)(絡(luò))：v1v2v3v4v1v2v3v4v1v2v3v4104178

1.頂點(diǎn)的度對于有向圖而言,有:

頂點(diǎn)的出度:

以頂點(diǎn)vi為出發(fā)點(diǎn)的邊的數(shù)目,記為OD(vi).

頂點(diǎn)的入度:

以頂點(diǎn)vi為終止點(diǎn)的邊的數(shù)目,記為ID(vi).

TD(vi)=OD(vi)+ID(vi)三.名詞術(shù)語依附于頂點(diǎn)vi的邊的數(shù)目,記為TD(vi).v1v2v3v4v1v3v4v2

邊的數(shù)目達(dá)到最大的圖稱為完全圖.邊的數(shù)目達(dá)到或接近最大的圖稱為稠密圖,否則,稱為稀疏圖.具有n個(gè)頂點(diǎn)的有向圖最多有n(n-1)條邊.具有n個(gè)頂點(diǎn)的無向圖最多有n(n-1)/2條邊.對于具有n個(gè)頂點(diǎn),e條邊的圖,有

2e=

TD(vi)ni=1結(jié)論1結(jié)論2結(jié)論3

2.

路徑DCEBAP(A,E):

A,B,EA,C,D,E

出發(fā)點(diǎn)與終止點(diǎn)相同的路徑稱為回路或環(huán)；頂點(diǎn)序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。不帶權(quán)的圖的路徑長度是指路徑上所經(jīng)過的邊的數(shù)目，帶權(quán)的圖的路徑長度是指路徑上經(jīng)過的邊上的權(quán)值之和。頂點(diǎn)vx到vy之間有路徑P(vx,vy)的充分必要條件為:存在頂點(diǎn)序列vx,vi1,vi2,…,vim,vy,

并且序列中相鄰兩個(gè)頂點(diǎn)構(gòu)造的頂點(diǎn)偶對分別為圖中的一條邊。

3.子圖v1v2v3v4對于圖G=(V,E)與G′=(V′,E′),若有V′

V,E′

E,則稱G′為G的一個(gè)子圖.v1v2v3v4v1v2

4.圖的連通無向圖中頂點(diǎn)vi到vj

有路徑,則稱頂點(diǎn)vi與vj

是連通的。若無向圖中任意兩個(gè)頂點(diǎn)都連通,則稱該無向圖是連通的。若有向圖中頂點(diǎn)vi到vj

有路徑,并且頂點(diǎn)vj

到vi也有路徑,則稱頂點(diǎn)vi與vj

是連通的。若有向圖中任意兩個(gè)頂點(diǎn)都連通,則稱該有向圖是強(qiáng)連通的。(1).無向圖的連通(2).有向圖的連通

5.生成樹

包含具有n個(gè)頂點(diǎn)的連通圖G的全部n個(gè)頂點(diǎn),僅包含其n-1條邊的連通子圖稱為G的一個(gè)生成樹。v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2對于一個(gè)圖,需要存儲的信息應(yīng)該包括:(1).所有頂點(diǎn)的數(shù)據(jù)信息；(2).頂點(diǎn)之間關(guān)系(邊或弧)的信息;(3).權(quán)的信息。7.2圖的存儲結(jié)構(gòu)一.鄰接矩陣存儲方法核心思想:采用兩個(gè)數(shù)組存儲一個(gè)圖.1.定義一個(gè)一維數(shù)組VERTEX[1:n]存放圖中所有頂點(diǎn)的數(shù)據(jù)信息.2.定義一個(gè)二維數(shù)組A[1:n,1:n]存放圖中所有頂點(diǎn)之間關(guān)系的信息(該數(shù)組被稱為鄰接矩陣),有

1

當(dāng)頂點(diǎn)vi到頂點(diǎn)vj有邊時(shí)A[i,j]=

0

當(dāng)頂點(diǎn)vi到頂點(diǎn)vj無邊時(shí)

對于帶權(quán)的圖,有

wij

當(dāng)頂點(diǎn)vi到頂點(diǎn)vj有邊,且邊的權(quán)為wij

A[i,j]=

當(dāng)頂點(diǎn)vi到頂點(diǎn)vj無邊時(shí)

oo數(shù)組存儲方法0111101111011110A1=v1v2v3v4Vertex1[1:4]v1v2v3v4Vertex2[1:4]

4

6

7

8

A2=v1v2v3v4v1v2v3v4104178(1).無向圖的鄰接矩陣一定是一個(gè)對稱矩陣.(2).不帶權(quán)的有向圖的鄰接矩陣一般是一個(gè)稀疏矩陣。(3).無向圖的鄰接矩陣的第i行(或第i列)非0或非

元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的度數(shù).(4).有向圖的鄰接矩陣的第i行非0或非元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的出度;第i列非0或非元素的個(gè)數(shù)為第

i個(gè)頂點(diǎn)的入度。特點(diǎn):二.鄰接表存儲方法核心思想:對具有n個(gè)頂點(diǎn)的圖建立n個(gè)線性鏈表存儲該圖.1.每一個(gè)鏈表前面設(shè)置一個(gè)頭結(jié)點(diǎn),用來存放一個(gè)頂點(diǎn)的數(shù)據(jù)信息,稱之為頂點(diǎn)結(jié)點(diǎn).其結(jié)構(gòu)為:vertexlink其中,vertex

域存放某個(gè)頂點(diǎn)的數(shù)據(jù)信息;

link域存放某個(gè)鏈表中第一個(gè)結(jié)點(diǎn)的地址.2.第i個(gè)鏈表中的每一個(gè)鏈結(jié)點(diǎn)(稱之為邊結(jié)點(diǎn))表示以第i

個(gè)頂點(diǎn)為出發(fā)點(diǎn)的一條邊;邊結(jié)點(diǎn)的構(gòu)造為nextweightadjvex其中,next

域?yàn)橹羔樣?

weight

域?yàn)闄?quán)值域(若圖不帶權(quán),則無此域);

adjvex

域存放以第i個(gè)頂點(diǎn)為出發(fā)點(diǎn)的一條邊的另一端點(diǎn)在頭結(jié)點(diǎn)數(shù)組中的位置.n個(gè)頭結(jié)點(diǎn)之間為一數(shù)組結(jié)構(gòu).1234v1v2v3v447861233^^^^

(1).無向圖的第i個(gè)鏈表中邊結(jié)點(diǎn)的個(gè)數(shù)是第i個(gè)頂點(diǎn)度數(shù).(2).有向圖的第i個(gè)鏈表中邊結(jié)點(diǎn)的個(gè)數(shù)是第i個(gè)頂點(diǎn)的出度。特點(diǎn)^^^^1234v1

v3v2v4234332411421v1v2v3v4v1v2v3v46478Typeedgeptr=

edgenode;定義一個(gè)指向結(jié)點(diǎn)的指針類型

edgenode=record定義一個(gè)結(jié)點(diǎn)類型

adjvex:1..n;頂點(diǎn)編號

weight:real;邊的權(quán)值

next:edgeptr;指向下一個(gè)結(jié)點(diǎn)的指針

end;

vexnode=record定義一個(gè)頭結(jié)點(diǎn)類型

vertex:vertype;頂點(diǎn)類型

link:edgeptr;指向第一個(gè)頂點(diǎn)的指針

end;

adj_list=Array[1..n]ofvexnode;定義一個(gè)數(shù)組，數(shù)組內(nèi)容類型為頭結(jié)點(diǎn)類型

鄰接表的類型定義(Pascal)鄰接表的類型定義(C語言)Typeedgeptr=

edgenode;定義一個(gè)指向結(jié)點(diǎn)的指針類型

edgenode=record定義一個(gè)結(jié)點(diǎn)類型

adjvex:1..n;頂點(diǎn)編號

weight:real;邊的權(quán)值

next:edgeptr;指向下一個(gè)結(jié)點(diǎn)的指針

end;

vexnode=record定義一個(gè)頭結(jié)點(diǎn)類型

vertex:vertype;頂點(diǎn)類型

link:edgeptr;指向第一個(gè)頂點(diǎn)的指針

end;

adj_list=Array[1..n]ofvexnode;定義一個(gè)數(shù)組，數(shù)組內(nèi)容類型為頭結(jié)點(diǎn)類型

建立鄰接表的算法：

Procedurebuild_adjlist(var

ga:adj_list)Beginread(n,e);fori:=1tondo[ga[i].vertex:=i;

ga[i].link:=nil;]fork:=1toedo[read(i,j);new(p);

p^.adjvex:=j;p^.next:=ga[i].link;

ga[i].link:=p;]end;1234v1v2v3v46412^^7284^^三.有向圖的十字鏈表存儲方法

(略)

四.無向圖的多重鄰接表存儲方法

(略)關(guān)于逆鄰接表v1v2v3v46478ADEFCBABCDEF^^^^^^12345623461341245123534615例

已知一具有n個(gè)頂點(diǎn)的無向圖G采用鄰接表存儲方法,

寫一算法,刪除圖中數(shù)據(jù)信息為item的那個(gè)頂點(diǎn).需要做的工作:

(1).尋找滿足條件的那個(gè)頂點(diǎn);(2).從頭結(jié)點(diǎn)數(shù)組中刪除該頂點(diǎn);(3).刪除與該頂點(diǎn)相關(guān)的邊;(4).修改有關(guān)的邊結(jié)點(diǎn)的adjvex

域的內(nèi)容。ADEFCBABCDEF^^^^^12345623461341245123534615ADEFCBABDEFF^^123456235131243514^^^procedureDel(g,n,item);begink:=0;fori:=1tondo

if(g[i].vertex=item)then[k:=i;exit;]if(k=0)thenreturn;p:=g[k].link;

fori:=k+1tondo[g[i-1].vertex:=g[i].vertex;g[i-1].link:=g[i].link;]n:=n–1;//頂點(diǎn)的個(gè)數(shù)減1//

while(p<>nil)do[q:=p;p:=p.next;dispose(q);]

fori:=1tondo[p:=g[i].link;while(p<>nil）do

if(p.adjvex=k)then[if(g[i].link=p)then

g[i].link[i]:=p.nextelse

q.next:=p.next;r:=p;p:=p.next;

dispose(r);]else[if(p.adjvex>k)then

p.adjvex:=p.adjvex–1;q:=p;p:=p.next;]]end;

從圖中某個(gè)指定的頂點(diǎn)出發(fā),按照某一原則對圖中所有頂點(diǎn)都訪問且僅訪問一次,得到一個(gè)由圖中所有頂點(diǎn)組成的序列,這一過程稱為圖的遍歷.原則:

從圖中某個(gè)指定的頂點(diǎn)v出發(fā),先訪問頂點(diǎn)v,然后從頂點(diǎn)v未被訪問過的一個(gè)鄰接點(diǎn)出發(fā),繼續(xù)進(jìn)行深度優(yōu)先遍歷,直到圖中與v相通的所有頂點(diǎn)都被訪問;若此時(shí)圖中還有未被訪問過的頂點(diǎn),則從另一個(gè)未被訪問過的頂點(diǎn)出發(fā)重復(fù)上述過程,直到遍歷全圖.一.深度優(yōu)先搜索7.3圖的遍歷

為了標(biāo)記某一時(shí)刻圖中哪些頂點(diǎn)是否被訪問,定義一維數(shù)組visited[1:n],有

1

表示第i個(gè)頂點(diǎn)已經(jīng)被訪問

visited[i]=

0

表示第i個(gè)頂點(diǎn)還未被訪問

13684257123456^^^^^^123456231451672828387878^38^47562345678例：用深度優(yōu)先算法遍歷下圖中的G從V1出發(fā)的訪問序列為：V1,V2,V4,V8,V5,V6,V3,V7深度優(yōu)先遍歷的非遞歸算法：Proceduredfs(g:adj-list；v0:integer)；

Begin

Initstack（s）;write(v0);visited[v0]:=1;p:=g[v0].link;while(p<>nil)or(notempty(s))do[whilep<>nildoIfvisited[p^.adjvex]=1thenp:=p^.next;else[w:=p^.adjvex;write(w);visited[w]:=1;push(s，p);p:=g[w].link;]Ifnotempty(s)then[pop(s，p);p:=p^.next;]]end;二.廣度優(yōu)先搜索原則:

從圖中某個(gè)指定的頂點(diǎn)v出發(fā),先訪問頂點(diǎn)v,然后依次訪問頂點(diǎn)v的各個(gè)未被訪問過的鄰接點(diǎn),然后又從這些鄰接點(diǎn)出發(fā),按照同樣的規(guī)則訪問它們的那些未被訪問過的鄰接點(diǎn)，如此下去，直到圖中與v相通的所有頂點(diǎn)都被訪問;若此時(shí)圖中還有未被訪問過的頂點(diǎn),則從另一個(gè)未被訪問過的頂點(diǎn)出發(fā)重復(fù)上述過程,直到遍歷全圖.13684257123456^^^^^^123456231451672828387878^38^47562345678例：用廣度優(yōu)先算法遍歷下圖中的G從V1出發(fā)的訪問序列為：V1,V2,V3,V4,V5,V6,V7,V8廣度優(yōu)先遍歷的算法如下：

Procedurebfs(g:adj-list;v0:integer);Beginvisited[v0]:=1;write(v0);f:=0;r:=0;p:=g[v0].link;

REPEATWhilep<>nildo[v:=p^.adjvex;if(visited[v]=0)then[r:=r+1;q[r]:=v;write(v);//入隊(duì)并打印

visited[v]:=1;]p:=p^.next;]Iffrthen[f:=f+1;v:=q[f];p:=g[v].link;]UNTIL(p=

)AND(f=r)

end;

可以用深度優(yōu)先搜索或廣度優(yōu)先搜索算法來判斷圖是否連通。在對無向圖進(jìn)行遍歷時(shí)，對于連通圖，僅需要一次搜索過程，圖中的頂點(diǎn)就全部被訪問。對于非連通圖，則需要多次調(diào)用搜索過程，而每次調(diào)用得到的頂點(diǎn)訪問序列恰好為其各個(gè)連通分量中的頂點(diǎn)集。三.求圖的連通分量算法:

procedurecomponent(varg);beginfori:=1tovnumdovisited[i]:=0;count:=0;fori:=1tovnumdoifvisited[I]=0then[count:=count+1;dfs(g,i);]end;7.4最小生成樹和最短路徑問題

帶權(quán)連通圖中,總的權(quán)值之和最小的帶權(quán)生成樹為最小生成樹.最小生成樹也稱最小代價(jià)生成樹,或最小花費(fèi)生成樹.構(gòu)造網(wǎng)的最小生成樹的依據(jù)：在網(wǎng)中選擇n-1條邊，連接網(wǎng)的n個(gè)頂點(diǎn)；2.盡可能選取權(quán)值為最小的邊。最小生成樹的概念：最小生成樹問題v4v2v6v5v3v116115691814192220最小生成樹的權(quán)值

=56Kruskal算法：

1.設(shè)T的初態(tài)為空集；

2.當(dāng)T中邊數(shù)小于n-1時(shí)做下列工作①從E中選取權(quán)值為最小的邊(v,w)，并刪除之；②若(v,w)不和T中的邊一起構(gòu)成回路，則將邊(v,w)加入到T中去。1246536536215465124653①T為空124653②選權(quán)值最小的邊(1,3)

從E中將其刪去11246531③選E中最小的邊(4,6)從E中將其刪去212465312④從E中選最小的邊(2,5)從E中將其刪去3124653123⑤從E中選最小的邊(3,6)從E中將其刪去4⑥從E中選最小的邊(3,4)，但加入T后會使T中出現(xiàn)回路，所以邊(3,4)不可取，把邊(3,4)從E中刪除。再看(1,4)同樣會使T構(gòu)成回路，仍不可取，從E中刪去(1,4)，選(2,3)，從E中刪去(2,3),最后已夠5條邊了，這樣生成樹就是最小生成樹。最小生成樹可能不唯一，但權(quán)的總數(shù)相同。24653123415算法的思想明確、也很簡單，但具體實(shí)現(xiàn)時(shí)比較困難，需要解決一些具體的問題，譬如如何所選的新邊沒有和已選的邊構(gòu)成回路。算法討論：Prim算法：

1.設(shè)V(T)的初態(tài)為空集(V(T)為落在生成樹上的頂點(diǎn)集合);2.在連通圖上任選一頂點(diǎn)加入到V(T)集合中去；

3.將下列步驟重復(fù)n-1次：①在i屬于V(T)，j不屬于V(T)的邊中，選權(quán)值最小的邊

(i,j)；②將頂點(diǎn)j加入到V(T)中去；③輸出i,j及Wij。例：①初態(tài)V(T)=φ

②選①頂點(diǎn)=>V(T)=｛1｝③做n-1次1)邊(1,2)的權(quán)值最小，∴將②=>V(T)=｛1,2｝;write(1,2)weight161246532)邊(2,3)的權(quán)值最小，∴將③=>V(T)=｛1,2,3｝;write(2,3)weight53)邊(3,4)的權(quán)值最小，∴將④=>V(T)=｛1,2,3,4｝;write(3,4)weight6165618192111143364)邊(2,6)的權(quán)值最小，∴將⑥=>V(T)=｛1,2,3,4,6｝;write(2,6)weight115)邊(4,5)的權(quán)值最小，∴將⑤=>V(T)=｛1,2,3,4,5,6｝;write(4,5)weight18∑i=16Weight=5612465316561819211114336124653165618117.5最短路徑問題一.路徑長度的定義1.不帶權(quán)的圖:路徑上所經(jīng)過的邊的數(shù)目。2.帶權(quán)的圖:路徑上所經(jīng)過的邊上的權(quán)值之和.二.問題的提出設(shè)出發(fā)頂點(diǎn)為v(通常稱為源點(diǎn))。確定源點(diǎn)到其他各頂點(diǎn)的最短路徑，常應(yīng)用于選擇路線，架設(shè)電線等.013524455010201015152033530v0是源點(diǎn)最短路徑v0→v210v0→v2→v310+15=25v0→v2→v3→v110+15+20v0→v445v0→v5無路可走從以上可以發(fā)現(xiàn)每一條最短路徑中間所經(jīng)過的頂點(diǎn)具有如下特點(diǎn)：下一條最短路徑(設(shè)其終點(diǎn)為x)可能是<v0,x>,或者<v0,u,…,v,x>，而u,…,v都是已求得的最短路徑終點(diǎn)。例假設(shè)S為已求得的最短路徑的終點(diǎn)的集合(S初態(tài)為空集)，則下一條長度次短的最短路徑（設(shè)終點(diǎn)為x）：或者是弧<v0,x>；或者是中間經(jīng)過S集合中頂點(diǎn)，最后到達(dá)頂點(diǎn)x的路徑。Dijkstra算法思想：2.設(shè)置一個(gè)標(biāo)志數(shù)組S[1:n]記錄源點(diǎn)v到圖中哪些頂點(diǎn)的最短路徑已經(jīng)找到，有：

1表示源點(diǎn)到頂點(diǎn)i的最短路徑已經(jīng)找到

S[i]=

0

表示源點(diǎn)到頂點(diǎn)i的最短路徑尚未找到初始時(shí)，

S[V0]=1,S[i]=0

i=1,2,,niv{3.設(shè)置數(shù)組dist[1:n]分別記錄源點(diǎn)V0

到圖中各頂點(diǎn)的最短路徑的路徑長度，其中，dist[i]記錄源點(diǎn)到頂點(diǎn)i的最短路徑的長度；初始時(shí)，dist數(shù)組的值為鄰接矩陣第V0行的n個(gè)元素值。

4.設(shè)置數(shù)組path[1:n]分別記錄源點(diǎn)V0

到圖中各頂點(diǎn)的最短路徑所經(jīng)過的頂點(diǎn)序列，其中，path[i]記錄源點(diǎn)到頂點(diǎn)i的路徑，初始時(shí)，path[i]=

V0

,

i=1,2,3,,n三.解決問題所需要確定的數(shù)據(jù)結(jié)構(gòu)1.圖的存儲:設(shè)cost為帶權(quán)的鄰接矩陣

當(dāng)頂點(diǎn)vi到頂點(diǎn)vj

有邊,且權(quán)為Wij

時(shí)，則

cost[i，j]=Wij

當(dāng)頂點(diǎn)vi到頂點(diǎn)vj無邊時(shí)cost[i,j]=

0

當(dāng)vi=vj

時(shí)

四.算法(用自然語言表達(dá))1.

確定dist、S、path三個(gè)數(shù)組的初值。2.利用S數(shù)組與dist數(shù)組在那些尚未找到最短路徑的頂點(diǎn)中確定一個(gè)與源點(diǎn)最近的頂點(diǎn)u,即dist值最小的頂點(diǎn)并置

S[u]為1，同時(shí)將頂點(diǎn)u加入path[u].3.根據(jù)頂點(diǎn)u修改源點(diǎn)到所有尚未找到最短路徑的頂點(diǎn)的路徑長度。即

1）將源點(diǎn)V0到頂點(diǎn)u的(最短)路徑長度分別加到源點(diǎn)

V0通過頂點(diǎn)u可以直接到達(dá)、且尚未找到最短路徑那些的頂點(diǎn)的路徑長度上;若加后的長度小于原來V0到某頂點(diǎn)r的路徑長度，則用加后的長度替代原來的長度，否則不替代。

2）若替代，將源點(diǎn)V0到頂點(diǎn)u的路徑(最短路徑)上經(jīng)過的所有頂點(diǎn)替換path[r].4.重復(fù)第2至第3步n-1次。fori1tondo

dist[i]cost[v,i]end

S[i]0S[v]1

path[i]{v}

Floyed算法思想：從i到j(luò)的路徑上每次增加一個(gè)結(jié)點(diǎn)k，看這個(gè)增加了一個(gè)結(jié)點(diǎn)k的新路徑的長度是否比原來的路徑長度小，若小,則以新路徑代之,否則保持原路徑。A(k)[i,j]=min{A(k-1)[i,j],A(k-1)[i,k]+A(k-1)[k,j]}(1≤k≤n)算法計(jì)算公式：其中:A(k)[i,j]表示頂點(diǎn)i,j之間的中間點(diǎn)的序號不大于k的最短距離;

由于G中頂點(diǎn)編號不大于n，所以最后到了An[i,j]就代表i到j(luò)的最短路徑之長。算法描述：procedureall_path(cost);Beginfori:=1tondoforj:=1tondo[a[i,j]:=cost[i,j];

if(i<>j)and(a[i,j]<max)then

path[i,j]=[i]+[j]]fork:=1tondofori:=1tondoforj:=1tondoifa[i,k]+a[k,j]<a[i,j]then[a[i,j]:=a[i,k]+a[k,j];

path[i,j]:=path[i,k]+path[k,j];]End;cost=04116023∞0cost:帶權(quán)鄰接矩陣A：最短路徑長度P：相應(yīng)的路徑例：641132ABC321初態(tài)K=0時(shí)，A(0)123

1

2

304116023∞0

ABACPath(0)123

1

2

3BABCCA

K=1時(shí)，A(1)123Path(1)123104111ABAC26022BABC33703CACABK=2時(shí)，A(2)123Path(2)12310461ABABC26022BABC33703CACABK=3時(shí)，A(3)123Path(3)12310461ABABC25

022BCABC33703CACAB★AOV網(wǎng)與拓?fù)渑判蛞?什么是AOV網(wǎng)驗(yàn)收籌備招標(biāo)備料進(jìn)駐工地測量挖地基澆注水泥搭架子…例1程序語言數(shù)據(jù)結(jié)構(gòu)離散數(shù)學(xué)軟件工程操作系統(tǒng)編譯原理數(shù)據(jù)庫計(jì)算機(jī)組成匯編網(wǎng)絡(luò)數(shù)字邏輯計(jì)算機(jī)導(dǎo)論例2二.AOV網(wǎng)的定義

在AOV網(wǎng)中，若頂點(diǎn)i到頂點(diǎn)j之間有有向路徑，則稱頂點(diǎn)i為頂點(diǎn)j的前驅(qū)，頂點(diǎn)j為頂點(diǎn)i的后繼；若頂點(diǎn)i到頂點(diǎn)j之間為一條有向邊，則稱頂點(diǎn)i為頂點(diǎn)j

的直接前驅(qū)，頂點(diǎn)j為頂點(diǎn)i的直接后繼。以頂點(diǎn)表示活動，以有向邊表示活動之間的優(yōu)先關(guān)系的有向圖稱為AOV網(wǎng)。三.拓?fù)渑判?/p>

檢查AOV網(wǎng)是否存在回路的方法是對AOV網(wǎng)進(jìn)行拓?fù)渑判颍瑯?gòu)造一個(gè)序列，使得該序列滿足條件：

1.若在AOV網(wǎng)中，頂點(diǎn)i優(yōu)先于頂點(diǎn)j,則在該序列中也是頂點(diǎn)i優(yōu)先于頂點(diǎn)j。

2.若在AOV網(wǎng)中，頂點(diǎn)i與頂點(diǎn)j之間不存在優(yōu)先關(guān)系,則在該序列中建立它們的優(yōu)先關(guān)系，即頂點(diǎn)i優(yōu)先于頂點(diǎn)j，或頂點(diǎn)j優(yōu)先于頂點(diǎn)i。

3.若能夠構(gòu)造出拓?fù)湫蛄?，則拓?fù)湫蛄邪珹OV網(wǎng)的全部頂點(diǎn)。

四.拓?fù)渑判蚍椒?/p>

1.從AOV網(wǎng)中任選擇一個(gè)沒有前驅(qū)(入度為0)的頂點(diǎn)；

2.從AOV網(wǎng)中去掉該頂點(diǎn)以及以該頂點(diǎn)為出發(fā)點(diǎn)的所有邊；

3.重復(fù)上述過程，直到網(wǎng)中的所有頂點(diǎn)都被去掉,或者網(wǎng)中還有頂點(diǎn)，但不存在入度為0的頂點(diǎn)；

前者說明AOV網(wǎng)中無回路，后者說明AOV網(wǎng)中存在回路。v1v4v3v2v6v5v7v1v5v7v3v6v2v4例v4v3v2v6v7v4v3v2v6v5v7v4v3v2v7v4v3v7v4v7v7★AOE網(wǎng)與關(guān)鍵路徑籌備付款簽合同做預(yù)置件驗(yàn)收施工…招標(biāo)7天聯(lián)系材料8天圖紙?jiān)O(shè)計(jì)15天進(jìn)駐工地4天運(yùn)材料6天搬運(yùn)3天例一.AOE網(wǎng)的定義

AOE網(wǎng)為一個(gè)帶權(quán)的有向無環(huán)圖，其中，頂點(diǎn)表示事件，有向邊表示活動，邊上的權(quán)值表示活動持續(xù)的時(shí)間。v1v4v2v3v5v7v9v8v6a1a2a3a4a5a6a7a8a9a10a1164511297244

正常情況下，AOE網(wǎng)中只有一個(gè)入度為0的頂點(diǎn)，稱