第9章圖圖的基本概念圖的存儲(chǔ)結(jié)構(gòu)圖的實(shí)現(xiàn)圖的遍歷最小生成樹(shù)最短路徑拓?fù)渑判蜿P(guān)鍵路徑

主要知識(shí)點(diǎn)編輯ppt教學(xué)計(jì)劃編排問(wèn)題

一個(gè)教學(xué)計(jì)劃包含許多課程，在教學(xué)計(jì)劃包含的許多課程之間，有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。編輯ppt課程編號(hào)

課程名稱

先修課程

C1

計(jì)算機(jī)導(dǎo)論

無(wú)C2

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

C1，C4

C3

匯編語(yǔ)言

C1

C4

C程序設(shè)計(jì)語(yǔ)言

C1

C5

計(jì)算機(jī)圖形學(xué)

C2，C3，C4

C6

接口技術(shù)

C3

C7

數(shù)據(jù)庫(kù)原理

C2，C9

C8

編譯原理

C4C9操作系統(tǒng)

C2編輯ppt教學(xué)計(jì)劃編排問(wèn)題（圖形結(jié)構(gòu)）

各課程之間的次序關(guān)系可用一個(gè)稱作圖的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，如課程之間優(yōu)先關(guān)系有向圖。有向圖中的每個(gè)頂點(diǎn)表示一門(mén)課程，如果從頂點(diǎn)vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先于課程j進(jìn)行。

編輯ppt課程之間優(yōu)先關(guān)系的有向圖

C1C3C2C4C8C6C5C9C7編號(hào)

課程名稱

C1

計(jì)算機(jī)導(dǎo)論

C2

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

C3

匯編語(yǔ)言

C4

C程序設(shè)計(jì)C5

計(jì)算機(jī)圖形學(xué)

C6

接口技術(shù)

C7

數(shù)據(jù)庫(kù)原理

C8

編譯原理

C9操作系統(tǒng)

編輯ppt9.1圖1.圖的基本概念圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。圖G的定義是：G=（V，E）其中，V={x|x∈某個(gè)數(shù)據(jù)元素集合} E={(x，y)|x，y∈V} 或 E={＜x，y＞|x，y∈V并且Path(x，y)}其中，（x，y）表示從x到y(tǒng)的一條雙向通路，即（x，y）是無(wú)方向的；Path（x，y）表示從x到y(tǒng)的一條單向通路，即Path（x，y）是有方向的。問(wèn)題：圖的特點(diǎn)編輯ppt圖有許多復(fù)雜結(jié)構(gòu)，本課程只討論最基本的圖，因此，本章討論的圖中不包括存在從自身到自身的邊的圖，以及多條邊的圖帶自身環(huán)的圖多重圖編輯ppt基本術(shù)語(yǔ)：（1）頂點(diǎn)和邊：

圖中的結(jié)點(diǎn)一般稱作頂點(diǎn)，圖中的第i個(gè)頂點(diǎn)記做vi。兩個(gè)頂點(diǎn)vi和vj相關(guān)聯(lián)稱作頂點(diǎn)vi和vj之間有一條邊，圖中的第k條邊記做ek，ek=（vi,vj）或＜vi,vj＞。013201234560120123(a)圖G1(b)圖G2(c)圖G3(d)圖G4編輯ppt（2）有向圖和無(wú)向圖：在有向圖中，頂點(diǎn)對(duì)＜x,y＞是有序的，頂點(diǎn)對(duì)＜x,y＞稱為從頂點(diǎn)x到頂點(diǎn)y的一條有向邊，有向圖中的邊也稱作弧；在無(wú)向圖中，頂點(diǎn)對(duì)（x,y）是無(wú)序的，頂點(diǎn)對(duì)（x,y）稱為與頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的一條邊。013201234560120123(a)圖G1(b)圖G2(c)圖G3(d)圖G4

編輯ppt（3）完全圖：在有n個(gè)頂點(diǎn)的無(wú)向圖中，若有n(n-1)/2條邊，即任意兩個(gè)頂點(diǎn)之間有且只有一條邊，則稱此圖為無(wú)向完全圖；在有n個(gè)頂點(diǎn)的有向圖中，若有n(n-1)條邊，即任意兩個(gè)頂點(diǎn)之間有且只有方向相反的兩條邊，則稱此圖為有向完全圖013201234560120123(a)圖G1(b)圖G2(c)圖G3(d)圖G4

無(wú)向完全圖不是無(wú)向完全圖有向完全圖不是有向完全圖編輯ppt（4）鄰接頂點(diǎn)：在無(wú)向圖G中，若（u,v）是E(G)中的一條邊，則稱u和v互為鄰接頂點(diǎn)，并稱邊（u,v）依附于頂點(diǎn)u和v；在有向圖G中，若＜u,v＞是E(G)中的一條邊，則稱頂點(diǎn)u鄰接到頂點(diǎn)v，頂點(diǎn)v鄰接自頂點(diǎn)u，并稱邊＜u,v＞和頂點(diǎn)u和頂點(diǎn)v相關(guān)聯(lián)。013201234560120123(a)圖G1(b)圖G2(c)圖G3(d)圖G4

編輯ppt（5）頂點(diǎn)的度：頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)，記作TD(v)。有向圖：頂點(diǎn)的度=入度+出度。入度ID(v)定義為以頂點(diǎn)v為終點(diǎn)的有向邊的條數(shù)；出度OD(v)定義為以頂點(diǎn)v為起點(diǎn)的有向邊的條數(shù)；無(wú)向圖：TD(v)=ID(v)=OD(v)013201234560120123(a)圖G1(b)圖G2(c)圖G3(d)圖G4

編輯ppt（6）路徑：

在圖G=(V,E)中，若從頂點(diǎn)vi出發(fā)有一組邊使可到達(dá)頂點(diǎn)vj，則稱頂點(diǎn)vi到頂點(diǎn)vj的頂點(diǎn)序列為從頂點(diǎn)vi到頂點(diǎn)vj的路徑.013201234560120123(a)圖G1(b)圖G2(c)圖G3(d)圖G4從頂點(diǎn)0到頂點(diǎn)3的路徑？如圖G1中：頂點(diǎn)3頂點(diǎn)0頂點(diǎn)2頂點(diǎn)0頂點(diǎn)3編輯ppt（7）權(quán)：

有些圖的邊附帶有數(shù)據(jù)信息，這些附帶的數(shù)據(jù)信息稱為權(quán)。帶權(quán)的圖也稱作網(wǎng)絡(luò)或網(wǎng)。2135467879610612715163BACDE60304575804035施工進(jìn)度圖

交通網(wǎng)絡(luò)圖

編輯ppt（8）路徑長(zhǎng)度：對(duì)于不帶權(quán)的圖，一條路徑的路徑長(zhǎng)度是指該路徑上的邊的條數(shù)；對(duì)于帶權(quán)的圖，一條路徑的路徑長(zhǎng)度是指該路徑上各個(gè)邊權(quán)值的總和。編輯ppt（9）子圖：

設(shè)有圖G1={V1,E1}和圖G2={V2,E2}，若V1V2，且E1

E2，則稱圖G2是圖G1的子圖。圖G2圖G1編輯ppt（10）連通圖和強(qiáng)連通圖：在無(wú)向圖中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱頂點(diǎn)vi和頂點(diǎn)vj是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的，則稱該圖是連通圖。在有向圖中，若對(duì)于任意一對(duì)頂點(diǎn)vi和頂點(diǎn)vj（vi≠vj）都存在路徑，則稱圖G是強(qiáng)連通圖。不是強(qiáng)連通圖強(qiáng)連通圖連通圖編輯ppt（11）生成樹(shù)：一個(gè)連通圖的最小連通子圖稱作該圖的生成樹(shù)。有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n個(gè)頂點(diǎn)和n-1條邊。生成樹(shù)一般是對(duì)無(wú)向圖來(lái)討論。圖G2的生成樹(shù)編輯ppt（12）簡(jiǎn)單路徑和回路：若路徑上各頂點(diǎn)v1,v2,…,vm,互不重復(fù)，則稱這樣的路徑為簡(jiǎn)單路徑；若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。編輯ppt數(shù)據(jù)集合：由一組頂點(diǎn)集合{vi}和一組邊{ej}集合組成。當(dāng)為帶權(quán)圖時(shí)每條邊上權(quán)wj還構(gòu)成權(quán)集合{wj}。操作集合：（1）初始化Initiate(G,n)（2）插入頂點(diǎn)InsertVertex(G,vertex)（3）插入邊InsertEdgeG,v1,v2,weight)（4）刪除邊DeleteEdge(G,v1,v2)（5）刪除頂點(diǎn)DeleteVertex(G,vertex)（6）取第一個(gè)鄰接頂點(diǎn)GetFirstVex(G,v)（7）取下一個(gè)鄰接頂點(diǎn)GetNextVex(G,intv1,v2)（8）遍歷DepthFirstSearch(G)2.圖的抽象數(shù)據(jù)類型編輯ppt9.2圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)主要有鄰接矩陣和鄰接表兩種。1.圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)假設(shè)圖G=(V,E)有n個(gè)頂點(diǎn)，即V={v0,v1,…,vn-1}，E可用如下形式的矩陣A描述，對(duì)于A中的每一個(gè)元素aij，滿足：由于矩陣A中的元素aij表示了頂點(diǎn)vi和頂點(diǎn)vj之間邊的關(guān)系，或者說(shuō)，A中的元素aij表示了頂點(diǎn)vi和頂點(diǎn)vj（0≤j≤n-1）的鄰接關(guān)系，所以矩陣A稱作鄰接矩陣。

編輯ppt無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣有向圖的鄰接矩陣一般是非對(duì)稱矩陣其中V表示了圖的頂點(diǎn)集合，A表示了圖的鄰接矩陣編輯ppt對(duì)于帶權(quán)圖，鄰接矩陣定義為：編輯ppt帶權(quán)圖及其鄰接矩陣其中V表示了圖的頂點(diǎn)集合，A表示了圖的鄰接矩陣。對(duì)于帶權(quán)圖，鄰接矩陣第i行中所有0<aij<∞的元素個(gè)數(shù)等于第i個(gè)頂點(diǎn)的出度，鄰接矩陣第j列中所有0<aij<∞的元素個(gè)數(shù)等于第j個(gè)頂點(diǎn)的入度。編輯ppt2.圖的鄰接表存儲(chǔ)結(jié)構(gòu)當(dāng)圖的邊數(shù)少于頂點(diǎn)個(gè)數(shù)且頂點(diǎn)個(gè)數(shù)值較大時(shí)，圖的鄰接n×n矩陣的存儲(chǔ)問(wèn)題就變成了稀疏矩陣的存儲(chǔ)問(wèn)題，此時(shí)，鄰接表就是一種較鄰接矩陣更為有效的存儲(chǔ)結(jié)構(gòu)。BADCE(a)01234ABCDE0datasorce1432adjdestnext23411∧

∧

∧

∧

(b)4∧

頂點(diǎn)信息頂點(diǎn)在數(shù)組中的下標(biāo)頂點(diǎn)的鄰接頂點(diǎn)在數(shù)組中下標(biāo)構(gòu)成單鏈表的頭指針編輯ppt數(shù)組的data域存儲(chǔ)圖的頂點(diǎn)信息；sorce域存儲(chǔ)該頂點(diǎn)在數(shù)組中的下標(biāo)序號(hào)；adj域?yàn)樵擁旤c(diǎn)的鄰接頂點(diǎn)單鏈表的頭指針。第i行單鏈表中的dest域存儲(chǔ)所有起始頂點(diǎn)為vi的鄰接頂點(diǎn)vj在數(shù)組中的下標(biāo)序號(hào)，next域?yàn)閱捂湵碇邢乱粋€(gè)鄰接頂點(diǎn)的指針域。如果是帶權(quán)圖，單鏈表中需再增加cost域，用來(lái)存儲(chǔ)邊<vi,vj>的權(quán)值wij。編輯ppt9.3圖的實(shí)現(xiàn)1.鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖操作的實(shí)現(xiàn)設(shè)圖G=(V,E)V是頂點(diǎn)集可以用順序表表示；E是邊集，刻畫(huà)了頂點(diǎn)之間的關(guān)系，用鄰接矩陣表示；邊的數(shù)量當(dāng)做整體，用一個(gè)變量表示結(jié)構(gòu)體變量先定義相應(yīng)的結(jié)構(gòu)體事先確定頂點(diǎn)個(gè)數(shù)MaxVertices編輯ppt結(jié)構(gòu)體定義#include"SeqList.h"

struct{SeqListVertices; intedge[MaxVertices][MaxVertices]; intnumOfEdges; };

一個(gè)圖G可以用一個(gè)AdjMGraph類型的結(jié)構(gòu)體變量或指針來(lái)表示。定義語(yǔ)句為：AdjMGraphG，*G1;

typedefAdjMGraph編輯pptvoidInitiate(AdjMGraph*G,intn) {inti,j;

ListInitiate(&G->Vertices); /*順序表初始化*/for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j) G->edge[i][j]=0; else G->edge[i][j]=MaxWeight;}

G->numOfEdges=0; /*邊的條數(shù)置為0*/}初始化G對(duì)于給定的圖G給定一個(gè)AdjMGraph類型的結(jié)構(gòu)體變量或指針。定義語(yǔ)句為：AdjMGraphG;初始化順序表成員初始化頂點(diǎn)關(guān)系成員初始化邊數(shù)成員給定一個(gè)AdjMGraph類型的結(jié)構(gòu)體變量或指針。定義語(yǔ)句為：AdjMGraph*G;編輯pptvoidInsertVertex(AdjMGraph*G,DataTypevertex){ListInsert(&G->Vertices,_____________________,vertex);}

在給定的圖G中插入頂點(diǎn)給定一個(gè)AdjMGraph類型的結(jié)構(gòu)體變量或指針。語(yǔ)句為：AdjMGraphG;給定一個(gè)AdjMGraph類型的結(jié)構(gòu)體變量或指針。語(yǔ)句為：AdjMGraph*G;給定頂點(diǎn)頂點(diǎn)插入操作就是對(duì)AdjMGraph類型的結(jié)構(gòu)體變量中的成員Vertices插入數(shù)據(jù)也就是順序表的插入操作G->Vertices.size編輯ppt在給定的圖G中插入邊給定一個(gè)AdjMGraph類型的結(jié)構(gòu)體變量或指針。語(yǔ)句為：AdjMGraphG;給定一個(gè)AdjMGraph類型的結(jié)構(gòu)體變量或指針。語(yǔ)句為：AdjMGraph*G;給定邊邊插入操作就是對(duì)AdjMGraph類型的結(jié)構(gòu)體變量中的成員edges插入數(shù)據(jù)也就是修改二維數(shù)組操作AdjMGraph類型的結(jié)構(gòu)體變量中的成員edges插入數(shù)據(jù)導(dǎo)致邊數(shù)的增加，因此還需要修改成員Numofedges的值給定邊兩個(gè)鄰接頂點(diǎn)在順序表中的位置標(biāo)號(hào)編輯ppt

voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight){if(__________________________________________________________){ printf("參數(shù)v1或v2越界出錯(cuò)!\n"); exit(1);}

G->edge[v1][v2]=weight;G->numOfEdges++;}插入邊操作v1<0||v1>=G->Vertices.size||v2<0||v2>=G->Vertices.size編輯pptvoidDeleteEdge(AdjMWGraph*G,intv1,intv2){if(v1<0||v1>=G->Vertices.size||v2<0||v2>=G->Vertices.size||v1==v2) {printf("參數(shù)v1或v2越界出錯(cuò)!\n"); exit(1);}

if(___________________________________________) {printf("該邊不存在!\n"); exit(0);}

G->edge[v1][v2]=MaxWeight; G->numOfEdges--;}刪除邊操作G->edge[v1][v2]==MaxWeight||v1==v2編輯pptintGetFirstVex(AdjMGraphG,intv){intcol;

if(v<0||v>G.Vertices.size) { printf("參數(shù)v1越界出錯(cuò)!\n"); exit(1); }

for(col=0;col<G.Vertices.size;col++) if(G.edge[v][col]>0&&G.edge[v][col]<MaxWeight)returncol; return-1;}取第一個(gè)鄰接頂點(diǎn)大于0并且小于MaxWeight?編輯pptintGetNextVex(AdjMGraphG,intv1,intv2){intcol;

if(v1<0||v1>=G.Vertices.size||v2<0||v2>=G.Vertices.size) {printf("參數(shù)v1或v2越界出錯(cuò)!\n");exit(1); }

for(col=v2+1;col<G.Vertices.size;col++) if(G.edge[v1][col]>0&&G.edge[v1][col]<MaxWeight)returncol; return-1;}大于0并且小于MaxWeight?取下一個(gè)鄰接頂點(diǎn)編輯ppt2.鄰接矩陣圖操作的測(cè)試?yán)?-1以下圖所示的帶權(quán)有向圖為例編寫(xiě)測(cè)試鄰接矩陣圖的程序。ABCDE1040305020邊的權(quán)值邊的起點(diǎn)邊的終點(diǎn)頂點(diǎn)存儲(chǔ)在一個(gè)字符數(shù)組中邊信息存儲(chǔ)在一個(gè)結(jié)構(gòu)數(shù)組中編輯ppt圖的創(chuàng)建函數(shù)設(shè)計(jì)如下：邊信息結(jié)構(gòu)體定義typedefstruct{introw; //行下標(biāo)

intcol; //列下標(biāo)

intweight; //權(quán)值}RowColWeight;ABCDE1040305020創(chuàng)建該圖對(duì)一個(gè)AdjMGraph類型的結(jié)構(gòu)變量插入頂點(diǎn)和邊編輯pptvoidCreatGraph(AdjMGraph*G,DataTypeV[],intn,RowColWeightE[],inte)/*在圖G中插入n個(gè)頂點(diǎn)信息V和e條邊信息E*/{ inti,k;

Initiate(G,n); /*初始化n個(gè)頂點(diǎn)的圖*/

for(i=0;i<n;i++) InsertVertex(G,V[i]); /*頂點(diǎn)插入*/

for(k=0;k<e;k++) InsertEdge(G,E[k].row,E[k].col,E[k].weight);/*邊插入*/

}圖的創(chuàng)建函數(shù)圖存放的AdjMGraph類型的指針變量頂點(diǎn)和頂點(diǎn)數(shù)邊信息和邊數(shù)編輯ppt測(cè)試程序設(shè)計(jì)如下：#include<stdio.h>#include<stdlib.h>

typedefcharDataType; #defineMaxSize100#defineMaxVertices10#defineMaxEdges100#defineMaxWeight10000

#include"AdjMGraph.h"#include"AdjMGraphCreate.h"voidmain(void){AdjMWGraphg1;DataTypea[]={'A','B','C','D','E'};RowColWeightrcw[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}};intn=5,e=5;inti,j;CreatGraph(&g1,a,n,rcw,e);DeleteEdge(&g1,0,4);printf("頂點(diǎn)集合為：");for(i=0;i<g1.Vertices.size;i++)printf("%c",g1.Vertices.list[i]);printf("\n");printf("權(quán)值集合為：\n");for(i=0;i<g1.Vertices.size;i++){for(j=0;j<g1.Vertices.size;j++) printf("%5d",g1.edge[i][j]); printf("\n");}}編輯ppt2.鄰接表存儲(chǔ)結(jié)構(gòu)下圖操作的實(shí)現(xiàn)BADCE(a)01234ABCDE0datasorce1432adjdestnext23411∧

∧

∧

∧

(b)4∧

三個(gè)成員：data,source,單鏈表頭指針adj兩個(gè)成員：下標(biāo)dest,下一個(gè)結(jié)點(diǎn)指針next編輯ppt2.鄰接表存儲(chǔ)結(jié)構(gòu)下圖操作的實(shí)現(xiàn)鄰接表的存儲(chǔ)結(jié)構(gòu)typedefstructNode{ intdest; /*鄰接邊的弧頭頂點(diǎn)序號(hào)*/

structNode*next;}Edge; /*鄰接邊單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體*/

typedefstruct{ DataTypedata; /*頂點(diǎn)數(shù)據(jù)元素*/

intsorce; /*鄰接邊的弧尾頂點(diǎn)序號(hào)*/

Edge*adj; /*鄰接邊的頭指針*/}AdjLHeight; /*數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體*/編輯ppttypedefstruct{AdjLHeighta[MaxVertices]; /*鄰接表數(shù)組*/intnumOfVerts; /*頂點(diǎn)個(gè)數(shù)*/intnumOfEdges; /*邊個(gè)數(shù)*/}AdjLGraph; /*鄰接表結(jié)構(gòu)體*/討論：圖操作的實(shí)現(xiàn)方法一個(gè)鄰接表用一個(gè)AdjLGragph類型的指針變量表示，定義語(yǔ)句為：AdjLGraph*G;編輯ppt012iMaxVertices︰︰︰3.插入第i個(gè)頂點(diǎn)i？

AdjLGraph*Ga[i]data編輯ppt012v1MaxVertices︰︰︰4.插入邊v1,v2是否在numOfVerts范圍內(nèi)？已知頂點(diǎn)v1和v2adj…∧pv2×①②③④⑤⑥修改邊數(shù)編輯ppt012v1MaxVertices︰︰︰5.刪除邊v1,v2是否在numOfVerts范圍內(nèi)？已知頂點(diǎn)v1和v2adj…∧查找v2？…∧curr只要curr存在且其dest值!=v2則curr下移一個(gè)一般需要記錄curr的前一個(gè)，引入precurrpre找完，分為三種情況ⅰ.在第一個(gè)ⅱ.不是第一個(gè)ⅲ.其他①②③④⑤⑥編輯ppt012vMaxVertices︰︰︰6.取第一個(gè)鄰接頂點(diǎn)v是否在numOfVerts范圍內(nèi)？已知頂點(diǎn)vadj…∧①②編輯ppt鄰接表存儲(chǔ)結(jié)構(gòu)下的圖的定義和操作測(cè)試參見(jiàn)具體程序:GraphTest.c編輯ppt9.4圖的遍歷1.圖的深度和廣度優(yōu)先遍歷算法圖的遍歷是訪問(wèn)圖中的每一個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)只被訪問(wèn)一次.圖遍歷方法深度優(yōu)先遍歷廣度優(yōu)先遍歷算法設(shè)計(jì)需要考慮三個(gè)問(wèn)題：算法的參數(shù)要指定訪問(wèn)的第一個(gè)頂點(diǎn)；要考慮遍歷路徑可能出現(xiàn)的死循環(huán)問(wèn)題；要使一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)按照某種次序被訪問(wèn)。編輯ppt一、圖的深度優(yōu)先遍歷算法圖的深度優(yōu)先遍歷算法是遍歷時(shí)深度優(yōu)先的算法；圖的深度優(yōu)先遍歷是指在圖的所有鄰接頂點(diǎn)中，每次都在訪問(wèn)完當(dāng)前頂點(diǎn)之后，接著首先訪問(wèn)當(dāng)前頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)。圖的深度優(yōu)先遍歷算法是一個(gè)函數(shù)遞歸調(diào)用算法。ABCDE1040305020①②③①②①②編輯ppt

開(kāi)始選擇初始頂點(diǎn)v0取v的第一個(gè)鄰接頂點(diǎn)ww訪問(wèn)？取v的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)w結(jié)束0w存在否按深度優(yōu)先遍歷訪問(wèn)w1訪問(wèn)和標(biāo)記v已訪問(wèn)連通圖的深度優(yōu)先遍歷算法為：編輯ppt對(duì)于例9-8所示的有向圖，頂點(diǎn)A作為初始訪問(wèn)結(jié)點(diǎn)，深度優(yōu)先遍歷訪問(wèn)頂點(diǎn)次序?yàn)椋篈BDCEABCDE1040305020①②③④⑤同一個(gè)路徑頂點(diǎn)優(yōu)先編輯ppt二、圖的廣度優(yōu)先遍歷算法圖的廣度優(yōu)先遍歷算法是一個(gè)分層搜索的過(guò)程，需要一個(gè)隊(duì)列以保持訪問(wèn)過(guò)的頂點(diǎn)的順序，以便按訪問(wèn)過(guò)的頂點(diǎn)的順序來(lái)訪問(wèn)這些頂點(diǎn)的鄰接頂點(diǎn)。連通圖的廣度優(yōu)先遍歷算法為：圖的廣度優(yōu)先遍歷是指從指定的頂點(diǎn)開(kāi)始，按照到該頂點(diǎn)路徑長(zhǎng)度由短到長(zhǎng)的順序，依次訪問(wèn)圖中的其余頂點(diǎn)。

編輯ppt

開(kāi)始選擇初始頂點(diǎn)v頂點(diǎn)入隊(duì)列QQ的隊(duì)頭元素u出隊(duì)Q空否0尋找u的第一個(gè)鄰接頂點(diǎn)ww訪問(wèn)？取u的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)w1結(jié)束0w存在否訪問(wèn)和標(biāo)記w已訪問(wèn)01訪問(wèn)和標(biāo)記v已訪問(wèn)編輯ppt

對(duì)于例9-8所示的有向圖，頂點(diǎn)A作為初始訪問(wèn)結(jié)點(diǎn)，廣度優(yōu)先遍歷訪問(wèn)頂點(diǎn)次序?yàn)椋篈BEDC問(wèn)題：圖的（深度、廣度）遍歷和生成樹(shù)的關(guān)系？ABCDE1040305020①②③④⑤同一個(gè)頂點(diǎn)的鄰接頂點(diǎn)優(yōu)先編輯ppt三、非連通圖的遍歷對(duì)于非連通圖，從圖的任意一個(gè)頂點(diǎn)開(kāi)始深度或廣度優(yōu)先遍歷并不能訪問(wèn)圖中的所有頂點(diǎn)。只能訪問(wèn)和初始頂點(diǎn)連通的所有頂點(diǎn)。但是，每一個(gè)頂點(diǎn)都作為一次初始頂點(diǎn)進(jìn)行深度優(yōu)先遍歷或廣度優(yōu)先遍歷，并根據(jù)頂點(diǎn)的訪問(wèn)標(biāo)記來(lái)判斷是否需要訪問(wèn)該頂點(diǎn)，就一定可以訪問(wèn)非連通圖中的所有頂點(diǎn)。編輯pptvoidDepthFSearch(AdjMWGraphG,intv,intvisited[],voidVisit(DataTypeitem)){

intw;Visit(G.Vertices.list[v]); visited[v]=1;

w=GetFirstVex(G,v);

while(w!=-1){if(!visited[w])DepthFSearch(G,w,visited,Visit);

w=GetNextVex(G,v,w);}}2.圖的深度和廣度優(yōu)先遍歷函數(shù)實(shí)現(xiàn)一、連通圖深度優(yōu)先遍歷編輯ppt二、非連通圖的深度優(yōu)先遍歷voidDepthFirstSearch(AdjMWGraphG,voidVisit(DataTypeitem)){

inti;

int*visited=(int*)malloc(sizeof(int)*G.Vertices.size);

for(i=0;i<G.Vertices.size;i++) visited[i]=0;

for(i=0;i<G.Vertices.size;i++)

if(!visited[i]) DepthFSearch(G,i,visited,Visit);

free(visited);}思想：對(duì)圖中每一個(gè)頂點(diǎn)作為初始頂點(diǎn)進(jìn)行深度優(yōu)先遍歷為了避免訪問(wèn)過(guò)的頂點(diǎn)重新被訪問(wèn)，引入標(biāo)記指針對(duì)圖中頂點(diǎn)進(jìn)行循環(huán)編輯ppt三、連通圖的廣度優(yōu)先遍歷#include"SeqQueue.h"voidBroadFSearch(AdjMWGraphG,intv,intvisited[],voidVisit(DataTypeitem)){DataTypeu,w;SeqCQueuequeue;

Visit(G.Vertices.list[v]); visited[v]=1;

QueueInitiate(&queue); QueueAppend(&queue,v);

while(QueueNotEmpty(queue)){QueueDelete(&queue,&u);

w=GetFirstVex(G,u);

while(w!=-1) {if(!visited[w]) { Visit(G.Vertices.list[w]); visited[w]=1;

QueueAppend(&queue,w); }

w=GetNextVex(G,u,w);

}}}編輯pptvoidBroadFirstSearch(AdjMWGraphG,voidVisit(DataTypeitem)){

inti;

int*visited=(int*)malloc(sizeof(int)*G.Vertices.size);

for(i=0;i<G.Vertices.size;i++) visited[i]=0;

for(i=0;i<G.Vertices.size;i++)

if(!visited[i]) BroadFSearch(G,i,visited,Visit);

free(visited);}四、非連通圖的廣度優(yōu)先遍歷編輯ppt五、程序舉例例9-2以圖9-8所示的帶權(quán)有向圖為例，編寫(xiě)測(cè)試上述圖的深度優(yōu)先和廣度優(yōu)先遍歷函數(shù)的程序。#include<stdio.h>#include<stdlib.h>#include<malloc.h>

typedefcharDataType; #defineMaxSize100#defineMaxVertices10#defineMaxEdges100

編輯ppt#defineMaxWeight10000#defineMaxQueueSize100#include"AdjMGraph.h"#include"AdjMGraphCreate.h"#include"AdjMGraphTraverse.h"

voidVisit(DataTypeitem){

printf("%c",item);}編輯pptvoidmain(void){ AdjMWGraphg1; DataTypea[]={'A','B','C','D','E'}; RowColWeightrcw[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}}; intn=5,e=5; CreatGraph(&g1,a,n,rcw,e); printf("深度優(yōu)先搜索序列為：");

DepthFirstSearch(g1,Visit); printf("\n廣度優(yōu)先搜索序列為：");

BroadFirstSearch(g1,Visit);}編輯ppt9.5最小生成樹(shù)1.基本概念一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖，它包含原圖中的所有n個(gè)頂點(diǎn)，并且有保持圖連通的最少的邊。（1）若在生成樹(shù)中刪除一條邊就會(huì)使該生成樹(shù)因變成非連通圖而不再滿足生成樹(shù)的定義；（2）若在生成樹(shù)中增加一條邊就會(huì)使該生成樹(shù)中因存在回路而不再滿足生成樹(shù)的定義；（3）一個(gè)連通圖的生成樹(shù)可能有許多；（4）有n個(gè)頂點(diǎn)的無(wú)向連通圖，無(wú)論它的生成樹(shù)的形狀如何，一定有且只有n-1條邊。編輯ppt1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)(b)(c)無(wú)向圖和它的不同的生成樹(shù)編輯ppt如果無(wú)向連通圖是一個(gè)帶權(quán)圖，那么它的所有生成樹(shù)中必有一棵邊的權(quán)值總和最小的生成樹(shù)，我們稱這棵生成樹(shù)為最小代價(jià)生成樹(shù)，簡(jiǎn)稱最小生成樹(shù)。

構(gòu)造有n個(gè)頂點(diǎn)的無(wú)向連通帶權(quán)圖的最小生成樹(shù)必須滿足以下三條：（1）構(gòu)造的最小生成樹(shù)必須包括n個(gè)頂點(diǎn)；（2）構(gòu)造的最小生成樹(shù)中有且只有n-1條邊；（3）構(gòu)造的最小生成樹(shù)中不存在回路。典型的構(gòu)造方法有兩種，一種稱作普里姆（Prim）算法，另一種稱作克魯斯卡爾（Kruskal）算法。編輯ppt2.普里姆算法一、算法思想假設(shè)G=(V,E)為一個(gè)帶權(quán)圖，V為帶權(quán)圖中頂點(diǎn)的集合，E為帶權(quán)圖中邊的權(quán)值集合。設(shè)置兩個(gè)新的集合U和T，U用于存放帶權(quán)圖G的最小生成樹(shù)的頂點(diǎn)的集合，T用于存放帶權(quán)圖G的最小生成樹(shù)的權(quán)值的集合。

編輯ppt普里姆算法思想是：(1)令集合U的初值為U={u0

}，集合T的初值為T(mén)={}。(2)從所有頂點(diǎn)u∈U和頂點(diǎn)v∈V-U的帶權(quán)邊中選出具有最小權(quán)值的邊(u,v)，

①將頂點(diǎn)v加入集合U中，

②將邊(u,v)加入集合T中。(3)判斷U=V是否成立

①不成立重復(fù)（2）

②成立時(shí)，最小生成樹(shù)構(gòu)造完畢。假設(shè)構(gòu)造最小生成樹(shù)時(shí)從頂點(diǎn)u0開(kāi)始結(jié)論：最終集合U中存放著最小生成樹(shù)頂點(diǎn)的集合，集合T中存放著最小生成樹(shù)邊的權(quán)值集合。編輯ppt圖9-10

普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程

U={A}V-U={B,C,D,E,F,G}T={50}U={A,B}V-U={C,D,E,F,G}更新T={50，40}U={A,B,E}V-U={C,D,F,G}更新T={50，40，50}T={}405050U={A,B,E,D}V-U={C,F,G}更新T={50，40，50，30}30U={A,B,E,D,F}V-U={C,G}更新T={50,40,50,30,42}42U={A,B,E,D,F,G}V-U={C}更新T={50,40,50,30,42,45}45U={A,B,E,D,F,G,C}V-U={}更新編輯pptU={A}V-U={B,C,D,E,F,G}T={}初始狀態(tài)：0124635最小生成樹(shù)A第1步：在U和V-U的頂點(diǎn)之間選擇權(quán)值最小的邊對(duì)應(yīng)的頂點(diǎn)。060∞50∞∞∞B50U={A,B}V-U={C,D,E,F,G}更新T={50}-1編輯ppt0124635最小生成樹(shù)A第2步：在U和V-U的頂點(diǎn)之間選擇權(quán)值最小的邊對(duì)應(yīng)的頂點(diǎn)。-160∞50∞∞∞B50U={A,B}V-U={C,D,E,F,G}第1步更新后T={50}-1預(yù)處理：引入一個(gè)一維數(shù)組lowcost[]。lowcost[]lowcost初值為第1行權(quán)值，第1個(gè)改為-1在第1步更新后對(duì)Lowcost進(jìn)行更新對(duì)更新的頂點(diǎn)對(duì)應(yīng)的鄰接矩陣中的行元素從第1元素開(kāi)始與lowcost中的元素進(jìn)行比較，用小的替換lowcost中的值6540E40編輯ppt二、普里姆函數(shù)設(shè)計(jì)普里姆函數(shù)應(yīng)有兩個(gè)參數(shù)，一個(gè)參數(shù)是圖G，另一個(gè)參數(shù)是通過(guò)函數(shù)得到的最小生成樹(shù)的頂點(diǎn)數(shù)據(jù)和相應(yīng)頂點(diǎn)的邊的權(quán)值數(shù)據(jù)closeVertex。其數(shù)據(jù)類型定義為如下結(jié)構(gòu)體：typederstruct{VerTvertex; intweight;}MinSpanTree;其中，vertex域用來(lái)保存最小生成樹(shù)每條邊的弧頭頂點(diǎn)數(shù)據(jù)，weight域用來(lái)保存最小生成樹(shù)的相應(yīng)邊的權(quán)值。圖G圖G的最小生成樹(shù)可以用MinSpanTree類型的結(jié)構(gòu)數(shù)組和結(jié)構(gòu)指針變量表示普里姆算法可以用一個(gè)函數(shù)來(lái)實(shí)現(xiàn)編輯ppt普里姆函數(shù)設(shè)計(jì)：voidPrim(AdjMWGraphG,MinSpanTreecloseVertex[]){VerTx;intn=G.Vertices.size,minCost; int*lowCost=(int*)malloc(sizeof(int)*n); inti,j,k;

for(i=1;i<n;i++) lowCost[i]=G.edge[0][i];

/*從頂點(diǎn)0出發(fā)構(gòu)造最小生成樹(shù)*/

ListGet(G.Vertices,0,&x); closeVertex[0].vertex=x; lowCost[0]=-1;

for(i=1;i<n;i++)編輯ppt{/*尋找當(dāng)前最小權(quán)值的邊所對(duì)應(yīng)的弧頭頂點(diǎn)k*/minCost=MaxWeight;

for(j=1;j<n;j++) {if(lowCost[j]<minCost&&lowCost[j]>0) {minCost=lowCost[j]; k=j; } }

ListGet(G.Vertices,k,&x); closeVertex[i].vertex=x; closeVertex[i].weight=minCost;

lowCost[k]=-1; for(j=1;j<n;j++) {if(G.edge[k][j]<lowCost[j]) lowCost[j]=G.edge[k][j]; } }}

編輯ppt設(shè)計(jì)說(shuō)明：（1）函數(shù)中定義一個(gè)臨時(shí)數(shù)組lowCost，數(shù)組元素lowCost[v]中保存了集合U中頂點(diǎn)ui與集合V-U中頂點(diǎn)vj的所有邊中當(dāng)前具有最小權(quán)值的邊(u,v)。（2）集合U的初值為U={序號(hào)為0的頂點(diǎn)}。lowCost的初始值為鄰接矩陣數(shù)組中第0行的值，這樣初始時(shí)lowCost中就存放了從集合U中頂點(diǎn)0到集合V-U中各個(gè)頂點(diǎn)的權(quán)值。（3）每次從lowCost中尋找具有最小權(quán)值的邊，根據(jù)lowCost的定義，這樣的邊其弧頭頂點(diǎn)必然為集合U中的頂點(diǎn)，其弧尾頂點(diǎn)必然為集合V-U中的頂點(diǎn)。當(dāng)選到一條這樣的邊(u,v)，就保存其頂點(diǎn)數(shù)據(jù)和權(quán)值數(shù)據(jù)到參數(shù)closeVertex中，并將lowCost[v]置為-1，表示頂點(diǎn)v加入了集合U中。編輯ppt0-115023456lowCost60∞

∞

∞

∞

0-11-123654405660∞

∞

0-11-123504-1570660∞

0-11-123-14-1530642520-11-123-14-15-1642520-11-123-14-15-16-1450-11-123-14-15-16-1-1(a)(b)(c)(d)(e)(f)(g)lowCostlowCostlowCostlowCostlowCostlowCost（4）當(dāng)頂點(diǎn)v從集合V-U加入到集合U后，若存在一條邊(u,v)，u是集合U的頂點(diǎn)，v是集合V-U的頂點(diǎn)，且邊(u,v)較原先lowCost[v]的代價(jià)更小，則用這樣的權(quán)值修改原先lowCost[v]中的相應(yīng)權(quán)值。（5）以圖9-10（a）所示的無(wú)向連通帶權(quán)圖為例，調(diào)用普里姆函數(shù)時(shí)數(shù)組lowCost的動(dòng)態(tài)變化過(guò)程如圖示。編輯ppt函數(shù)主要是一個(gè)兩重循環(huán)，其中每一重循環(huán)的次數(shù)均為頂點(diǎn)個(gè)數(shù)n，所以該算法的時(shí)間復(fù)雜度為O(n2)。

三、測(cè)試程序例9-3以圖9-10（a）所示的無(wú)向連通帶權(quán)圖為例設(shè)計(jì)測(cè)試上述Prim函數(shù)的程序。編輯ppt3.克魯斯卡爾算法克魯斯卡爾算法是一種按照帶權(quán)圖中邊的權(quán)值的遞增順序構(gòu)造最小生成樹(shù)的方法。設(shè)無(wú)向連通帶權(quán)圖G=(V,E)，其中V為頂點(diǎn)的集合，E為邊的集合。

克魯斯卡爾算法思想是：設(shè)帶權(quán)圖G的最小生成樹(shù)T由頂點(diǎn)集合和邊的集合構(gòu)成，其初值為T(mén)=(V,{})，即初始時(shí)最小生成樹(shù)T只由帶權(quán)圖G中的頂點(diǎn)集合組成，各頂點(diǎn)之間沒(méi)有一條邊。這樣，最小生成樹(shù)T中的各個(gè)頂點(diǎn)各自構(gòu)成一個(gè)連通分量。然后，按照邊的權(quán)值遞增的順序考察帶權(quán)圖G中的邊集合E中的各條邊，①若被考察的邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊加入到最小生成樹(shù)T，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；②若被考察的邊的兩個(gè)頂點(diǎn)屬于T的同一個(gè)連通分量，則將此邊舍去。如此下去，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，T中的該連通分量即為帶權(quán)圖G的一棵最小生成樹(shù)編輯pptACBGEFD30ACBGEFD3040ACBGEFD423040ACBGEFD45423040ACBGEFD5045423040ACBGEFD504542305040(a)(b)(c)(d)(e)(f)克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程編輯ppt9.6最短路徑1.基本概念路徑長(zhǎng)度:一條路徑上所經(jīng)過(guò)的邊的數(shù)目帶權(quán)路徑長(zhǎng)度:路徑上所經(jīng)過(guò)邊的權(quán)值之和最短路徑:(帶權(quán))路徑長(zhǎng)度(值)最小的那條路徑圖9-13（a）有向帶權(quán)圖；（b）鄰接矩陣從頂點(diǎn)B到頂點(diǎn)D的路徑：路徑(B,E,D)路徑(B,A,D)路徑(B,A,C,F,D)路徑(B,A,C,F,E,D)編輯ppt2.從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑一、狄克斯特拉算法思想：初始假設(shè)：

假設(shè)G=(V,E)，

集合S中存放已找到最短路徑的頂點(diǎn)，

集合T中存放當(dāng)前還未找到最短路徑的頂點(diǎn)。按路徑長(zhǎng)度遞增的順序逐步產(chǎn)生最短路徑。算法依據(jù)若從頂點(diǎn)S到頂點(diǎn)T有一條最短路徑，則該路徑上任何頂點(diǎn)到頂點(diǎn)S的距離都是最短的。編輯ppt設(shè)A為源點(diǎn)，求A到其他各頂點(diǎn)（B、C、D、E、F）的最短路徑。編輯ppt求解過(guò)程編輯ppt具體步驟：初始狀態(tài)，集合S={源點(diǎn)}={v0}，T=V-S；然后從集合T中選擇到源點(diǎn)v0路徑長(zhǎng)度最短的頂點(diǎn)u加入到集合S中，集合S中每加入一個(gè)新的頂點(diǎn)u都要修改源點(diǎn)v0到集合T中剩余頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度值.修改原則：集合T中各頂點(diǎn)的新的當(dāng)前最短路徑長(zhǎng)度值，為原來(lái)的當(dāng)前最短路徑長(zhǎng)度值與從源點(diǎn)過(guò)頂點(diǎn)u到達(dá)該頂點(diǎn)的路徑長(zhǎng)度中的較小者。此過(guò)程不斷重復(fù)，直到集合T中的頂點(diǎn)全部加入到集合S中為止。引入標(biāo)記數(shù)組S引入路徑長(zhǎng)度數(shù)組distance引入記錄最短路徑前一個(gè)頂點(diǎn)數(shù)組path編輯ppt一般的，假設(shè)u是新加入集合S的點(diǎn)，完成以下步驟：①計(jì)算源點(diǎn)v0到T中各個(gè)頂點(diǎn)的最短距離；②另一個(gè)方面計(jì)算源點(diǎn)v0到經(jīng)頂點(diǎn)u到達(dá)T中各個(gè)頂點(diǎn)的距離distanced0d1d2dudn-1︰︰標(biāo)記Ss0s1s21sn-1︰︰計(jì)算公式為：du+d(u,y),其中y是T中的頂點(diǎn)，也就是標(biāo)記為0的頂點(diǎn)③根據(jù)上述準(zhǔn)則修改distance中的值如果distance[y]>du+d(u,y),則用du+d(u,y)替換distznce[y]y編輯ppt狄克斯特拉算法求從頂點(diǎn)A到其余各頂點(diǎn)最短路徑的過(guò)程編輯ppt二、狄克斯特拉函數(shù)設(shè)計(jì)

參數(shù)設(shè)計(jì)：函數(shù)共有4個(gè)參數(shù)，其中2個(gè)為輸入?yún)?shù)，分別為帶權(quán)圖G和源點(diǎn)序號(hào)v0；2個(gè)為輸出參數(shù)，分別為distance[]和path[]，distance[]用來(lái)存放得到的從源點(diǎn)v0到其余各頂點(diǎn)的最短距離數(shù)值，path[]用來(lái)存放得到的從源點(diǎn)v0到其余各頂點(diǎn)的最短路徑上到達(dá)目標(biāo)頂點(diǎn)的前一頂點(diǎn)下標(biāo)。編輯ppt狄克斯特拉函數(shù)設(shè)計(jì)：voidDijkstra(AdjMGraphG,intv0,intdistance[],intpath[])/*帶權(quán)圖G從下標(biāo)v0頂點(diǎn)到其它頂點(diǎn)的最短距離distance*//*和最短路徑下標(biāo)path*/{intn=G.Vertices.size;int*s=(int*)malloc(sizeof(int)*n);intminDis,i,j,u;/*初始化*/for(i=0;i<n;i++) {distance[i]=G.edge[v0][i];s[i]=0; if(i!=v0&&distance[i]<MaxWeight)path[i]=v0; elsepath[i]=-1;}s[v0]=1;

編輯ppt/*在還未找到最短路徑的頂點(diǎn)集中選有最短距離的頂點(diǎn)u*/for(i=1;i<n;i++){minDis=MaxWeight; for(j=0;j<=n;j++) if(s[j]==0&&distance[j]<minDis) {u=j;minDis=distance[j];} /*當(dāng)已不再存在路徑時(shí)算法結(jié)束*/

if(minDis==MaxWeight)return; s[u]=1;/*標(biāo)記頂點(diǎn)u已從集合T加入到集合S中*/ /*修改從v0到其它頂點(diǎn)的最短距離和最短路徑*/

for(j=0;j<n;j++) if(s[j]==0&&G.edge[u][j]<MaxWeight&& distance[u]+G.edge[u][j]<distance[j]) {distance[j]=distance[u]+G.edge[u][j];path[j]=u; }}}

編輯ppt三、測(cè)試程序例9-4：以圖9-13的有向帶權(quán)圖為例設(shè)計(jì)測(cè)試上述Dijkstra函數(shù)的程序。編輯ppt3.每對(duì)頂點(diǎn)之間的最短路徑

帶權(quán)有向圖，每對(duì)頂點(diǎn)之間的最短路徑可通過(guò)調(diào)用狄克斯特拉算法實(shí)現(xiàn)。具體方法是：每次以不同的頂點(diǎn)作為源點(diǎn)，調(diào)用狄克斯特拉算法求出從該源點(diǎn)到其余頂點(diǎn)的最短路徑。重復(fù)n次就可求出每對(duì)頂點(diǎn)之間的最短路徑。由于狄克斯特拉算法的時(shí)間復(fù)雜度為O(n2)，所以這種算法的時(shí)間復(fù)雜度為O(n3)。

弗洛伊德算法的思想是：設(shè)矩陣cost用來(lái)存放帶權(quán)有向圖G的權(quán)值，即矩陣元素cost[i][j]中存放著下標(biāo)為i的頂點(diǎn)到下標(biāo)為j的頂點(diǎn)之間的權(quán)值，可以通過(guò)遞推構(gòu)造一個(gè)矩陣序列A0,A1,A2,……,AN來(lái)求每對(duì)頂點(diǎn)之間的最短路徑。其中，Ak[i][j]（0≤k≤n）表示從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)下標(biāo)不大于k的最短路徑長(zhǎng)度。初始時(shí)有，A0[i][j]=cost[i][j]。編輯ppt一種情況是該路徑不經(jīng)過(guò)下標(biāo)為k+1的頂點(diǎn)，此時(shí)該路徑長(zhǎng)度與從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)下標(biāo)不大于k的最短路徑長(zhǎng)度相同；另一種情況是該路徑經(jīng)過(guò)下標(biāo)為k+1的頂點(diǎn)，此時(shí)該路徑可分為兩段，一段是從頂點(diǎn)vi到頂點(diǎn)vk+1的最短路徑，另一段是從頂點(diǎn)vk+1到頂點(diǎn)vj的最短路徑，此時(shí)的最短路徑長(zhǎng)度等于這兩段最短路徑長(zhǎng)度之和。當(dāng)已經(jīng)求出Ak,要遞推求解Ak+1時(shí)，有：編輯ppt這兩種情況中的路徑長(zhǎng)度較小者，就是要求的從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)下標(biāo)不大于k+1的最短路徑長(zhǎng)度。用公式描述為：A0[i][j]=cost[i][j]Ak+1[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}（0≤k≤n-1）編輯ppt9.7拓?fù)渑判?/p>

1．偏序關(guān)系和全序關(guān)系拓?fù)渑判蚓褪且赡硞€(gè)集合上的偏序關(guān)系得到該集合上的全序關(guān)系。若集合X上的關(guān)系R是自反的、反對(duì)稱的和傳遞的，則稱關(guān)系R是集合X上的偏序關(guān)系（或稱半序關(guān)系）。設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，若對(duì)于每一個(gè)x∈X，都有(x,x)∈R，則稱R是自反的。設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，如果對(duì)于任意的x,y,z∈X，若當(dāng)(x,y)∈R且(y,z)∈R時(shí)，有(x,z)∈R，則稱關(guān)系R是傳遞的。

編輯ppt設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，若對(duì)于所有的x,y∈X，若當(dāng)(x,y)∈R且(y,x)∈R時(shí)，有x=y，則稱關(guān)系R是反對(duì)稱的。例如，設(shè)X是實(shí)數(shù)集合，R為小于等于關(guān)系，即R={(x,y)|x∈X∧y∈X∧x≤y}，由于當(dāng)x≤y且y≤x時(shí)有x＝y(tǒng)，因此，關(guān)系R是反對(duì)稱關(guān)系。另外，相等關(guān)系也是反對(duì)稱關(guān)系。設(shè)關(guān)系R是集合X上的偏序關(guān)系，若對(duì)所有的x,y∈X，有(x,y)∈R或(y,x)∈R，則稱關(guān)系R是集合X上的全序關(guān)系。

偏序關(guān)系的實(shí)質(zhì)是在集合X的元素之間建立層次結(jié)構(gòu)。這種層次結(jié)構(gòu)是依賴于偏序關(guān)系的可比性建立起來(lái)的。但是，偏序關(guān)系不能保證集合X中的任意兩個(gè)元素之間都能比較。而全序關(guān)系可以保證集合中的任意兩個(gè)元素之間都可以比較。編輯ppt

2．有向圖在實(shí)際問(wèn)題中的應(yīng)用一個(gè)有向圖可以表示一個(gè)施工流程圖，或產(chǎn)品生產(chǎn)流程圖，或數(shù)據(jù)流圖等。設(shè)圖中每一條有向邊表示兩個(gè)子工程之間的先后次序關(guān)系。若以有向圖中的頂點(diǎn)來(lái)表示活動(dòng)，以有向邊來(lái)表示活動(dòng)之間的先后次序關(guān)系，則這樣的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexNetwork)，簡(jiǎn)稱AOV網(wǎng)。

AOV網(wǎng)表示的有向圖要解決的一個(gè)問(wèn)題，就是如何得到一個(gè)完成整個(gè)工程項(xiàng)目的各子工程的序列。這就是有向圖的拓?fù)渑判騿?wèn)題。

3924756081編輯ppt

3．拓?fù)渑判蛟谟邢驁D中的應(yīng)用如果把有向圖中的所有頂點(diǎn)看作集合中的元素，把有向圖中的有向邊看作集合中的關(guān)系（通常情況下是先于關(guān)系），則可以證明，如果有向圖中不存在回路，則對(duì)應(yīng)的集合上的關(guān)系滿足偏序關(guān)系。因此，如何得到AOV網(wǎng)表示的施工流程圖的一個(gè)完成整個(gè)工程項(xiàng)目的各子工程的序列問(wèn)題，就是一個(gè)AOV網(wǎng)表示的有向圖的拓?fù)渑判騿?wèn)題。

對(duì)一個(gè)有向圖進(jìn)行拓?fù)渑判颍褪菍⒂邢驁D中的所有頂點(diǎn)排成一個(gè)線性序列，使得對(duì)有向圖中任意一對(duì)頂點(diǎn)u和v，若<u,v>是有向圖中的一條有向邊，則頂點(diǎn)u在該線性序列中出現(xiàn)在頂點(diǎn)v之前。這樣的線性序列稱為滿足拓?fù)浯涡虻男蛄校?jiǎn)稱為拓?fù)湫蛄小?duì)有向圖建立拓?fù)湫蛄械倪^(guò)程稱為對(duì)有向圖的拓?fù)渑判颉＞庉媝pt對(duì)于AOV網(wǎng)的拓?fù)渑判蚓褪菍OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列。拓?fù)渑判驅(qū)嶋H上就是要由某個(gè)集合上的一個(gè)偏序關(guān)系得到該集合上的一個(gè)全序關(guān)系。

例如，下圖所示的兩個(gè)有向圖，由于左圖中頂點(diǎn)B無(wú)法和頂點(diǎn)C比較，所以左圖表示的是偏序關(guān)系。如果在左圖中人為添加一條頂點(diǎn)B到頂點(diǎn)C的有向邊，即右圖，則右圖表示的就是全序關(guān)系。如果我們對(duì)一個(gè)有向圖進(jìn)行拓?fù)渑判颍玫搅嗽撚邢驁D中所有頂點(diǎn)的一個(gè)線性序列，因線性序列中所有頂點(diǎn)均可以比較，也就相當(dāng)于通過(guò)人為添加一些有向邊，把有向圖對(duì)應(yīng)的偏序關(guān)系變成了全序關(guān)系。

編輯ppt編輯ppt

4．有向圖的拓?fù)渑判蛩惴ㄓ邢驁D的拓?fù)渑判蛩惴ǎ?1)在有向圖中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并把它輸出；(2)從有向圖中刪去該頂點(diǎn)以及與它相關(guān)的有向邊。重復(fù)上述兩個(gè)步驟，直到所有頂點(diǎn)都輸出，或者剩余的頂點(diǎn)中找不到?jīng)]有前驅(qū)的頂點(diǎn)。在前一種情況下，頂點(diǎn)的輸出序列就是一個(gè)拓?fù)湫蛄校缓笠环N情況則說(shuō)明有向圖中存在回路，如果有向圖中存在回路，則該有向圖一定無(wú)法得到一個(gè)拓?fù)湫蛄小＞庉媝pt

上述算法僅能得到有向圖的一個(gè)拓?fù)湫蛄小８倪M(jìn)上述算法，可以得到有向圖的所有拓?fù)湫蛄小Ｈ绻粋€(gè)有向圖存在一個(gè)拓?fù)湫蛄校ǔ１硎驹撚邢驁D對(duì)應(yīng)的某個(gè)施工流程圖的一種施工方案切實(shí)可行；而如果一個(gè)有向圖不存在一個(gè)拓?fù)湫蛄校瑒t說(shuō)明該有向圖對(duì)應(yīng)的某個(gè)施工流程圖存在設(shè)計(jì)問(wèn)題，不存在切實(shí)可行的任何一種施工方案。

編輯ppt例：對(duì)于如下圖所示的AOV網(wǎng)，寫(xiě)出利用拓?fù)渑判蛩惴ǖ玫降囊粋€(gè)拓?fù)湫蛄小＝猓焊鶕?jù)拓?fù)渑判蛩惴ǎ玫降囊粋€(gè)拓?fù)湫蛄袨?,1,7,2,4,8,5,9,3,6。39圖9-17AOV網(wǎng)24756081編輯ppt9.8關(guān)鍵路徑

1．工程管理中的問(wèn)題在工程規(guī)劃中，經(jīng)常需要考慮這樣的問(wèn)題，完成整個(gè)工程最短需要多長(zhǎng)時(shí)間，工程中的哪些工序是一些重要的工序，縮短這些重要工序的時(shí)間可以縮短整個(gè)工程的工期。在生產(chǎn)管理中，也存在這樣的問(wèn)題，一件產(chǎn)品有多道生產(chǎn)工序，減少哪道工序所用的時(shí)間可以縮短產(chǎn)品的生產(chǎn)周期。諸如此類的問(wèn)題，可以使用有向圖進(jìn)行描述和分析。下面我們首先給出描述這類問(wèn)題的有關(guān)概念，然后討論解決的方法。編輯ppt

2．AOE網(wǎng)對(duì)工程管理問(wèn)題的表示在有向圖中，如果頂點(diǎn)表示事件，有向邊表示活動(dòng)，有向邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間，這樣的有向圖稱為邊表示活動(dòng)的網(wǎng)(ActivityOnEdge)，簡(jiǎn)稱AOE網(wǎng)。對(duì)于AOE網(wǎng)，需要研究的問(wèn)題是：（1）完成整個(gè)工程需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？編輯ppta9=6a6=4a2=7a1=5a3=3a4=6a5=3a7=5a8=4a10=5a11=8a14=9a12=2a13=8a15=3圖9-19AOE網(wǎng)v0v3v1v4v7v6v8v5v2v9編輯ppt基本概念：路徑長(zhǎng)度：AOE網(wǎng)的一條路徑上所有活動(dòng)的總和稱為該路徑的長(zhǎng)度。關(guān)鍵路徑：在AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)的所有路徑中，具有最大路徑長(zhǎng)度的路徑稱為關(guān)鍵路徑。關(guān)鍵