數(shù)據(jù)結(jié)構(gòu)第七章圖

會計學1數(shù)據(jù)結(jié)構(gòu)第七章圖2圖的基本概念圖定義圖是由頂點集合(vertex)及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中V={x|x

某個數(shù)據(jù)對象}

是頂點的有窮非空集合；

E1={(x,y)|x,yV}或E2={<x,y>|x,yV&&Path(x,y)}

其中，E1是頂點之間關(guān)系的有窮集合，也叫做邊(edge)集合，此時的圖稱為無向圖。E2表示從x到y(tǒng)的一條弧，且稱x為弧尾，y為弧頭，這樣的圖稱為有向圖。第1頁/共100頁3有向圖與無向圖

在有向圖中，頂點對

<x,y>是有序的。在無向圖中，頂點對(x,y)是無序的。完全圖

若有n個頂點的無向圖有n(n-1)/2

條邊,則此圖為無向完全圖。有n個頂點的有向圖有n(n-1)

條邊,則此圖為有向完全圖。00001111222265433第2頁/共100頁4

鄰接頂點

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

設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。權(quán)

某些圖的邊具有與它相關(guān)的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。0123子圖0130123023第3頁/共100頁5頂點的度

一個頂點v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點的度等于該頂點的入度與出度之和。頂點v的入度是以v為終點的有向邊的條數(shù),記作ID(v);頂點v的出度是以v為始點的有向邊的條數(shù),記作OD(v)。路徑

在圖G＝(V,E)中,若從頂點vi出發(fā),沿一些邊經(jīng)過一些頂點vp1,vp2,…,vpm，到達頂點vj。則稱頂點序列(vivp1vp2...vpmvj)為從頂點vi

到頂點vj

的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。第4頁/共100頁6頂點的出度:以頂點v為弧尾的弧的數(shù)目;頂點的入度:以頂點v為弧頭的弧的數(shù)目。ABECF有向圖頂點的度(TD)=出度(OD)+入度(ID)TD(B)=OD(B)+ID(B)=3例如:第5頁/共100頁7路徑長度

非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑

若路徑上各頂點v1,v2,...,vm均不互相重復,則稱這樣的路徑為簡單路徑。簡單回路若路徑上第一個頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)。012301230123第6頁/共100頁8ABECF如:從A到F長度為3的路徑{A,B,C,F}第7頁/共100頁9連通圖與連通分量

在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量

在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。第8頁/共100頁10無向圖,若圖中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖;若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEBACDFE第9頁/共100頁11有向圖,若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖。否則，其各個強連通子圖稱作它的強連通分量。ABECFABECF第10頁/共100頁12生成樹:假設(shè)一個連通圖有n個頂點和e條邊，其中n-1條邊和n個頂點構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。在極小連通子圖中增加一條邊，則一定有環(huán)。在極小連通子圖中去掉一條邊，則成為非連通圖。BACDFEBACDFE第11頁/共100頁13有n個頂點，n-1條邊的圖必定是生成樹嗎？對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。BACDFEBACDFE第12頁/共100頁14圖的存儲結(jié)構(gòu)在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關(guān)系的鄰接矩陣。設(shè)圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數(shù)組A.edge[n][n]，定義：鄰接矩陣(AdjacencyMatrix)第13頁/共100頁15無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123012第14頁/共100頁16在有向圖中,統(tǒng)計第i行1的個數(shù)可得頂點i的出度，統(tǒng)計第j列1的個數(shù)可得頂點j的入度。在無向圖中,統(tǒng)計第i行(列)1的個數(shù)可得頂點i的度。第15頁/共100頁17186329542031網(wǎng)絡(luò)的鄰接矩陣第16頁/共100頁18#defineMaxValueInt_MaxconstintNumEdges=50; //邊條數(shù)constintNumVertices=10;//頂點個數(shù)typedefcharVertexData;//頂點數(shù)據(jù)類型

typedefintEdgeData;//邊上權(quán)值類型typedefstruct{ VertexDatavexList[NumVertices];//頂點表

EdgeDataEdge[NumVertices][NumVertices];

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

intn,e;//圖中當前的頂點個數(shù)與邊數(shù)}MTGraph;

用鄰接矩陣表示的結(jié)構(gòu)定義第17頁/共100頁19鄰接表(AdjacencyList)鄰接表:是圖的一種鏈式存儲結(jié)構(gòu)?；〉慕Y(jié)點結(jié)構(gòu)

adjvex;//該弧所指向的頂點的位置

nextarc;//指向下一條弧指針

info;//該弧相關(guān)信息的指針adjvexnextarcinfo頂點的結(jié)點結(jié)構(gòu)datafirstarc

data;//頂點信息firstarc;//指向第一條依附該頂點的弧第18頁/共100頁20無向圖的鄰接表

同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點代表一條邊(邊結(jié)點),結(jié)點中有另一頂點的下標dest和指針link。ABCDdataadjABCD0123destlinkdestlink130210第19頁/共100頁21有向圖的鄰接表和逆鄰接表ABCdataadjABC012destlinkdestlink鄰接表(出邊表)dataadjABC012destlink逆鄰接表(入邊表)102011第20頁/共100頁22網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表BACD69528dataadjABCD0123destcostlink1

53

62

83

21

9(出邊表)(頂點表)第21頁/共100頁23帶權(quán)圖的邊結(jié)點中保存該邊上的權(quán)值cost。頂點i的邊鏈表的表頭指針adj在頂點表的下標為i的頂點記錄中，該記錄還保存了該頂點的其它信息。在鄰接表的邊鏈表中，各個邊結(jié)點的鏈入順序任意，視邊結(jié)點輸入次序而定。設(shè)圖中有n個頂點，e條邊，則用鄰接表表示無向圖時，需要n個頂點結(jié)點，2e個邊結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點結(jié)點，e個邊結(jié)點。第22頁/共100頁24圖的鄰接表存儲表示#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//該弧所指向的頂點的位置

structArcNode*nextarc;//指向下一條弧指針

InfoType*info;//該弧相關(guān)信息的指針}ArcNode;typedefstructVNode{VertexTypedata;//頂點信息

ArcNode*firstarc;//指向第一條依附該頂點的弧

}VNode,AdjList[MAX_VERTEX_NUM];第23頁/共100頁25typedefstruct{AdjListvertices;Intvexnum,arcnum;//圖的當前頂點數(shù)和弧數(shù)Intkind;//圖的種類標志}ALGraph;第24頁/共100頁26typedefcharVertexData;//頂點數(shù)據(jù)類型typedefintEdgeData;//邊上權(quán)值類型typedefstructnode{//邊結(jié)點

intdest;//目標頂點下標

EdgeDatacost; //邊上的權(quán)值

Structnode*link;//下一邊鏈接指針}EdgeNode;鄰接表表示的圖的定義（為算法）第25頁/共100頁27typedefstruct{//頂點結(jié)點

VertexDatadata;//頂點數(shù)據(jù)域

EdgeNode*firstAdj;//邊鏈表頭指針}VertexNode;

typedefstruct{//圖的鄰接表

VertexNodeVexList[NumVertices];//鄰接表

intn,e;//圖中當前的頂點個數(shù)與邊數(shù)}AdjGraph;第26頁/共100頁28鄰接表的構(gòu)造算法(無向圖)voidCreateGraph(AdjGraphG){cin>>G.n>>G.e; //輸入頂點個數(shù)和邊數(shù)

for(inti=0;i<G.n;i++){cin>>G.VexList[i].data;//輸入頂點信息

G.VexList[i].firstAdj=NULL;}for(i=0;i<e;i++){//逐條邊輸入

cin>>tail>>head>>weight;EdgeNode*p=newEdgeNode;p->dest=head;p->cost=weight; 第27頁/共100頁29

//鏈入第tail號鏈表的前端

p->link=G.VexList[tail].firstAdj;G.VexList[tail].firstAdj=p;

p=newEdgeNode;p->dest=tail;p->cost=weight;

//鏈入第head號鏈表的前端

p->link=G.VexList[head].firstAdj;G.VexList[head].firstAdj=p;}}第28頁/共100頁30圖的遍歷從圖中某一頂點出發(fā)訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，這一過程就叫做圖的遍歷(TraversingGraph)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。為了避免重復訪問，可設(shè)置一個標志頂點是否被訪問過的輔助數(shù)組visited[]。第29頁/共100頁31輔助數(shù)組visited[]的初始狀態(tài)為0,在圖的遍歷過程中,一旦某一個頂點i

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

DFS(DepthFirstSearch)廣度優(yōu)先搜索

BFS(BreadthFirstSearch)第30頁/共100頁32深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索過程67ACDEGBFIHACDEGBFIH1234589123456789前進回退深度優(yōu)先生成樹第31頁/共100頁33DFS在訪問圖中某一起始頂點v后,由v出發(fā),訪問它的任一鄰接頂點w1;再從w1出發(fā),訪問與w1鄰接但還沒有訪問過的頂點w2;然后再從w2出發(fā),進行類似的訪問,…如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發(fā),進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復上述過程,直到連通圖中所有頂點都被訪問過為止。第32頁/共100頁34

圖的深度優(yōu)先搜索算法voidGraph_Traverse(AdjGraphG){ int*visited=newint[NumVertices];for(inti=0;i<G.n;i++)visited[i]=0;//訪問數(shù)組visited初始化

for(inti=0;i<G.n;i++)if(!visited[i])DFS(G,i,visited);

//從頂點i出發(fā)開始搜索

delete[]visited;//釋放visited}第33頁/共100頁35voidDFS(AdjGraphG,intv,intvisited[]){cout<<GetValue(G,v)<<‘’;//訪問頂點vvisited[v]=1; //頂點v作訪問標記

intw=GetFirstNeighbor(G,v);

//取v的第一個鄰接頂點wwhile(w!=-1){ //若鄰接頂點w存在

if(!visited[w])DFS(G,w,visited);

//若頂點w未訪問過,遞歸訪問頂點ww=GetNextNeighbor(G,v,w);

//取頂點v排在w后的下一個鄰接頂點

}} 第34頁/共100頁36廣度優(yōu)先搜索BFS(BreadthFirstSearch)廣度優(yōu)先搜索過程ACDEGBFIHACDEGBFH123456789123456789廣度優(yōu)先生成樹I第35頁/共100頁37BFS在訪問了起始頂點v之后,由v出發(fā),依次訪問v的各個未被訪問過的鄰接頂點w1,w2,…,wt,然后再順序訪問w1,w2,…,wt的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點，…如此做下去，直到圖中所有頂點都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點,不像深度優(yōu)先搜索那樣有往回退的情況。因此,廣度優(yōu)先搜索不是一個遞歸的過程。第36頁/共100頁38為了實現(xiàn)逐層訪問,算法中使用了一個隊列,以記憶正在訪問的這一層和下一層的頂點,以便于向下一層訪問。為避免重復訪問,需要一個輔助數(shù)組visited[]，給被訪問過的頂點加標記。

圖的廣度優(yōu)先搜索算法voidGraph_Traverse(AdjGraphG){ ‥‥‥‥‥for(inti=0;i<G.n;i++)if(!visited[i])BFS(G,i,visited);‥‥‥‥‥}第37頁/共100頁39voidBFS(AdjGraphG,intv,intvisited[]){cout<<GetValue(v)<<'';visited[v]=1;Queue<int>q;InitQueue(&q);EnQueue(&q,v);//進隊列

while(!QueueEmpty(&q)){//隊空搜索結(jié)束

DeQueue(&q,v);intw=GetFirstNeighbor(G,v);while(w!=-1){//若鄰接頂點w存在

if(!visited[w]){//未訪問過

cout<<GetValue(w)<<‘’;第38頁/共100頁40

visited[w]=1;EnQueue(&q,w);} w=GetNextNeighbor(G,v,w);}//重復檢測v的所有鄰接頂點

}//外層循環(huán)，判隊列空否

delete[]visited;}第39頁/共100頁41

連通分量(Connectedcomponent)當無向圖為非連通圖時,從圖中某一頂點出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點,只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷,可求得無向圖的所有連通分量。圖的連通性問題第40頁/共100頁42求連通分量的算法需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。第41頁/共100頁43ACDEIBFOGHJNMLK非連通無向圖的三個連通分量AHKCDEIBFOGJNML非連通圖的連通分量的極小連通子圖第42頁/共100頁44重連通分量(BiconnectedComponent)在無向連通圖G中,當且僅當刪去G中的頂點v及所有依附于v的所有邊后,可將圖分割成兩個或兩個以上的連通分量，則稱頂點v為關(guān)節(jié)點。沒有關(guān)節(jié)點的連通圖叫做重連通圖。在重連通圖上,任何一對頂點之間至少存在有兩條路徑,在刪去某個頂點及與該頂點相關(guān)聯(lián)的邊時,也不破壞圖的連通性。一個連通圖G如果不是重連通圖，那么它可以包括幾個重連通分量。第43頁/共100頁45在一個無向連通圖G中,重連通分量可以利用深度優(yōu)先生成樹找到。在圖中各頂點旁標明的深度優(yōu)先數(shù),給出進行深度優(yōu)先搜索時各頂點訪問的次序。深度優(yōu)先生成樹的根是關(guān)節(jié)點的充要條件是它至少有兩個子女。其它頂點u是關(guān)節(jié)點的充要條件是它至少有一個子女w,從w出發(fā),不能通過w、w的子孫及一條回邊所組成的路徑到達u的祖先。第44頁/共100頁46ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有兩個子女關(guān)節(jié)點關(guān)節(jié)點關(guān)節(jié)點第45頁/共100頁47ABCDEFGHIJABHIDFBCDEFGH連通圖和它的連通分量第46頁/共100頁48最小生成樹(minimumcostspanningtree)使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n個頂點的連通網(wǎng)絡(luò)的生成樹有n個頂點、n-1條邊。構(gòu)造最小生成樹的準則必須使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達到最小。第47頁/共100頁49普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡(luò)N={V,E}中的某一頂點u0出發(fā),選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊 (u0,v),將其頂點加入到生成樹頂點集合U中。 以后每一步從一個頂點在U中,而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續(xù)下去,直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合U中為止。采用鄰接矩陣作為圖的存儲表示。第48頁/共100頁50252510504613228102514242216185046132504613210原圖(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212第49頁/共100頁51在構(gòu)造過程中，還設(shè)置了兩個輔助數(shù)組：

lowcost[]存放生成樹頂點集合內(nèi)頂點到生成樹外各頂點的各邊上的當前最小權(quán)值；

nearvex[]記錄生成樹頂點集合外各頂點距離集合內(nèi)哪個頂點最近(即權(quán)值最小)。例子5046132281025142422161812第50頁/共100頁52若選擇從頂點0出發(fā)，即u0=0，則兩個輔助數(shù)組的初始狀態(tài)為：然后反復做以下工作：在lowcost[]中選擇nearvex[i]

-1&&lowcost[i]最小的邊,用v標記它。則選中的權(quán)值最小的邊為(nearvex[v],v),相應(yīng)的權(quán)值為lowcost[v]。02810-1000000lowcostnearvex0123456第51頁/共100頁53將nearvex[v]改為-1,表示它已加入生成樹頂點集合。將邊(nearvex[v],v,lowcost[v])加入生成樹的邊集合。取lowcost[i]=min{lowcost[i],Edge[v][i]}，即用生成樹頂點集合外各頂點i到剛加入該集合的新頂點v的距離Edge[v][i]與原來它們到生成樹頂點集合中頂點的最短距離lowcost[i]做比較,取距離近的作為這些集合外頂點到生成樹頂點集合內(nèi)頂點的最短距離。第52頁/共100頁54

如果生成樹頂點集合外頂點i到剛加入該集合的新頂點v的距離比原來它到生成樹頂點集合中頂點的最短距離還要近，則修改nearvex[i]:nearvex[i]=v。表示生成樹外頂點i到生成樹內(nèi)頂點v當前距離最近。 02810

-1000000

lowcostnearvex0123456選v=5選邊(0,5)第53頁/共100頁55頂點v=5加入生成樹頂點集合：02825

10

-10005

-10

lowcostnearvex0123456選v=4選邊(5,4)50461322810251424221618原圖邊(0,5,10)

加入生成樹1204613210255第54頁/共100頁560123456頂點v=4加入生成樹頂點集合：02822

25

10

24

-100

4

-1

-1

4

lowcostnearvex選v=3選邊(4,3)50461322810251424221618原圖邊(5,4,25)

加入生成樹125046132102522第55頁/共100頁57頂點v=3加入生成樹頂點集合：02812

22

25

10

18

-103

-1

-1

-1

3

lowcostnearvex0123456選v=2選邊(3,2)50461322810251424221618原圖邊(4,3,22)

加入生成樹12504613210252212第56頁/共100頁58lowcostnearvex0123456頂點v=2加入生成樹頂點集合：0

16

12

22

25

1018

-1

2

-1

-1

-1

-13

選v=1選邊(2,1)50461322810251424221618原圖邊(3,2,12)

加入生成樹125041321025221612第57頁/共100頁59頂點v=1加入生成樹頂點集合：0

16

12

22

25

10

14

-1

-1

-1

-1

-1

-1

1

lowcostnearvex0123456選v=6選邊(1,6)50461322810251424221618原圖邊(2,1,16)

加入生成樹125046132102514221612第58頁/共100頁60lowcostnearvex0123456頂點v=6加入生成樹頂點集合：0

16

12

22

25

10

14

-1

-1

-1

-1

-1

-1

-1

50461322810251424221618原圖邊(1,6,14)

加入生成樹125046132102514221612第59頁/共100頁61最后生成樹中邊集合里存入得各條邊為：

(0,5,10),(5,4,25),(4,3,22), (3,2,12),(2,1,16),(1,6,14)利用普里姆算法建立最小生成樹voidPrim(GraphG,MST&T,intu){float*lowcost=newfloat[NumVertices];int*nearvex=newint[NumVertices];for(inti=0;i<NumVertices;i++){lowcost[i]=G.Edge[u][i];//Vu到各點代價

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

}第60頁/共100頁62

nearvex[u]=-1;//加到生成樹頂點集合

intk=0;//存放最小生成樹結(jié)點的變量

for(i=0;i<G.n;i++)if(i!=u){//循環(huán)n-1次,加入n-1條邊

EdgeDatamin=MaxValue;intv=0; for(intj=0;j<NumVertices;j++) if(nearvex[j]!=-1&&//=-1不參選

lowcost[j]<min) {v=j;min=lowcost[j];}

//求生成樹外頂點到生成樹內(nèi)頂點具有最

//小權(quán)值的邊,v是當前具最小權(quán)值的邊

第61頁/共100頁63

if(v){//v=0表示再也找不到要求頂點

T[k].tail=nearvex[v];//選邊加入生成樹

T[k].head=v;T[k++].cost=lowcost[v];nearvex[v]=-1;//該邊加入生成樹標記

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;}}第62頁/共100頁64

}//循環(huán)n-1次,加入n-1條邊}分析以上算法,設(shè)連通網(wǎng)絡(luò)有n個頂點,則該算法的時間復雜度為O(n2),它適用于邊稠密的網(wǎng)絡(luò)。注意：當各邊有相同權(quán)值時，由于選擇的隨意性，產(chǎn)生的生成樹可能不唯一。當各邊的權(quán)值不相同時，產(chǎn)生的生成樹是唯一的。

第63頁/共100頁65活動網(wǎng)絡(luò)(ActivityNetwork)計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學習。用頂點表示活動的網(wǎng)絡(luò)(AOV網(wǎng)絡(luò))第64頁/共100頁66

C1

高等數(shù)學

C2

程序設(shè)計基礎(chǔ)

C3

離散數(shù)學C1,C2

C4

數(shù)據(jù)結(jié)構(gòu)C3,C2C5

高級語言程序設(shè)計C2C6

編譯方法C5,C4C7

操作系統(tǒng)C4,C9C8

普通物理C1C9

計算機原理C8

課程代號課程名稱先修課程第65頁/共100頁67學生課程學習工程圖C8C3C5C4C9C6C7C1C2第66頁/共100頁68可以用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊<Vi,Vj>表示活動Vi必須先于活動Vj進行。這種有向圖叫做頂點表示活動的AOV網(wǎng)絡(luò)

(ActivityOnVertices)。在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路,即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項活動應(yīng)以自己作為先決條件。因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。第67頁/共100頁69檢測有向環(huán)的一種方法是對AOV網(wǎng)絡(luò)構(gòu)造它的拓撲有序序列。即將各個頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點的拓撲有序序列的運算就叫做拓撲排序。如果通過拓撲排序能將AOV網(wǎng)絡(luò)的所有頂點都排入一個拓撲有序的序列中,則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。第68頁/共100頁70如果AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。例如,對學生選課工程圖進行拓撲排序,得到的拓撲有序序列為

C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2第69頁/共100頁71拓撲排序的方法①

輸入AOV網(wǎng)絡(luò)。令n為頂點個數(shù)。 ②在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點,并輸出之;③從圖中刪去該頂點,同時刪去所有它發(fā)出的有向邊;④重復以上②、③步,直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點,但已跳出處理循環(huán)。說明圖中還剩下一些頂點,它們都有直接前驅(qū)。這時網(wǎng)絡(luò)中必存在有向環(huán)。第70頁/共100頁72C0C1C2C3C4C5拓撲排序的過程(a)有向無環(huán)圖C2C5C1C0C3(b)輸出頂點C4C1C2C5C3(c)輸出頂點C0C4C0C2C5C1C3(d)輸出頂點C3第71頁/共100頁73C1C2C5(e)輸出頂點C2C5C1(f)輸出頂點C1C5(g)輸出頂點C5

最后得到的拓撲有序序列為C4,C0,C3,C2,C1,C5

。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點，如C4和C2，也排出了先后次序關(guān)系。(h)拓撲排序完成第72頁/共100頁74AOV網(wǎng)絡(luò)及其鄰接表表示C0C1C2C3C4C5C0C1C2C30C4C50012345countdataadj

1301031

destlink3051500150第73頁/共100頁75在鄰接表中增設(shè)一個數(shù)組count[]，記錄各頂點入度。入度為零的頂點即無前驅(qū)頂點。在輸入數(shù)據(jù)前,頂點表VexList[]和入度數(shù)組count[]全部初始化。在輸入數(shù)據(jù)時,每輸入一條邊<j,k>,就需要建立一個邊結(jié)點,并將它鏈入相應(yīng)邊鏈表中,統(tǒng)計入度信息：

EdgeNode*p=newEdgeNode;

p->dest=k;

//建立邊結(jié)點

p->link=G.VexList[j].firstAdj;VexList[j].firstAdj=p;

//鏈入頂點j的邊鏈表的前端

count[k]++; //頂點k入度加一第74頁/共100頁76在算法中,使用一個存放入度為零的頂點的鏈式棧,供選擇和輸出無前驅(qū)的頂點。拓撲排序算法可描述如下：建立入度為零的頂點棧;當入度為零的頂點棧不空時,重復執(zhí)行

從頂點棧中退出一個頂點,并輸出之;

從AOV網(wǎng)絡(luò)中刪去這個頂點和它發(fā)出的邊,邊的終頂點入度減一;

如果邊的終頂點入度減至0,則該頂點進入度為零的頂點棧;

如果輸出頂點個數(shù)少于AOV網(wǎng)絡(luò)的頂點個數(shù),則報告網(wǎng)絡(luò)中存在有向環(huán)。第75頁/共100頁77拓撲排序的算法voidTopologicalSort(AdjGraphG){StackS;StackEmpty(S);intj;

//入度為零的頂點棧初始化

for(inti=0;i<n;i++)//入度為零頂點

if(count[i]==0)Push(S,i);//進棧

for(i=0;i<n;i++)//期望輸出n個頂點

if(StackEmpty(S)){//中途?？?轉(zhuǎn)出

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

第76頁/共100頁78

else{//繼續(xù)拓撲排序

Pop(S,j);//退棧

cout<<j<<endl;//輸出

EdgeNode*p=VexList[j].firstAdj;while(p!=NULL){//掃描出邊表

intk=p->dest; //另一頂點

if(--count[k]==0)//頂點入度減一

Push(S,k);

//頂點的入度減至零,進棧

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

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

用頂點表示事件(Event),

則這樣的有向圖叫做用邊表示活動的網(wǎng)絡(luò),簡稱AOE(ActivityOnEdges)網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：完成整個工程至少需要多少時間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?第78頁/共100頁80為縮短完成工程所需的時間,應(yīng)當加快哪些活動? 從源點到各個頂點,以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同,但只有各條路徑上所有活動都完成了,整個工程才算完成。因此,完成整個工程所需的時間取決于從源點到匯點的最長路徑長度,即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(CriticalPath)。第79頁/共100頁81a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10要找出關(guān)鍵路徑，必須找出關(guān)鍵活動,即不按期完成就會影響整個工程完成的活動。關(guān)鍵路徑上的所有活動都是關(guān)鍵活動。因此,只要找到了關(guān)鍵活動,就可以找到關(guān)鍵路徑。例如,下圖就是一個AOE網(wǎng)。第80頁/共100頁82定義幾個與計算關(guān)鍵活動有關(guān)的量：①

事件Vi

的最早可能開始時間Ve(i)

是從源點V0

到頂點Vi的最長路徑長度。②

事件Vi的最遲允許開始時間Vl[i]

是在保證匯點Vn-1

在Ve[n-1]

時刻完成的前提下，事件Vi

的允許的最遲開始時間。③

活動ak的最早可能開始時間

e[k]

設(shè)活動ak在邊<Vi,Vj>上,則e[k]是從源點V0到頂點Vi

的最長路徑長度。因此,

e[k]=Ve[i]。④

活動ak

的最遲允許開始時間

l[k]

第81頁/共100頁83

l[k]是在不會引起時間延誤的前提下,該活動允許的最遲開始時間。

l[k]=Vl[j]-dur(<i,j>)。

其中,dur(<i,j>)是完成

ak所需的時間。⑤

時間余量

l[k]-e[k]

表示活動

ak的最早可能開始時間和最遲允許開始時間的時間余量。l[k]==e[k]

表示活動

ak

是沒有時間余量的關(guān)鍵活動。為找出關(guān)鍵活動,需要求各個活動的e[k]

與l[k]，以判別是否l[k]==e[k]。第82頁/共100頁84為求得e[k]與l[k],需要先求得從源點V0

到各個頂點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>的集合。第83頁/共100頁85這兩個遞推公式的計算必須分別在拓撲有序及逆拓撲有序的前提下進行。設(shè)活動ak

(k=1,2,…,e)在帶權(quán)有向邊<Vi,Vj>

上,其持續(xù)時間用dur(<Vi,Vj>)

表示,則有

e[k]=Ve[i]；

l[k]=Vl[j]-dur(<Vi,Vj>)；k=1,2,…,e。這樣就得到計算關(guān)鍵路徑的算法。為了簡化算法,假定在求關(guān)鍵路徑之前已經(jīng)對各頂點實現(xiàn)了拓撲排序,并按拓撲有序的順序?qū)Ω黜旤c重新進行了編號。第84頁/共100頁861324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10VeVl12345678

0812222840465808122228404658el008121222222840460081212322228404612345678910第85頁/共100頁87事件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>活動a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

e0006457771614

l02366877101614l-e0

2302300300關(guān)鍵是是是是是是第86頁/共100頁88利用關(guān)鍵路徑法求AOE網(wǎng)的各關(guān)鍵活動void

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

int

i,

j;

int

p,k;

int

e,l;

Ve=newint[n];

Vl=newint[n];

for(i=0;

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

for(i=0;i<n;

i++){//順向計算事件最早允許開始時間

Edge<int>*p=NodeTable[i].adj;//該頂點邊鏈表鏈頭指針p

while(p!=NULL){//找所有后繼鄰接頂點

k=p→dest;//i的后繼鄰接頂點k

if(Ve[i]+p→cost>Ve[k]) Ve[k]=Ve[i]+p→cost; p=p→link;//找下一個后繼

}

第87頁/共100頁89}

for(i=0;

i<n;

i++)Vl[i]=Ve[n-1];//逆向計算事件 的最遲開始時間

for(i=n-2;

i;

i--){//按逆拓撲有序順序處理

p=NodeTable[i].adj;//該頂點邊鏈表鏈頭指針p

while(p!=NULL){

k=p→dest;//i的后繼鄰接頂點k

if(Vl[k]-

p→cost<Vl[i])

Vl[i]=Vl[k]-

p→cost;

p=p→link;//找下一個后繼

}

}第88頁/共100頁90

for(i=0;

i<n;

i++){//逐個頂點求各活動的e[k]和l[k]

p=NodeTable[i].adj; //該頂點邊鏈表鏈頭指針p

while(p!=NULL){

k=p→dest; //k是i的后繼鄰接頂點

e=Ve[i];l=Vl[k]-p→cost;

if(l==e)//關(guān)鍵活動

cout<<"<"<<i<<","<<k

<<“>”<<“是關(guān)鍵活動”<<endl;

p=p→link;//找下一個后繼

}

}}

第89頁/共100頁91注意在拓撲排序求Ve[i]和逆拓撲有序求Vl[i]時,所需為O(n+e),求各個活動的e[k]和l[k]時所需時間為O(e),總共花費時間仍然是O(n+e)。所有頂點按拓撲有序的次序編號僅計算Ve[i]和Vl[i]

是不夠的，還須計算e[k]

和l[k]。不是任一關(guān)鍵活動加速一定能使整個工程提前。想使整個工程提前，要考慮各個關(guān)鍵路徑上所有關(guān)鍵活動。第90頁/共100頁92最短路徑(ShortestPath)最短路徑問題：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。問題解法

邊上權(quán)值非負情形的單源最短路徑問題

—Dijkstra算法邊上權(quán)值為任意值的單源最短路徑問題

—Bellman和Ford算法所有頂點之間的最短路徑

—Floyd算法第91頁/共100頁93邊上權(quán)值非負情形的單源最短路徑問題問題的提法：給定一個帶權(quán)有向圖D與源點v，求從v到D中其它頂點的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑,Dijkstra提出按路徑長度的遞增次序,逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。舉例說明第92頁/共100頁94Dijkstra逐步求解的過程10432101003050206010源點終點最短路徑路徑長度v0

v1

(v0,v1)10

v