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

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

Graph＝(V,E)

其中V={x|x

某個(gè)數(shù)據(jù)對(duì)象}

是頂點(diǎn)的有窮非空集合；

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

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

在有向圖中，頂點(diǎn)對(duì)

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

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

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

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

鄰接頂點(diǎn)

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

設(shè)有兩個(gè)圖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頂點(diǎn)的度

一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(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)序列(vivp1vp2...vpmvj)為從頂點(diǎn)vi

到頂點(diǎn)vj

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

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

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

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

在有向圖中,若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。第8頁/共100頁10無向圖,若圖中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖;若無向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。BACDFEBACDFE第9頁/共100頁11有向圖,若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量。ABECFABECF第10頁/共100頁12生成樹:假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。在極小連通子圖中增加一條邊，則一定有環(huán)。在極小連通子圖中去掉一條邊，則成為非連通圖。BACDFEBACDFE第11頁/共100頁13有n個(gè)頂點(diǎn)，n-1條邊的圖必定是生成樹嗎？對(duì)非連通圖，則稱由各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林。BACDFEBACDFE第12頁/共100頁14圖的存儲(chǔ)結(jié)構(gòu)在圖的鄰接矩陣表示中，有一個(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]，定義：鄰接矩陣(AdjacencyMatrix)第13頁/共100頁15無向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。0123012第14頁/共100頁16在有向圖中,統(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的度。第15頁/共100頁17186329542031網(wǎng)絡(luò)的鄰接矩陣第16頁/共100頁18#defineMaxValueInt_MaxconstintNumEdges=50; //邊條數(shù)constintNumVertices=10;//頂點(diǎn)個(gè)數(shù)typedefcharVertexData;//頂點(diǎn)數(shù)據(jù)類型

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

EdgeDataEdge[NumVertices][NumVertices];

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

intn,e;//圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù)}MTGraph;

用鄰接矩陣表示的結(jié)構(gòu)定義第17頁/共100頁19鄰接表(AdjacencyList)鄰接表:是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。弧的結(jié)點(diǎn)結(jié)構(gòu)

adjvex;//該弧所指向的頂點(diǎn)的位置

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

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

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

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

53

62

83

21

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

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

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

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

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

intdest;//目標(biāo)頂點(diǎn)下標(biāo)

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

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

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

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

typedefstruct{//圖的鄰接表

VertexNodeVexList[NumVertices];//鄰接表

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

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

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號(hào)鏈表的前端

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

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

//鏈入第head號(hào)鏈表的前端

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

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

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

BFS(BreadthFirstSearch)第30頁/共100頁32深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索過程67ACDEGBFIHACDEGBFIH1234589123456789前進(jìn)回退深度優(yōu)先生成樹第31頁/共100頁33DFS在訪問圖中某一起始頂點(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)都被訪問過為止。第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);

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

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

intw=GetFirstNeighbor(G,v);

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

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

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

//取頂點(diǎn)v排在w后的下一個(gè)鄰接頂點(diǎn)

}} 第34頁/共100頁36廣度優(yōu)先搜索BFS(BreadthFirstSearch)廣度優(yōu)先搜索過程ACDEGBFIHACDEGBFH123456789123456789廣度優(yōu)先生成樹I第35頁/共100頁37BFS在訪問了起始頂點(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è)遞歸的過程。第36頁/共100頁38為了實(shí)現(xiàn)逐層訪問,算法中使用了一個(gè)隊(duì)列,以記憶正在訪問的這一層和下一層的頂點(diǎn),以便于向下一層訪問。為避免重復(fù)訪問,需要一個(gè)輔助數(shù)組visited[]，給被訪問過的頂點(diǎn)加標(biāo)記。

圖的廣度優(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);//進(jìn)隊(duì)列

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

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

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

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

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

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

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

連通分量(Connectedcomponent)當(dāng)無向圖為非連通圖時(shí),從圖中某一頂點(diǎn)出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn),只能訪問到該頂點(diǎn)所在的最大連通子圖(連通分量)的所有頂點(diǎn)。若從無向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷,可求得無向圖的所有連通分量。圖的連通性問題第40頁/共100頁42求連通分量的算法需要對(duì)圖的每一個(gè)頂點(diǎn)進(jìn)行檢測(cè)：若已被訪問過，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個(gè)連通分量。對(duì)于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。第41頁/共100頁43ACDEIBFOGHJNMLK非連通無向圖的三個(gè)連通分量AHKCDEIBFOGJNML非連通圖的連通分量的極小連通子圖第42頁/共100頁44重連通分量(BiconnectedComponent)在無向連通圖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)的連通圖叫做重連通圖。在重連通圖上,任何一對(duì)頂點(diǎn)之間至少存在有兩條路徑,在刪去某個(gè)頂點(diǎn)及與該頂點(diǎn)相關(guān)聯(lián)的邊時(shí),也不破壞圖的連通性。一個(gè)連通圖G如果不是重連通圖，那么它可以包括幾個(gè)重連通分量。第43頁/共100頁45在一個(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è)子女。其它頂點(diǎn)u是關(guān)節(jié)點(diǎn)的充要條件是它至少有一個(gè)子女w,從w出發(fā),不能通過w、w的子孫及一條回邊所組成的路徑到達(dá)u的祖先。第44頁/共100頁46ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有兩個(gè)子女關(guān)節(jié)點(diǎn)關(guān)節(jié)點(diǎn)關(guān)節(jié)點(diǎn)第45頁/共100頁47ABCDEFGHIJABHIDFBCDEFGH連通圖和它的連通分量第46頁/共100頁48最小生成樹(minimumcostspanningtree)使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(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á)到最小。第47頁/共100頁49普里姆(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中為止。采用鄰接矩陣作為圖的存儲(chǔ)表示。第48頁/共100頁50252510504613228102514242216185046132504613210原圖(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212第49頁/共100頁51在構(gòu)造過程中，還設(shè)置了兩個(gè)輔助數(shù)組：

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

nearvex[]記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近(即權(quán)值最小)。例子5046132281025142422161812第50頁/共100頁52若選擇從頂點(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]。02810-1000000lowcostnearvex0123456第51頁/共100頁53將nearvex[v]改為-1,表示它已加入生成樹頂點(diǎn)集合。將邊(nearvex[v],v,lowcost[v])加入生成樹的邊集合。取lowcost[i]=min{lowcost[i],Edge[v][i]}，即用生成樹頂點(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)的最短距離。第52頁/共100頁54

如果生成樹頂點(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)前距離最近。 02810

-1000000

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

10

-10005

-10

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

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

25

10

24

-100

4

-1

-1

4

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

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

22

25

10

18

-103

-1

-1

-1

3

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

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

16

12

22

25

1018

-1

2

-1

-1

-1

-13

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

加入生成樹125041321025221612第57頁/共100頁59頂點(diǎn)v=1加入生成樹頂點(diǎn)集合：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頂點(diǎn)v=6加入生成樹頂點(diǎn)集合：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到各點(diǎn)代價(jià)

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

}第60頁/共100頁62

nearvex[u]=-1;//加到生成樹頂點(diǎn)集合

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

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];}

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

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

第61頁/共100頁63

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

}//循環(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)生的生成樹是唯一的。

第63頁/共100頁65活動(dòng)網(wǎng)絡(luò)(ActivityNetwork)計(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í)。用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV網(wǎng)絡(luò))第64頁/共100頁66

C1

高等數(shù)學(xué)

C2

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

C3

離散數(shù)學(xué)C1,C2

C4

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

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

編譯方法C5,C4C7

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

普通物理C1C9

計(jì)算機(jī)原理C8

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

(ActivityOnVertices)。在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路,即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。因此，對(duì)給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。第67頁/共100頁69檢測(cè)有向環(huán)的一種方法是對(duì)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ù)渑判?。如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄?則該網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)。第68頁/共100頁70如果AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。例如,對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判?得到的拓?fù)溆行蛐蛄袨?/p>

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

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2第69頁/共100頁71拓?fù)渑判虻姆椒á?/p>

輸入AOV網(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)。第70頁/共100頁72C0C1C2C3C4C5拓?fù)渑判虻倪^程(a)有向無環(huán)圖C2C5C1C0C3(b)輸出頂點(diǎn)C4C1C2C5C3(c)輸出頂點(diǎn)C0C4C0C2C5C1C3(d)輸出頂點(diǎn)C3第71頁/共100頁73C1C2C5(e)輸出頂點(diǎn)C2C5C1(f)輸出頂點(diǎn)C1C5(g)輸出頂點(diǎn)C5

最后得到的拓?fù)溆行蛐蛄袨镃4,C0,C3,C2,C1,C5

。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對(duì)于本來沒有這種關(guān)系的頂點(diǎn)，如C4和C2，也排出了先后次序關(guān)系。(h)拓?fù)渑判蛲瓿傻?2頁/共100頁74AOV網(wǎng)絡(luò)及其鄰接表表示C0C1C2C3C4C5C0C1C2C30C4C50012345countdataadj

1301031

destlink3051500150第73頁/共100頁75在鄰接表中增設(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=newEdgeNode;

p->dest=k;

//建立邊結(jié)點(diǎn)

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

//鏈入頂點(diǎn)j的邊鏈表的前端

count[k]++; //頂點(diǎn)k入度加一第74頁/共100頁76在算法中,使用一個(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)。第75頁/共100頁77拓?fù)渑判虻乃惴╲oidTopologicalSort(AdjGraphG){StackS;StackEmpty(S);intj;

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

for(inti=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;}

第76頁/共100頁78

else{//繼續(xù)拓?fù)渑判?/p>

Pop(S,j);//退棧

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

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

intk=p->dest; //另一頂點(diǎn)

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

Push(S,k);

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

p=p->link; }}}第77頁/共100頁79用邊表示活動(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(ActivityOnEdges)網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?第78頁/共100頁80為縮短完成工程所需的時(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)鍵路徑(CriticalPath)。第79頁/共100頁81a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng),即不按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)。關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。因此,只要找到了關(guān)鍵活動(dòng),就可以找到關(guān)鍵路徑。例如,下圖就是一個(gè)AOE網(wǎng)。第80頁/共100頁82定義幾個(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]

第81頁/共100頁83

l[k]是在不會(huì)引起時(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]。第82頁/共100頁84為求得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>的集合。第83頁/共100頁85這兩個(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,…,e。這樣就得到計(jì)算關(guān)鍵路徑的算法。為了簡化算法,假定在求關(guān)鍵路徑之前已經(jīng)對(duì)各頂點(diǎn)實(shí)現(xiàn)了拓?fù)渑判?并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)行了編號(hào)。第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>活動(dòng)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)鍵活動(dòng)void

graph::CriticalPath(){//在此算法中需要對(duì)鄰接表中單鏈表的結(jié)點(diǎn)加以//修改,在各結(jié)點(diǎn)中增加一個(gè)int域cost,記錄該結(jié)//點(diǎn)所表示的邊上的權(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++){//順向計(jì)算事件最早允許開始時(shí)間

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

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

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

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

}

第87頁/共100頁89}

for(i=0;

i<n;

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

for(i=n-2;

i;

i--){//按逆拓?fù)溆行蝽樞蛱幚?/p>

p=NodeTable[i].adj;//該頂點(diǎn)邊鏈表鏈頭指針p

while(p!=NULL){

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

if(Vl[k]-

p→cost<Vl[i])

Vl[i]=Vl[k]-

p→cost;

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

}

}第88頁/共100頁90

for(i=0;

i<n;

i++){//逐個(gè)頂點(diǎn)求各活動(dòng)的e[k]和l[k]

p=NodeTable[i].adj; //該頂點(diǎn)邊鏈表鏈頭指針p

while(p!=NULL){

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

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

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

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

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

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

}

}}

第89頁/共100頁91注意在拓?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ào)僅計(jì)算Ve[i]和Vl[i]

是不夠的，還須計(jì)算e[k]

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

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

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

—Bellman和Ford算法所有頂點(diǎn)之間的最短路徑

—Floyd算法第91頁/共100頁93邊上權(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)的最短路徑全部求出為止。舉例說明第92頁/共100頁94Dijkstra逐步求解的過程10432101003050206010源點(diǎn)終點(diǎn)最短路徑路徑長度v0

v1

(v0,v1)10

v