《數(shù)據(jù)結(jié)構(gòu)教學(xué)》第09章

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

主要知識點編輯ppt教學(xué)計劃編排問題

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

課程名稱

先修課程

C1

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

無C2

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

C1，C4

C3

匯編語言

C1

C4

C程序設(shè)計語言

C1

C5

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

C2，C3，C4

C6

接口技術(shù)

C3

C7

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

C2，C9

C8

編譯原理

C4C9操作系統(tǒng)

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

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

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

C1C3C2C4C8C6C5C9C7編號

課程名稱

C1

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

C2

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

C3

匯編語言

C4

C程序設(shè)計C5

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

C6

接口技術(shù)

C7

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

C8

編譯原理

C9操作系統(tǒng)

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

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

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

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

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

編輯ppt（6）路徑：

在圖G=(V,E)中，若從頂點vi出發(fā)有一組邊使可到達(dá)頂點vj，則稱頂點vi到頂點vj的頂點序列為從頂點vi到頂點vj的路徑.013201234560120123(a)圖G1(b)圖G2(c)圖G3(d)圖G4從頂點0到頂點3的路徑？如圖G1中：頂點3頂點0頂點2頂點0頂點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）路徑長度：對于不帶權(quán)的圖，一條路徑的路徑長度是指該路徑上的邊的條數(shù)；對于帶權(quán)的圖，一條路徑的路徑長度是指該路徑上各個邊權(quán)值的總和。編輯ppt（9）子圖：

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

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

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

∧

∧

∧

(b)4∧

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

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

一個圖G可以用一個AdjMGraph類型的結(jié)構(gòu)體變量或指針來表示。定義語句為：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對于給定的圖G給定一個AdjMGraph類型的結(jié)構(gòu)體變量或指針。定義語句為：AdjMGraphG;初始化順序表成員初始化頂點關(guān)系成員初始化邊數(shù)成員給定一個AdjMGraph類型的結(jié)構(gòu)體變量或指針。定義語句為：AdjMGraph*G;編輯pptvoidInsertVertex(AdjMGraph*G,DataTypevertex){ListInsert(&G->Vertices,_____________________,vertex);}

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

voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight){if(__________________________________________________________){ printf("參數(shù)v1或v2越界出錯!\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越界出錯!\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越界出錯!\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;}取第一個鄰接頂點大于0并且小于MaxWeight?編輯pptintGetNextVex(AdjMGraphG,intv1,intv2){intcol;

if(v1<0||v1>=G.Vertices.size||v2<0||v2>=G.Vertices.size) {printf("參數(shù)v1或v2越界出錯!\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?取下一個鄰接頂點編輯ppt2.鄰接矩陣圖操作的測試?yán)?-1以下圖所示的帶權(quán)有向圖為例編寫測試鄰接矩陣圖的程序。ABCDE1040305020邊的權(quán)值邊的起點邊的終點頂點存儲在一個字符數(shù)組中邊信息存儲在一個結(jié)構(gòu)數(shù)組中編輯ppt圖的創(chuàng)建函數(shù)設(shè)計如下：邊信息結(jié)構(gòu)體定義typedefstruct{introw; //行下標(biāo)

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

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

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

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

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

}圖的創(chuàng)建函數(shù)圖存放的AdjMGraph類型的指針變量頂點和頂點數(shù)邊信息和邊數(shù)編輯ppt測試程序設(shè)計如下：#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("頂點集合為：");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.鄰接表存儲結(jié)構(gòu)下圖操作的實現(xiàn)BADCE(a)01234ABCDE0datasorce1432adjdestnext23411∧

∧

∧

∧

(b)4∧

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

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

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

intsorce; /*鄰接邊的弧尾頂點序號*/

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

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

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

編輯ppt

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

對于例9-8所示的有向圖，頂點A作為初始訪問結(jié)點，廣度優(yōu)先遍歷訪問頂點次序為：ABEDC問題：圖的（深度、廣度）遍歷和生成樹的關(guān)系？ABCDE1040305020①②③④⑤同一個頂點的鄰接頂點優(yōu)先編輯ppt三、非連通圖的遍歷對于非連通圖，從圖的任意一個頂點開始深度或廣度優(yōu)先遍歷并不能訪問圖中的所有頂點。只能訪問和初始頂點連通的所有頂點。但是，每一個頂點都作為一次初始頂點進(jìn)行深度優(yōu)先遍歷或廣度優(yōu)先遍歷，并根據(jù)頂點的訪問標(biāo)記來判斷是否需要訪問該頂點，就一定可以訪問非連通圖中的所有頂點。編輯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ù)實現(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);}思想：對圖中每一個頂點作為初始頂點進(jìn)行深度優(yōu)先遍歷為了避免訪問過的頂點重新被訪問，引入標(biāo)記指針對圖中頂點進(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)有向圖為例，編寫測試上述圖的深度優(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最小生成樹1.基本概念一個有n個頂點的連通圖的生成樹是原圖的極小連通子圖，它包含原圖中的所有n個頂點，并且有保持圖連通的最少的邊。（1）若在生成樹中刪除一條邊就會使該生成樹因變成非連通圖而不再滿足生成樹的定義；（2）若在生成樹中增加一條邊就會使該生成樹中因存在回路而不再滿足生成樹的定義；（3）一個連通圖的生成樹可能有許多；（4）有n個頂點的無向連通圖，無論它的生成樹的形狀如何，一定有且只有n-1條邊。編輯ppt1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)(b)(c)無向圖和它的不同的生成樹編輯ppt如果無向連通圖是一個帶權(quán)圖，那么它的所有生成樹中必有一棵邊的權(quán)值總和最小的生成樹，我們稱這棵生成樹為最小代價生成樹，簡稱最小生成樹。

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

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

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

①將頂點v加入集合U中，

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

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

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

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

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

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

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

for(i=1;i<n;i++)編輯ppt{/*尋找當(dāng)前最小權(quán)值的邊所對應(yīng)的弧頭頂點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è)計說明：（1）函數(shù)中定義一個臨時數(shù)組lowCost，數(shù)組元素lowCost[v]中保存了集合U中頂點ui與集合V-U中頂點vj的所有邊中當(dāng)前具有最小權(quán)值的邊(u,v)。（2）集合U的初值為U={序號為0的頂點}。lowCost的初始值為鄰接矩陣數(shù)組中第0行的值，這樣初始時lowCost中就存放了從集合U中頂點0到集合V-U中各個頂點的權(quán)值。（3）每次從lowCost中尋找具有最小權(quán)值的邊，根據(jù)lowCost的定義，這樣的邊其弧頭頂點必然為集合U中的頂點，其弧尾頂點必然為集合V-U中的頂點。當(dāng)選到一條這樣的邊(u,v)，就保存其頂點數(shù)據(jù)和權(quán)值數(shù)據(jù)到參數(shù)closeVertex中，并將lowCost[v]置為-1，表示頂點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)頂點v從集合V-U加入到集合U后，若存在一條邊(u,v)，u是集合U的頂點，v是集合V-U的頂點，且邊(u,v)較原先lowCost[v]的代價更小，則用這樣的權(quán)值修改原先lowCost[v]中的相應(yīng)權(quán)值。（5）以圖9-10（a）所示的無向連通帶權(quán)圖為例，調(diào)用普里姆函數(shù)時數(shù)組lowCost的動態(tài)變化過程如圖示。編輯ppt函數(shù)主要是一個兩重循環(huán)，其中每一重循環(huán)的次數(shù)均為頂點個數(shù)n，所以該算法的時間復(fù)雜度為O(n2)。

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

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

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

集合S中存放已找到最短路徑的頂點，

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

參數(shù)設(shè)計：函數(shù)共有4個參數(shù)，其中2個為輸入?yún)?shù)，分別為帶權(quán)圖G和源點序號v0；2個為輸出參數(shù)，分別為distance[]和path[]，distance[]用來存放得到的從源點v0到其余各頂點的最短距離數(shù)值，path[]用來存放得到的從源點v0到其余各頂點的最短路徑上到達(dá)目標(biāo)頂點的前一頂點下標(biāo)。編輯ppt狄克斯特拉函數(shù)設(shè)計：voidDijkstra(AdjMGraphG,intv0,intdistance[],intpath[])/*帶權(quán)圖G從下標(biāo)v0頂點到其它頂點的最短距離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/*在還未找到最短路徑的頂點集中選有最短距離的頂點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)已不再存在路徑時算法結(jié)束*/

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

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三、測試程序例9-4：以圖9-13的有向帶權(quán)圖為例設(shè)計測試上述Dijkstra函數(shù)的程序。編輯ppt3.每對頂點之間的最短路徑

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

弗洛伊德算法的思想是：設(shè)矩陣cost用來存放帶權(quán)有向圖G的權(quán)值，即矩陣元素cost[i][j]中存放著下標(biāo)為i的頂點到下標(biāo)為j的頂點之間的權(quán)值，可以通過遞推構(gòu)造一個矩陣序列A0,A1,A2,……,AN來求每對頂點之間的最短路徑。其中，Ak[i][j]（0≤k≤n）表示從頂點vi到頂點vj的路徑上所經(jīng)過的頂點下標(biāo)不大于k的最短路徑長度。初始時有，A0[i][j]=cost[i][j]。編輯ppt一種情況是該路徑不經(jīng)過下標(biāo)為k+1的頂點，此時該路徑長度與從頂點vi到頂點vj的路徑上所經(jīng)過的頂點下標(biāo)不大于k的最短路徑長度相同；另一種情況是該路徑經(jīng)過下標(biāo)為k+1的頂點，此時該路徑可分為兩段，一段是從頂點vi到頂點vk+1的最短路徑，另一段是從頂點vk+1到頂點vj的最短路徑，此時的最短路徑長度等于這兩段最短路徑長度之和。當(dāng)已經(jīng)求出Ak,要遞推求解Ak+1時，有：編輯ppt這兩種情況中的路徑長度較小者，就是要求的從頂點vi到頂點vj的路徑上所經(jīng)過的頂點下標(biāo)不大于k+1的最短路徑長度。用公式描述為：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ù)渑判蚓褪且赡硞€集合上的偏序關(guān)系得到該集合上的全序關(guān)系。若集合X上的關(guān)系R是自反的、反對稱的和傳遞的，則稱關(guān)系R是集合X上的偏序關(guān)系（或稱半序關(guān)系）。設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，若對于每一個x∈X，都有(x,x)∈R，則稱R是自反的。設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，如果對于任意的x,y,z∈X，若當(dāng)(x,y)∈R且(y,z)∈R時，有(x,z)∈R，則稱關(guān)系R是傳遞的。

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

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

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

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

3924756081編輯ppt

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

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

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

編輯ppt編輯ppt

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

上述算法僅能得到有向圖的一個拓?fù)湫蛄?。改進(jìn)上述算法，可以得到有向圖的所有拓?fù)湫蛄?。如果一個有向圖存在一個拓?fù)湫蛄?，通常表示該有向圖對應(yīng)的某個施工流程圖的一種施工方案切實可行；而如果一個有向圖不存在一個拓?fù)湫蛄校瑒t說明該有向圖對應(yīng)的某個施工流程圖存在設(shè)計問題，不存在切實可行的任何一種施工方案。

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

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

2．AOE網(wǎng)對工程管理問題的表示在有向圖中，如果頂點表示事件，有向邊表示活動，有向邊上的權(quán)值表示活動持續(xù)的時間，這樣的有向圖稱為邊表示活動的網(wǎng)(ActivityOnEdge)，簡稱AOE網(wǎng)。對于AOE網(wǎng)，需要研究的問題是：（1）完成整個工程需要多少時間？（2）哪些活動是影響工程進(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基本概念：路徑長度：AOE網(wǎng)的一條路徑上所有活動的總和稱為該路徑的長度。關(guān)鍵路徑：在AOE網(wǎng)中，從源點到匯點的所有路徑中，具有最大路徑長度的路徑稱為關(guān)鍵路徑。關(guān)鍵