《數(shù)據(jù)結構》課件第7章(圖)

★基本術語

圖是由頂點的非空有窮集合與頂點之間關系(邊或弧)的集合構成的結構,通常表示為

G=(V,E)其中,V為頂點集合,E為關系(邊或弧)的集合.一.圖的定義(b)這條邊依附于頂點vi和vj。(vi,vj)<vi,vj>vjvivjvi

關于一條邊或弧的表示方法:(1)

用圖形:(2)用符號:(3)

用語言:(a)

頂點vi與vj是這條邊的兩個鄰接點。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)

無向圖：

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

網(wǎng)(絡)：v1v2v3v4v1v2v3v4v1v2v3v41041781.頂點的度對于有向圖而言,有:

頂點的出度:

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

頂點的入度:

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

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

邊的數(shù)目達到最大的圖稱為完全圖.邊的數(shù)目達到或接近最大的圖稱為稠密圖,否則,稱為稀疏圖.

具有n個頂點的有向圖最多有n(n-1)條邊.

具有n個頂點的無向圖最多有n(n-1)/2條邊.

對于具有n個頂點,e條邊的圖,有

2e=TD(vi)ni=1結論1結論2結論32.

路徑DCEBAP(A,E):

A,B,EA,C,D,E

出發(fā)點與終止點相同的路徑稱為回路或環(huán)；頂點序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑。不帶權的圖的路徑長度是指路徑上所經(jīng)過的邊的數(shù)目，帶權的圖的路徑長度是指路徑上經(jīng)過的邊上的權值之和。

頂點vx到vy之間有路徑P(vx,vy)的充分必要條件為:存在頂點序列vx,vi1,vi2,…,vim,vy,并且序列中相鄰兩個頂點構造的頂點偶對分別為圖中的一條邊。3.子圖v1v2v3v4

對于圖G=(V,E)與G′=(V′,E′),若有V′V,E′E,則稱G′為G的一個子圖.v1v2v3v4v1v24.圖的連通

無向圖中頂點vi到vj有路徑,則稱頂點vi與vj是連通的。若無向圖中任意兩個頂點都連通,則稱該無向圖是連通的。

若有向圖中頂點vi到vj有路徑,并且頂點vj到vi也有路徑,則稱頂點vi與vj是連通的。若有向圖中任意兩個頂點都連通,則稱該有向圖是強連通的。(1)無向圖的連通(2)有向圖的連通5.生成樹

包含具有n個頂點的連通圖G的全部n個頂點,僅包含其n-1條邊的連通子圖稱為G的一個生成樹。v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2對于一個圖,需要存儲的信息應該包括:(1)所有頂點的數(shù)據(jù)信息；(2)頂點之間關系(邊或弧)的信息;(3)權的信息。★圖的存儲結構一.鄰接矩陣存儲方法1.定義一個一維數(shù)組VERTEX[1:n]存放圖中所有頂點的數(shù)據(jù)信息.2.定義一個二維數(shù)組A[1:n,1:n]存放圖中所有頂點之間關系的信息(該數(shù)組被稱為鄰接矩陣),有

1

當頂點vi到頂點vj有邊時A[i][j]=

0

當頂點vi到頂點vj無邊時對于帶權的圖,有

wij

當頂點vi到頂點vj有邊,且邊的權為wij

A[i][j]=

當頂點vi到頂點vj無邊時oo0111101111011110A1=v1v2v3v4Vertex1[1:4]v1v2v3v4Vertex2[1:4]467

8

A2=v1v2v3v4v1v2v3104178鄰接矩陣的類型定義如下:#defineVnum圖的頂點數(shù)enumadj{0,1};typedefadj_adjmatrix[vnum][vnum]adjmatrix;typedefstruct{VexTypeVexs[Vnum];//頂點的信息

adjmatrixarcs;//鄰接矩陣}graph;建立無向網(wǎng)鄰接矩陣的算法如下:voidbuild-graph(graph&ga){for(i=0;i<n;i++)scanf(“%d”,ga.Vexs[i]);for(i=0;i++;i<n)for(j=0;j++;j<n)ga.arcs[i][j]=maxint;for(k=0;k++;k<e)//讀入邊(i,j)和權

{scanf(“%d,%d,%d”,i,j,w);ga.arcs[i][j]=w;ga.arcs[j][i]=w;}}

(1)無向圖的鄰接矩陣一定是一個對稱矩陣;(2)不帶權的有向圖的鄰接矩陣一般是一個稀疏矩陣;(3)無向圖的鄰接矩陣的第i行(或第i列)非0或非元素的個數(shù)為第i個頂點的度數(shù);(4)有向圖的鄰接矩陣的第i行非0或非元素的個數(shù)為第i個頂點的出度;第i列非0或非元素的個數(shù)為第

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

域存放某個頂點的數(shù)據(jù)信息;

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

個頂點為出發(fā)點的一條邊;邊結點的構造為nextweightadjvex其中,next

域為指針域;

weight

域為權值域(若圖不帶權,則無此域);

adjvex

域存放以第i個頂點為出發(fā)點的一條邊的另一端點在頭結點數(shù)組中的位置.n個頭結點之間為一數(shù)組結構.1234v1v2v3v447861233^^^^(1)無向圖的第i個鏈表中邊結點的個數(shù)是第i個頂點度數(shù).(2)有向圖的第i個鏈表中邊結點的個數(shù)是第i個頂點的出度。特點:^^^^1234v1v3v2v4234332411421v1v2v3v4v1v2v3v46478typedefstructedgenode{intadjvex;//該邊所指向的頂點的序號

floatweight;//邊上的權值

structedgenode*next;//指向下一條弧的指針}*edgeptr;typedefstruct{VerTypevertex;edgeptrlink;}vexnode;typedefvexnodeAdj_List[MAX_VERTEX_NUM];

鄰接表的類型定義

voidbuild_adjlist(Adj_Listga){scanf(“%d,%d”,&n,&e);//讀入頂點數(shù)，邊數(shù)efor(i=0;i<n;i++)//初始化鄰接表

{ga[i].vertex=i;ga[i].link=NULL;}for(k=0;k<e;k++){scanf(“%d,%d”,&i,&j);//讀入頂點對<i,j>p=newstructedgenode;p->adjvex=j;p->next=ga[i].link;ga[i].link=p;}}建立圖的鄰接表的算法：1234v1v2v3v46412^^7284^^關于逆鄰接表v1v2v3v46478三.十字鏈表存儲方法

在用鄰接表表示有向圖時，有時需要同時使用鄰接表和逆鄰接表。用有向圖的十字鏈表可把這兩個結合起來表示。

其中，tail和head

分別表示弧的尾頂點和頭頂點；dut是弧的權值；hlink

鏈接以head為頭的另一條弧；tlink鏈接以tail為尾的另一條弧。另外，設立一個由n個表頭結點構成的向量，每個表頭結點存放一個頂點，其結構也由上述五個域組成，head域存放該頂點的入度；tail域存放出度;hlink鏈接以該頂點為頭的??；tlink鏈接以該頂點為尾的弧。tailheadduttlinkhlink0030300000126347002322450000348001^^^^^21436781234123452^^^

在鄰接多重表中,每一條邊只有一個邊結點。邊結點的結構如下：

markvertex1vertex2path1path2

其中,mark是記錄是否處理過的標記;vertex1和vertex2是該邊兩頂點位置。path1域指向下一條依附于頂點vertex1的邊；path2是指向下一條依附于頂點vertex2的邊。四.鄰接多重表存儲方法

頂點結點的結構存儲頂點信息的結點表以順序表方式組織,每一個頂點結點有兩個數(shù)據(jù)域：其中，data存放與該頂點相關的信息，F(xiàn)irstout是指示第一條依附該頂點的邊的指針。在鄰接多重表中,所有依附于同一個頂點的邊都鏈接在同一個單鏈表中。dataFirstout

從頂點i出發(fā),可以循鏈找到所有依附于該頂點的邊，也可以找到它的所有鄰接頂點。ADEFCBABCDEF^^^^^^12345623461341245123534615例：已知一具有n個頂點的無向圖G采用鄰接表存儲方法,

寫一算法,刪除圖中數(shù)據(jù)信息為item的那個頂點.需要做的工作:(1)尋找滿足條件的那個頂點;(2)從頭結點數(shù)組中刪除該頂點;(3)刪除與該頂點相關的邊;(4)修改有關的邊結點的adjvex域的內(nèi)容。ADEFCBABCDEF^^^^^12345623461341245123534615ADEFCBABDEFF^^123456235131243514^^^voidDel(g,n,item){k=0;for(i=1;i<=n;i++)if(g[i].vertex==item){k=i;break;}if(k==0)return;p=g[k].link;

for(i=k+1;i<=n;i++){g[i-1].vertex=g[i].vertex;g[i-1].link=g[i].link;}n=n–1;//頂點的個數(shù)減1//while(p!=null){q=p;p=p->next;deleteq;}

for(i=1;i<=n;i++){p=g[i].link;while(p!=null）

if(p->adjvex==k){if(g[i].link==p)g[i].link[i]=p->next;elseq->next:=p->next;r=p;p=p->next;deleter;}else{if(p->adjvex>k)p->adjvex=p->adjvex–1;q=p;p=p->next;}}}

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

從圖中某個指定的頂點v出發(fā),先訪問頂點v,然后從頂點v未被訪問過的一個鄰接點W1出發(fā),訪問了頂點W1后，再從W1出發(fā)，訪問和W1鄰接且未被訪問過的任意頂點W2，然后從W2出發(fā)進行如上訪問，重復，直到某一頂點所有鄰接點都被訪問過時，接著退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)，重復上述過程，直到所有的被訪問過的頂點的鄰接點都已被訪問為止。一.深度優(yōu)先搜索★圖的遍歷

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

1

表示第i個頂點已經(jīng)被訪問

visited[i]=

0

表示第i個頂點還未被訪問例如：用深度優(yōu)先搜索法遍歷下圖。123456782

3^1

4

5^1

6

7^2

8^2

8^3

8^3

8^4

5

6

7^V1V2V3V4V5V6V7V812345678voiddfs(Adj_Listg,intv0)｛//從v0出發(fā)，深度優(yōu)先遍歷圖g，g以鄰接表為存儲結構

printf(“%d”,v0);visited[v0]=1;//標志v0已訪問

p=g[v0].link;//找v0的第一個鄰接點

while(p!=NULL){if(visited[p->adjvex]==0)dfs(g,p->adjvex);p=p->next;//回溯—找v0的下一個鄰接點

}}深度優(yōu)先搜索的遞歸算法：voiddfs(Adj_Listg,intv0)｛top=0;printf(“%d”,v0);visited[v0]=1;//標志v0已訪問

p=g[v0].link;//找v0的第一個鄰接點

while(p!=NULL||top>0){while(p!=NULL){if(visited[p->adjvex]==1)p=p->next;//找v0的下一個鄰接點

else{w=p->adjvex;printf(“%d”,w);visited[w]=1;top++;S[top]=p;p=g[w].link;}}if(top>0){p=S[top];top--;p=p->next;}}}深度優(yōu)先搜索的非遞歸算法：

分析上述過程,在遍歷圖時,對圖中每個頂點至多調(diào)用一次dfs過程，因為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。因此，遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構，當用二維數(shù)組表示鄰接矩陣作圖的存儲結構時，查找每個頂點的鄰接點所需時間為O(n2),其中n為圖中頂點數(shù);而當以鄰接表作圖的存儲結構時，查找鄰接點所需時間為O(e)，其中e為無向圖中的邊數(shù)或有向圖中弧的個數(shù)。因此，當以鄰接表作存儲結構時，深度優(yōu)先搜索遍歷圖的時間復雜度為O(n+e)。深度優(yōu)先搜索遍歷算法的復雜性分析：二.廣度優(yōu)先搜索原則:

從圖中某個指定的頂點v出發(fā),先訪問頂點v,然后依次訪問頂點v的各個未被訪問過的鄰接點W1,W2,…,Wt，然后再依次訪問W1,W2,…,Wt的所有的未被訪問過的鄰接點，再從這些被訪問的頂點出發(fā)，逐次進行訪問，直到所有頂點都被訪問到為止。12345678例如右圖：從V1出發(fā)，V1訪問了;

再訪問與V1鄰接的V2，V3;

然后再訪問與V2鄰接的V4、V5，與V3鄰接的V6、V7;

再訪問與V4鄰接的V8則所有的頂點都被訪問到了因此遍歷結束。遍歷的順序是：V1→V2→V3→V4→V5→V6→V7→V8

①對于廣度優(yōu)先搜索的方法，我們用不著去記錄所走過的路徑。我們只需記錄與每一個頂點相鄰接的所有頂點，而且當訪問完這些頂點時，按照先記錄先搜索的方式，對被記錄的頂點進行廣度優(yōu)先搜索。（即若W1在W2之前被訪問，則W1的鄰接點也在W2的鄰接點之前被訪問。）所以我們用一個隊列Q來記錄這些頂點是比較方便的（依次存放被訪問的結點）。②和dfs算法一樣，在這里也需要一個輔助函數(shù)Visited[W]來標志頂點是否被訪問過。③我們?nèi)约僭O圖用鄰接表來表示。算法：voidbfs(Adj_Listg,intv0)//g為圖的鄰接矩陣或鄰接表，從V0出發(fā)，用廣度優(yōu)先搜索法//遍歷圖，visited[w]為標志向量，其初值為0{visited[v0]=1;printf(“%d”,v0);f=0;r=0;p=g[v0].link;do{while(p!=NULL){v=p->adjvex;if(visited[v]==0){q[r]=v;r++;printf(“%d”,v);visited[v]=1;}p=p->next;//找某一頂點的所有鄰接點并進隊

}if(f!=r)//v出隊

{v=q[f];f++;p=g[v].link;}}while((p!=NULL)||(f!=r))}

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

{intcount;

for(v=0;v<n;v++)/*初始化visited數(shù)組

visited[v]=0;

count=0;

for(v=0;v<n;v++)

if(visited[v]==0)

{count++;

dfs(g,v);

}returncount;}

★最小生成樹和最短路徑問題

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

=56Kruskal算法：

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

2.當T中邊數(shù)小于n-1時做下列工作①從E中選取權值最小的邊(v,w)，并刪除之；②若(v,w)不和T中的邊一起構成回路，則將邊(v,w)加入到T中去。1246536536215465124653①T為空124653②選權值最小的邊(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構成回路，仍不可取，從E中刪去(1,4)，選(2,3)，從E中刪去(2,3),最后已夠5條邊了，這樣生成樹就是最小生成樹。最小生成樹可能不唯一，但權的總數(shù)相同。24653123415

算法的思想明確、也很簡單，但具體實現(xiàn)時比較困難，需要解決一些具體的問題，譬如如何所選的新邊沒有和已選的邊構成回路。算法討論：Prim算法：

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

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

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

②選①頂點=>V(T)=｛1｝③做n-1次1)邊(1,2)的權值最小，∴將②=>V(T)=｛1,2｝;weight(1,2)=161246532)邊(2,3)的權值最小，∴將③=>V(T)=｛1,2,3｝;

weight

(2,3)=53)邊(3,4)的權值最小，∴將④=>V(T)=｛1,2,3,4｝;

weight(3,4)=6165618192111143364)邊(2,6)的權值最小，∴將⑥=>V(T)=｛1,2,3,4,6｝;

weight(2,6)=115)邊(4,5)的權值最小，∴將⑤=>V(T)=｛1,2,3,4,5,6｝;

weight(4,5)=18∑i=16Weight=561246531656181921111433612465316561811最短路徑問題:一.路徑長度的定義1.不帶權的圖:路徑上所經(jīng)過的邊的數(shù)目。2.帶權的圖:路徑上所經(jīng)過的邊上的權值之和.二.問題的提出三.解決問題所需要確定的數(shù)據(jù)結構1.圖的存儲:以1~n分別代表n個頂點,采用鄰接矩陣存儲該圖,有

Wij

當頂點vi到頂點vj有邊,且權為Wij

A[i,j]=

當頂點vi到頂點vj無邊時

0

當vi=vj時

設出發(fā)頂點為v(通常稱為源點)。確定源點到其他各頂點的最短路徑，常應用于選擇路線，架設電線等.2.設置一個標志數(shù)組S[1:n]記錄源點v到圖中哪些頂點的最短路徑已經(jīng)找到，有：

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

S[i]=

0

表示源點到頂點i的最短路徑尚未找到初始時，

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

i=1,2,,niv{3.設置數(shù)組dist[1:n]分別記錄源點v到圖中各頂點的最短路徑的路徑長度，其中，dist[i]記錄源點到頂點i的最短路徑的長度；初始時，dist數(shù)組的值為鄰接矩陣第v行的n個元素值。

4.設置數(shù)組path[1:n]分別記錄源點v到圖中各頂點的最短路徑所經(jīng)過的頂點序列，其中，path[i]記錄源點到頂點i的路徑，初始時，path[i]=v,

i=1,2,3,,n013524455010201015152033530v0是源點最短路徑v0→v210v0→v2→v310+15=25v0→v2→v3→v110+15+20v0→v445v0→v5無路可走

從以上可以發(fā)現(xiàn)每一條最短路徑中間所經(jīng)過的頂點具有如下特點：下一條最短路徑(設其終點為x)可能是<v0,x>,或者<v0,u,…,v,x>，而u,…,v都是已求得的最短路徑終點。例

假設S為已求得的最短路徑的終點的集合(S初態(tài)為空集)，則下一條長度次短的最短路徑（設終點為x）：或者是弧<v0,x>；或者是中間經(jīng)過S集合中頂點，最后到達頂點x的路徑。Dijkstra算法思想：四.算法(用自然語言表達)

b)設S為已找到從v0出發(fā)的最短路徑的終點的集合,它的初態(tài)為源點（v0)。

c)設從v0出發(fā)到G中其余各頂點(終點)vi的最短路徑長度為：初態(tài)→dist[i]=cost[v0,vi]Vi∈V(G)②選擇u，使dist[u]=Min｛dist[i]|vi不屬于S,vi∈V(G)}

（則u為目前求得的一條從v0出發(fā)的最短路徑的終點）令S=S∪｛u｝（u進入s）

①設cost為帶權的鄰接矩陣

a)cost<i,j>=<i,j>上的權值(i,j之間有弧)∞(i,j之間無弧)｛

③修改所有不在S的終點的最短路徑的長度，若

dist[u]+cost[u,i]<dist[i]，則修改dist[i]為dist[i]=dist[u]+cost[u,i]同時修改相應的路徑.④重復操作②③共n-1次，由此求得從v0到G中其余各頂點的最短路徑是依路徑長度遞增的序列。voidshortpath(cost,v0)/*求從源點v0到其它各頂點的最短路徑,cost為有向圖的帶權鄰接矩陣，v0為其中某個頂點的編號；dist[i]為當前找到的從v0到i的最短路徑長度；path[i]為相應的路徑；max為計算機內(nèi)允許的最大值*/

{for(i=0;i<n;i++){dist[i]=cost[v0][i];

if(dist[i]<max)path[i]=[v0]+[i];//[]表示集合，+表示兩個集合相并

elsepath[i]=[];//[]表示為空集

}//建立dist及path的初態(tài)

s=char(v0);num=0;//s為已找到最短路徑的終點的集合

while(num<n-1){wm=max;u=v0;for(i=0;i<n;i++)//選dist[i]的最小值

if(!(iins)&&dist[i]<wm)//若i不屬于s且dist[i]<wm{u=i;wm=dist[i];}//按dist[i]的最小值選取了us=s+[u];//將u加入最短路徑的終點集合sfor(i=0;i<n;i++)//修改dist和past的值

if(!(iins)&&dist[u]+cost[u][i]<dist[i])//若i不屬于s{dist[i]=dist[u]+cost[u][i];path[i]=path[u]+[i];}num++;}}

算法執(zhí)行時間：第一個FOR循環(huán)是O(n)，接下來循環(huán)共進行n-1次，每一次執(zhí)行時間是O(n)，所以總的時間為O(n2)。Floyed算法思想：

從i到j的路徑上每次增加一個結點k，看這個增加了一個結點k的新路徑的長度是否比原來的路徑長度小，若小,則以新路徑代之,否則保持原路徑。A(k)[i][j]=min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}(1≤k≤n)

算法計算公式：其中:A(k)[i][j]表示頂點i,j之間的中間點的序號不大于k的最短距離;

由于G中頂點編號不大于n，所以最后到了An[i][j]就代表i到j的最短路徑之長。算法描述：voidall_path(cost){for(i=1;i<=n;i++)for(j=1;j<=n;j++){a[i][j]=cost[i][j];if((i!=j)&&(a[i][j]<max)path[i][j]=[i]+[j];}

for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i,k]+a[k,j]<a[i,j]){a[i][j]=a[i][k]+a[k][j];path[i][j]=path[i][k]+path[k][j];}}cost=04116023∞0cost:帶權鄰接矩陣A：最短路徑長度P：相應的路徑

例：641132ABC321初態(tài)K=0時，A(0)12312

304116023∞0

ABACPath(0)12312

3BABCCA

K=1時，A(1)123Path(1)123104111ABAC26022BABC33703CACABK=2時，A(2)123Path(2)12310461ABABC26022BABC33703CACABK=3時，A(3)123Path(3)12310461ABABC25022BCABC33703CACAB★AOV網(wǎng)與拓撲排序一.AOV網(wǎng)舉例：驗收籌備招標備料進駐工地測量挖地基澆注水泥搭架子…例1程序語言數(shù)據(jù)結構離散數(shù)學軟件工程操作系統(tǒng)編譯原理數(shù)據(jù)庫計算機組成匯編網(wǎng)絡數(shù)字邏輯計算機導論例2二.AOV網(wǎng)的定義

以頂點表示活動，以有向邊表示活動之間的優(yōu)先關系的有向圖稱為AOV網(wǎng)。

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

三.拓撲排序

檢查AOV網(wǎng)是否存在回路的方法是對AOV網(wǎng)進行拓撲排序，構造一個序列，使得該序列滿足條件：

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

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

3.若能夠構造出拓撲序列，則拓撲序列包含AOV網(wǎng)的全部頂點。

四.拓撲排序方法1.從AOV網(wǎng)中任選擇一個沒有前驅(入度為0)的頂點；2.從AOV網(wǎng)中去掉該頂點以及以該頂點為出發(fā)點的所有邊；3.重復上述過程，直到網(wǎng)中的所有頂點都被去掉,或者網(wǎng)中還有頂點，但不存在入度為0的頂點。

五.算法思想

建立一個棧（這個棧存放入度為0的結點）檢查鄰接表，將所有入度為零的頂點送棧，隨后輸出入度為0的頂點。Vj輸出時，將Vj的直接后繼Vk(k=1,2,,…)的入度減1，并將入度減到零的頂點進棧。當棧為空時，則檢查一下是否輸出了有向圖的全部頂點（n個）：若是，則排序結束；反之，則網(wǎng)中有環(huán)。一個好的算法，一般在時空兩個方面都應盡量的節(jié)約，對于拓撲排序算法，我們可以另開辟一塊空間作為棧，還可以想辦法利用它現(xiàn)有的存儲空間，形成一個鏈棧。v1v4v3v2v6v5v7v1v5v7v3v6v2v4例v4v3v2v6v7v4v3v2v6v5v7v4v3v2v7v4v3v7v4v7v7v1v4v3v2v6v5v7357^123456v1v2v3v4v5v6^7002111v7334^^7^6^7^voidtoposort(Adj_Listg)

/*假設G為有n個頂點,e條弧的有向圖,g是它的鄰接表的表頭向量，每個分量有三個域vex,in,next，對入度為0的頂點設計帶鏈的棧，top指示棧頂元素，in為入度*/{readlist();//輸入e條弧并建立鄰接表

top=0;

for(i=1;i<=n;i++)//查入度為零的頂點，并建立鏈棧

if(g[i].in==0){g[i].in=top;top=i;}m=0;//設m為計數(shù)器計算輸出的頂點個數(shù)while(top!=0){j=top;top=g[top].in;//退棧printf(“v%d”,j);m++;//輸出頂點并計數(shù)

q=g[j].link;//q是指針，指示以j為尾的弧

while(q!=NULL){k=q->vex;//頂點k為j的直接后繼

g[k].in=g[k].in-1;//入度減1if(g[k].in==0){g[k].in=top;top=k;//入度為零的頂點進棧}q=q->next;}}if(m<n)printf(“thenetworkhavecycle”);//輸出頂點數(shù)不足n，說明網(wǎng)中有環(huán)

}

假設有向圖有n個頂點，e條邊，那么建立鄰接表的執(zhí)行時間為O(e)；搜索入度為0的時間為O(n)；在拓撲排序過程中，若有向圖無環(huán)，則每個頂點進一次棧，入度減1的運算在WHILEtop≠0的語句中共執(zhí)行e次，所以總的執(zhí)行時間為O(n+e)。當有向圖中無環(huán)時，也可利用深度優(yōu)先搜索進行拓撲排序。因為圖中無環(huán),則由圖中某點出發(fā)進行深度優(yōu)先搜索遍歷時，最先退出dfs過程的頂點，即出度為0的頂點，是拓撲有序序列中最后一個頂點。由此，按退出dfs(深度)過程的先后記錄下來的頂點序列，即為逆向的拓撲有序序列。

六.復雜性分析★AOE網(wǎng)與關鍵路徑籌備付款簽合同做預置件驗收施工…招標7天聯(lián)系材料8天圖紙設計15天進駐工地4天運材料6天搬運3天例一.AOE網(wǎng)的定義

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

正常情況下，AOE網(wǎng)中只有一個入度為0的頂點，稱之為源點；有一個出度為0的頂點，稱之為終點。1.只有在某個頂點所代表的事件發(fā)生以后,該頂點引發(fā)的活動才能開始。2.進入某事件的所有邊所代表的活動都已完成,該頂點所代表的事件才能發(fā)生。AOE網(wǎng)的特點：1.關鍵路徑的定義

從源點到終點的路徑中具有最大路徑長度的路徑為關鍵路徑;關鍵路徑上的活動稱為關鍵活動。二.關鍵路徑2.關鍵路徑的特點1)關鍵路徑的長度為完成整個工程所需要的最短時間。2)關鍵路徑的長度變化(即任意關鍵活動的權值變化)將影響整個工程的進度，而其他非關鍵活動在一定范圍內(nèi)的變化不會影響工期。求關鍵活動的思路：

e(i)

—

活動ai的最早開始時間

l(i)

—

活動ai的最遲開始時間若l(i)–a(i)=0，則說明活動ai為一個關鍵活動。Ve(k)—

事件k的最早發(fā)生時間kaiVl(k)—

事件k的最遲發(fā)生時間aik事件k的最早發(fā)生時間Ve(k)事件k的最遲發(fā)生時間Vl(k)活動的ai最早開始時間e(i)活動的ai最遲開始時間l(i)求e(i)=l(i)結論1.計算事件k的最早發(fā)生時間Ve(k)

所謂事件k