ACM培訓(xùn)資料數(shù)據(jù)結(jié)構(gòu)與算法課件

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

(DATASTRUCTURE)計(jì)算機(jī)科學(xué)與工程系

10第七章圖圖的基本概念圖的存儲(chǔ)表示圖的遍歷與連通性最小生成樹最短路徑活動(dòng)網(wǎng)絡(luò)207.1

圖的基本概念圖的定義

圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中

V={x|x

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

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

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V&&Path(x,y)}

是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y(tǒng)的一條通路。30

鄰接頂點(diǎn)

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

設(shè)有兩個(gè)圖G＝(V,E)和G’＝(V’,E’),若V’V且E’

E,則稱圖G’是圖G的子圖。50頂點(diǎn)的度

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

vp1vp2...vpm

vj)

為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。60路徑長(zhǎng)度非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。簡(jiǎn)單路徑

若路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡(jiǎn)單路徑?；芈?/p>

若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合,則稱這樣的路徑為回路或環(huán)。簡(jiǎn)單回路

除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫簡(jiǎn)單回路

707.2

圖的存儲(chǔ)結(jié)構(gòu)1）存儲(chǔ)特點(diǎn)在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表；還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。2）鄰接矩陣設(shè)圖A=(V,E)是一個(gè)有n個(gè)頂點(diǎn)的圖，則圖的鄰接矩陣是一個(gè)二維數(shù)組A[n][n]，定義：7.2.1

鄰接矩陣(AdjacencyMatrix)表示法90100

網(wǎng)絡(luò)的鄰接矩陣1104）圖的創(chuàng)建

思路：1307.2.2

鄰接表(AdjacencyList)1)存儲(chǔ)特點(diǎn)對(duì)于圖G中的每個(gè)頂點(diǎn)vi，把所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表稱為頂點(diǎn)vi的鄰接表；將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表

140特點(diǎn)無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)有向圖中頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表例G1bdac1234acdbvexdatafirstarc

4

1^

1^^

3^adjvexnext1502）數(shù)據(jù)類型描述＃defineMaxVerNum100/*最大頂點(diǎn)數(shù)為100*/鄰接表類型：

typedefstructArcNode{intadjvex;/*鄰接點(diǎn)域*/InfoType*Info;/*表示邊上信息的域info*/structArcNode*next;/*指向下一個(gè)鄰接點(diǎn)的指針域*/}ArcNode;表頭結(jié)點(diǎn)類型：

typedefstructVnode{VertexTypevertex;/*頂點(diǎn)域*/ArcNode*firstedge;/*邊表頭指針*/}Vnode,AdjList[MaxVertexNum];圖的類型：

typedefstruct{AdjListvertices;/*鄰接表*/intvexnum,arcnum;/*頂點(diǎn)數(shù)和邊數(shù)*/}ALGraph;/*ALGraph是以鄰接表方式存儲(chǔ)的圖類型*/1707.2.3

十字鏈表(OrthogonalList)

十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它實(shí)際上是鄰接表與逆鄰接表的結(jié)合1)存儲(chǔ)特點(diǎn)圖中每一條弧有一個(gè)結(jié)點(diǎn)，把弧頭相同的弧連在同一鏈表上,弧尾相同的弧也連在同一鏈表上。結(jié)點(diǎn)結(jié)構(gòu)為：頂點(diǎn)結(jié)點(diǎn)為鏈表頭結(jié)點(diǎn)，其結(jié)構(gòu)為：1807.2.4

鄰接多重表(AdjacencyMultilist)鄰接多重表是無向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1)存儲(chǔ)特點(diǎn)圖中每一條邊用一個(gè)邊結(jié)點(diǎn)表示，其結(jié)構(gòu)為：每個(gè)頂點(diǎn)用一個(gè)結(jié)點(diǎn)表示，其結(jié)構(gòu)為：markivexilinkjvexjlinkdatafirstedge1907.3

圖的遍歷與連通性從圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，叫做圖的遍歷

(GraphTraversal)。為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個(gè)頂點(diǎn)i

被訪問，就立即讓visited[i]

為1，防止它被多次訪問。2107.3.1

深度優(yōu)先搜索DFS1）基本思想：任選圖中一個(gè)頂點(diǎn)v,訪問此頂點(diǎn),并作訪問標(biāo)記。從v出發(fā)，訪問它的任一未被訪問過的鄰接頂點(diǎn)w

，作訪問標(biāo)記，并以w為新的出發(fā)點(diǎn)，繼續(xù)進(jìn)行深度優(yōu)先搜索。當(dāng)某個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)都被訪問過后，則退回到前一次剛訪問過的頂點(diǎn)k，從k的另一個(gè)沒有被訪問的鄰接頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索。重復(fù)上述過程,直到圖中所有頂點(diǎn)都被訪問過為止220深度優(yōu)先搜索的示例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V52302）算法實(shí)現(xiàn)難點(diǎn)：如何標(biāo)記已訪問結(jié)點(diǎn)v?如何查找v的所有鄰接點(diǎn)？解決辦法：設(shè)置一個(gè)布爾向量數(shù)組visited[n]，初值為0。若序號(hào)為i的結(jié)點(diǎn)已被訪問過，則visited[i]=1。根據(jù)圖的存儲(chǔ)方式不同，采取相應(yīng)方法查找：鄰接矩陣：vi

的鄰接點(diǎn)是鄰接矩陣中第i行上非0元素對(duì)應(yīng)的列值，若A[i][j]<>0，則vj為vi鄰接點(diǎn)。鄰接表：是以G.vertices[i]為表頭結(jié)點(diǎn)的單鏈表上的所有結(jié)點(diǎn)。250V1V2V4V5V3V7V6V8例1234V1V3V4V2vexdatafirstarc

2

7

8

3^^^adjvexnext5V5

6^

4

8

2^V6V7V8678

7^^^深度遍歷：V1V3V7V6V2V4V8V5260廣度優(yōu)先搜索的示例例V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V6V7V8V5290廣度優(yōu)先搜索的示例遍歷結(jié)果：A、B、C、D例300為了實(shí)現(xiàn)逐層訪問，算法中使用了一個(gè)隊(duì)列，以記憶正在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。2）算法實(shí)現(xiàn)開始標(biāo)志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結(jié)束NNYY310

BFS開始訪問Vi,置標(biāo)志求V鄰接點(diǎn)WW存在嗎V下一鄰接點(diǎn)WW訪問過結(jié)束NYNY初始化隊(duì)列Vi入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪問W,置標(biāo)志W(wǎng)入隊(duì)NY320如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為d1+d2+…+dn=O(e)，其中的di是頂點(diǎn)i的度。如果使用鄰接矩陣，則對(duì)于每一個(gè)被訪問過的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的n個(gè)元素，總的時(shí)間代價(jià)為O(n2)。3）算法分析3307.4

圖的連通性與生成樹7.4.1

圖的連通性問題連通圖與連通分量

在無向圖中,若從頂點(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)連通分量。340連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例2451363507.4.2

最小生成樹

1）圖的生成樹連通圖G的一個(gè)子圖如果是一棵包含G的所有頂點(diǎn)的樹（所有頂點(diǎn)均由邊連接在一起，但不存在回路,有n-1條邊），則該子圖稱為G的生成樹。生成樹是連通圖的極小連通子圖。所謂極小是指：若在樹中任意增加一條邊，則將出現(xiàn)一個(gè)回路；若去掉一條邊，將會(huì)使之變成非連通圖。使用不同的遍歷圖的方法，可以得到不同的生成樹360說明一個(gè)圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點(diǎn)：生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹GHKI370V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8380例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林390

問題提出——要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，

頂點(diǎn)——

城市

權(quán)——

城市間建立通信線路所需花費(fèi)代價(jià)

生成樹各邊的權(quán)值總和稱為生成樹的權(quán)。權(quán)最小的生成樹稱為最小生成樹。2)構(gòu)造最小生成樹

問題分析n個(gè)城市間,最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng),只需n-1條線路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點(diǎn)）均連起來，且總耗費(fèi)各邊權(quán)值之和）最小1654327131791812752410400最小生成樹的重要性質(zhì)：

設(shè)G=（V，E）是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)真子集。若（u，v）是G中所有的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)不在U的邊中，具有最小權(quán)值的一條邊，則一定存在G的一棵最小生成樹包括此邊。uvUV—U410①普里姆(Prim)算法普里姆算法的基本思想：假設(shè)圖G={V,E}，所求最小生成樹T=(U,TE),其中U=V,TEE

從連通網(wǎng)絡(luò)G={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中為止。420

算法實(shí)現(xiàn):(略)

算法分析：

上述算法的初始化時(shí)間是O(1)，k循環(huán)中有兩個(gè)循環(huán)語句，其時(shí)間大致為：

令O(1)為某一正常數(shù)C，展開上述求和公式可知其數(shù)量級(jí)仍是n的平方。所以，整個(gè)算法的時(shí)間復(fù)雜性是O(n2)430②克魯斯卡爾(Kruskal)

算法克魯斯卡爾算法的基本思想：設(shè)有一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)G={V,E}，最初先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn)，沒有邊的非連通圖T={V,},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選取一條具有最小權(quán)值的邊(u,v)，若該邊的兩個(gè)頂點(diǎn)落在兩個(gè)不同的連通分量上，則將此邊加入到T中；否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此上步，直到T中所有頂點(diǎn)在同一個(gè)連通分量上為止。440應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程例1654326513566425165432123454507.5

有向無環(huán)圖及其應(yīng)用計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。7.5.1

活動(dòng)網(wǎng)絡(luò)(ActivityNetwork)

用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV網(wǎng)絡(luò))460

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)課程名稱先修課程470學(xué)生課程學(xué)習(xí)工程圖480可以用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊<Vi,Vj>表示活動(dòng)間的優(yōu)先關(guān)系，Vi必須先于活動(dòng)Vj

進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò)(ActivityOnVertices)。在AOV網(wǎng)絡(luò)中，如果活動(dòng)Vi必須在活動(dòng)Vj之前進(jìn)行，則存在有向邊<Vi,Vj>，AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)絡(luò)中如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。因此，對(duì)給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。490檢測(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)系都能得到滿足。拓?fù)渑判颍簭哪硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱為拓?fù)渑判颉?）拓?fù)渑判?00例如，對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判?，得到的拓?fù)溆行蛐蛄袨?/p>

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

或C1,C8,C9,C2,C5,C3,C4,C7,C65102）進(jìn)行拓?fù)渑判虻姆椒?/p>

輸入AOV網(wǎng)絡(luò)，令n為頂點(diǎn)個(gè)數(shù)在AOV網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn)（即此頂點(diǎn)入度為0）,并輸出之；從圖中刪去該頂點(diǎn),同時(shí)刪去所有它發(fā)出的有向邊;重復(fù)以上兩步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?；或圖中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。520C0C1C2C3C4C5例：拓?fù)渑判虻倪^程(a)有向無環(huán)圖(b)輸出頂點(diǎn)C4(c)輸出頂點(diǎn)C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d)輸出頂點(diǎn)C3530C1C2C5(e)輸出頂點(diǎn)C2C5C1(f)輸出頂點(diǎn)C1C5(g)輸出頂點(diǎn)C5(h)拓?fù)渑判蛲瓿?40AOV網(wǎng)絡(luò)及其鄰接表表示C0C1C2C3C4C5

destnext

C0C1C2C30C4C50012345countdataadj

130103

1

30

5

1

50

0

1

50在鄰接表中增設(shè)了一個(gè)count域，記錄各個(gè)頂點(diǎn)入度。入度為零的頂點(diǎn)即無前驅(qū)的頂點(diǎn)。5503）拓?fù)渑判蛩惴ㄈ攵葹?的頂點(diǎn)即為沒有前驅(qū)的頂點(diǎn)。刪除頂點(diǎn)及相應(yīng)弧的操作可轉(zhuǎn)換為弧頭頂點(diǎn)入度減1。為避免重復(fù)檢查入度為0的頂點(diǎn)，在算法中使用一個(gè)鏈?zhǔn)綏⑷攵葹?的頂點(diǎn)鏈接在一起，供選擇和輸出無前驅(qū)的頂點(diǎn)。只要出現(xiàn)入度為零的頂點(diǎn)，就將它加入棧中。560算法描述使用這種棧的拓?fù)渑判蛩惴梢悦枋鋈缦拢?/p>

(1)建立入度為零的頂點(diǎn)棧;輸出頂點(diǎn)計(jì)數(shù)器=0(2)當(dāng)入度為零的頂點(diǎn)棧不空時(shí),重復(fù)執(zhí)行從棧中取出頂點(diǎn)元素,并輸出之;計(jì)數(shù)器+1從AOV網(wǎng)絡(luò)中刪去這個(gè)頂點(diǎn)和它發(fā)出的邊,邊的終頂點(diǎn)入度減1;如果邊的終頂點(diǎn)入度減至0,則該頂點(diǎn)進(jìn)入度為零的頂點(diǎn)棧;(3)如果輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù),則報(bào)告網(wǎng)絡(luò)中存在有向環(huán)。570分析此拓?fù)渑判蛩惴芍?，如果AOV網(wǎng)絡(luò)有n個(gè)頂點(diǎn)，e條邊，在拓?fù)渑判虻倪^程中，搜索入度為零的頂點(diǎn)，建立鏈?zhǔn)綏Ｋ枰臅r(shí)間是O(n)。在正常的情況下，有向圖有n個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)進(jìn)一次棧，出一次棧，共輸出n次。頂點(diǎn)入度減一的運(yùn)算共執(zhí)行了e次。所以總的時(shí)間復(fù)雜度為O(n+e)。4）算法分析5807.5.2

用邊表示活動(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ò)，簡(jiǎn)稱AOE(ActivityOnEdges)網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：

(1)完成整個(gè)工程至少需要多少時(shí)間(假設(shè)沒有環(huán))?(2)為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?590在AOE網(wǎng)絡(luò)中,有些活動(dòng)順序進(jìn)行，有些活動(dòng)并行進(jìn)行。從源點(diǎn)到各個(gè)頂點(diǎn)，以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長(zhǎng)度也可能不同。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同，但只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。因此，完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑(CriticalPath)。1）關(guān)鍵路徑6001324a1=8a2=125678a10=12a9=6a8=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)。6102）如何求關(guān)鍵路徑定義幾個(gè)與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量：事件Vi

的最早發(fā)生時(shí)間Ve(i)是從源點(diǎn)V0

到頂點(diǎn)Vi的最長(zhǎng)路徑長(zhǎng)度。事件Vi的最遲發(fā)生時(shí)間Vl[i]是在保證匯點(diǎn)Vn

在Ve[n]時(shí)刻完成的前提下，事件Vi

的允許的最遲開始時(shí)間?；顒?dòng)ak的最早開始時(shí)間e[k]：設(shè)活動(dòng)ak在邊<Vi,Vj>上，則e[k]是從源點(diǎn)V0到頂點(diǎn)Vi

的最長(zhǎng)路徑長(zhǎng)度。因此,e[k]=Ve[i]?；顒?dòng)ak的最遲開始時(shí)間l[k]是在不會(huì)引起時(shí)間延誤的前提下,該活動(dòng)允許的最遲開始時(shí)間。

l[k]=Vl[j]-dur(<i,j>)其中,dur(<i,j>)是完成ak所需的時(shí)間。620時(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].為求得e[k]與l[k]，需要先求得從源點(diǎn)V0到各個(gè)頂點(diǎn)Vi的Ve[i]和Vl[i]。630求Ve[i]的遞推公式從Ve[1]=0開始，向前遞推

<Vi,Vj>S2,j=2,,n

其中S2是所有指向頂點(diǎn)Vi的有向邊<Vj

,Vi

>的集合從Vl[n]=Ve[n]開始，反向遞推

<Vi,Vj>S1,j=n-1,n-2,,1

其中S1是所有從頂點(diǎn)Vi

發(fā)出的有向邊<Vi

,Vj

>的集合這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚣澳嫱負(fù)溆行虻那疤嵯逻M(jìn)行。640

算法分析

在拓?fù)渑判蚯骎e[i]和逆拓?fù)溆行蚯骎l[i]時(shí),所需時(shí)間為O(n+e),求各個(gè)活動(dòng)的e[k]和l[k]時(shí)所需時(shí)間為O(e),總共花費(fèi)時(shí)間仍然是O(n+e)。6507.6

最短路徑(ShortestPath)問題提出:

用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等

問題：從某頂點(diǎn)出發(fā)，沿圖到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑最短路徑：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑，使得沿此路徑各邊上的權(quán)值總和達(dá)到最小。問題解法單源最短路徑—Dijkstra算法任意頂點(diǎn)對(duì)之間的最短路徑—Floyd算法6607.6.1

單源最短路徑問題問題的提法：

給定一個(gè)帶權(quán)有向圖D與源點(diǎn)v，求從v到D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑，Dijkstra提出按路徑長(zhǎng)度的遞增次序，逐步產(chǎn)生最短路徑的算法。6701)迪杰斯特拉(Dijkstra)算法基本思想

按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑:把V分成兩組：

(1)S：已求出最短路徑的頂點(diǎn)的集合(2)V-