數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)課件章節(jié)6

第6章圖6.1圖的基本介紹6.1.1圖的定義圖G是一個(gè)有序二元組(V,E)，其中V稱為頂集(VerticesSet)，E稱為邊集(Edgesset)，E與V不相交。它們亦可寫成V(G)和E(G)。其中，頂集的元素被稱為頂點(diǎn)(Vertex)，邊集的元素被稱為邊(edge)。E的元素都是二元組，用(x,y)表示，其中x,y∈V。下面是有關(guān)圖的一些基本概念。有向圖、無向圖：如果給圖的每條邊規(guī)定一個(gè)方向，那么得到的圖稱為有向圖，如圖(a)所示。在有向圖中，與一個(gè)結(jié)點(diǎn)相關(guān)聯(lián)的邊有出邊和入邊之分。相反，邊沒有方向的圖稱為無向圖，如圖(b)所示。完全圖：完全圖是指邊數(shù)達(dá)到最大值的圖，即在頂點(diǎn)數(shù)為n的無向圖中，邊數(shù)為n(n-1)/2；在頂點(diǎn)數(shù)為n的有向圖中，邊數(shù)為n(n-1)，如圖(c)所示。單圖：一個(gè)圖如果任意兩頂點(diǎn)之間只有一條邊（在有向圖中為兩頂點(diǎn)之間每個(gè)方向只有一條邊）；邊集中不含環(huán)，則稱為單圖。連通圖：若V(G)中任意兩個(gè)不同的頂點(diǎn)Vi和Vj都連通（即有路徑），則稱G為連通圖(ConnectedGraph)。連通分量：無向圖的極大連通子圖稱為的連通分量(ConnectedComponent)。任何連通圖的連通分量只有一個(gè)，即是其自身，非連通的無向圖有多個(gè)連通分量，如圖所示。強(qiáng)連通圖：有向圖中，若對于V(G)中任意兩個(gè)不同的頂點(diǎn)Vi和Vj，都存在從Vi到Vj以及從Vj到Vi的路徑，則稱是強(qiáng)連通圖。強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量，強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即是其自身。非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連通分量。要注意強(qiáng)連通圖和強(qiáng)連通分量只是針對有向圖而言的。強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量，強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即是其自身。非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連通分量。要注意強(qiáng)連通圖和強(qiáng)連通分量只是針對有向圖而言的。子圖（Sub-Graph）：當(dāng)圖G'=(V',E')其中V‘包含于V，E’包含于E，則G'稱作圖G=(V,E)的子圖。每個(gè)圖都是本身的子圖。度（Degree）：一個(gè)頂點(diǎn)的度是指與該頂點(diǎn)相關(guān)聯(lián)的邊的條數(shù)，頂點(diǎn)v的度記作d(v)。入度（In-degree）和出度（Out-degree）：對于有向圖來說，一個(gè)頂點(diǎn)的度可細(xì)分為入度和出度。一個(gè)頂點(diǎn)的入度是指與其關(guān)聯(lián)的各邊之中，以其為終點(diǎn)的邊數(shù)；出度則是相對的概念，指以該頂點(diǎn)為起點(diǎn)的邊數(shù)。自環(huán)（Loop）：若一條邊的兩個(gè)頂點(diǎn)為同一頂點(diǎn)，則此邊稱作自環(huán)。路徑（Path）：從u到v的一條路徑是指一個(gè)序列v0,e1,v1,e2,v2,...ek,vk，其中ei的頂點(diǎn)為vi及vi-1，k稱作路徑的長度。如果它的起止頂點(diǎn)相同，該路徑是“閉”的，反之，則稱為“開”的。一條路徑稱為一簡單路徑(simplepath)，如果路徑中除起始與終止頂點(diǎn)可以重合外，所有頂點(diǎn)兩兩不等。網(wǎng)：網(wǎng)指的是邊上帶權(quán)值的圖。通常權(quán)值為非負(fù)實(shí)數(shù)，可以表示為從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、時(shí)間和代價(jià)等。6.1.2圖的存儲方法1．鄰接矩陣法

鄰接矩陣（AdjacencyMatrix）是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個(gè)圖，其中V={v1,v2,…,vn}。G的鄰接矩陣是一個(gè)具有下列性質(zhì)的n階方陣：①對無向圖而言，鄰接矩陣一定是對稱的，而且主對角線一定為零（在此僅討論無向簡單圖），副對角線不一定為0，有向圖則不一定如此。②在無向圖中，任一頂點(diǎn)i的度為第i列（或第i行）所有非零元素的個(gè)數(shù)，在有向圖中頂點(diǎn)i的出度為第i行所有非零元素的個(gè)數(shù)，而入度為第i列所有非零元素的個(gè)數(shù)。③用鄰接矩陣法表示圖共需要n2個(gè)空間，由于無向圖的鄰接矩陣一定具有對稱關(guān)系，所以扣除對角線為零外，僅需要存儲上三角形或下三角形的數(shù)據(jù)即可，因此僅需要n(n-1)/2個(gè)空間。④稠密圖適合使用鄰接矩陣的存儲表示。圖的領(lǐng)接矩陣存儲結(jié)構(gòu)定義如下：

2．鄰接表法圖的鄰接表存儲方法是一種順序分配和鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲結(jié)構(gòu)。如果這個(gè)表頭結(jié)點(diǎn)所對應(yīng)的頂點(diǎn)存在相鄰頂點(diǎn)，則把相鄰頂點(diǎn)依次存放于表頭結(jié)點(diǎn)所指向的單向鏈表中，這個(gè)單鏈表稱為該頂點(diǎn)的邊表。邊表的頭指針和頂點(diǎn)的數(shù)據(jù)信息采用順序存儲（稱為頂點(diǎn)表），所以在鄰接表中存在兩種結(jié)點(diǎn)：頂點(diǎn)表結(jié)點(diǎn)和邊表結(jié)點(diǎn)，如圖所示。無向圖和有向圖的鄰接表實(shí)例分別如左下圖和右下圖所示。圖的鄰接表存儲結(jié)構(gòu)定義如下：3．鄰接表的基本操作（1）創(chuàng)建無向圖（2）創(chuàng)建有向圖創(chuàng)建有向圖的操作與創(chuàng)建無向圖類似，只不過只需要插入一種方向的邊。（3）插入邊結(jié)點(diǎn)插入邊結(jié)點(diǎn)的算法add_arc(i,j,value)是指在邊表中插入一個(gè)由序號為i的頂點(diǎn)指向序號為j的頂點(diǎn)的權(quán)值為value的邊結(jié)點(diǎn)。插入過程采用頭插法的方法。（4）查找頂點(diǎn)序號為i的第一個(gè)鄰接點(diǎn)（5）查找下一個(gè)鄰接點(diǎn)（6）獲取頂點(diǎn)u到頂點(diǎn)v的邊權(quán)值圖的鄰接表存儲方法具有以下特點(diǎn)：1．若圖G為無向圖，則鄰接表存儲方法所需的存儲空間為O(|V|+2|E|)；若圖G為有向圖，則所需的存儲空間為O(|V|+|E|)。前者是后者的兩倍是由于在無向圖中，每條邊在鄰接表中出現(xiàn)了兩次。2．對稀疏圖而言，采用鄰接表法表示圖可以極大地節(jié)省存儲空間。3．在鄰接表中，如果給定一個(gè)頂點(diǎn)，則能夠很容易獲得它的所有鄰邊；而在鄰接矩陣需要掃描一整行，花費(fèi)的時(shí)間為O(n)。但是如果要確定給定兩個(gè)頂點(diǎn)間是否存在邊，在鄰接矩陣?yán)锟梢粤⒖滩榈?；而在鄰接表中需要在相?yīng)頂點(diǎn)的邊表上遍歷查詢另一個(gè)結(jié)點(diǎn)，效率較低。4．圖的鄰接表表示不是唯一的，每個(gè)頂點(diǎn)的邊表各結(jié)點(diǎn)次序可以是任意的，它取決于建立鄰接表的算法以及邊的輸入次序。除了鄰接矩陣法和鄰接表法，還有十字鏈表和鄰接多重表，有興趣的同學(xué)可以查閱相關(guān)資料了解。6.2圖的遍歷6.2.1廣度優(yōu)先搜索廣度優(yōu)先搜索算法（Breadth-FirstSearch，縮寫為BFS），又譯作寬度優(yōu)先搜索，或橫向優(yōu)先搜索，是一種圖形搜索算法。廣度優(yōu)先搜索算法類似于二叉樹的層次遍歷算法。對圖的廣度優(yōu)先遍歷方法描述為：從圖中某個(gè)頂點(diǎn)v出發(fā)，在訪問該頂點(diǎn)v之后，依次訪問頂點(diǎn)v的所有未被訪問過的鄰接點(diǎn)，然后再訪問每個(gè)鄰接點(diǎn)的鄰接點(diǎn)，且訪問順序應(yīng)保持先被訪問的頂點(diǎn)其鄰接點(diǎn)也優(yōu)先被訪問，直到圖中的所有頂點(diǎn)都被訪問為止。在廣度優(yōu)先搜索中，要求先被訪問的頂點(diǎn)其鄰接點(diǎn)也被優(yōu)先訪問，因此，必須對每個(gè)頂點(diǎn)的訪問順序進(jìn)行記錄，以便后面按此順序訪問各頂點(diǎn)的鄰接點(diǎn)。應(yīng)利用一個(gè)隊(duì)列結(jié)構(gòu)記錄頂點(diǎn)訪問順序，就可以利用隊(duì)列結(jié)構(gòu)的操作特點(diǎn)，將訪問的每個(gè)頂點(diǎn)入隊(duì)，然后，再依次出隊(duì)，并訪問它們的鄰接點(diǎn)。同時(shí)為了避免重復(fù)訪問某個(gè)頂點(diǎn)，也需要創(chuàng)建一個(gè)一維數(shù)組visited[0..n-1]（n是圖中頂點(diǎn)的數(shù)目），用來記錄每個(gè)頂點(diǎn)是否已經(jīng)被訪問過。廣度優(yōu)先搜索的算法描述如下：下面通過實(shí)例來演示圖的廣度優(yōu)先搜索的過程，給定圖如下所示。假設(shè)從結(jié)點(diǎn)a開始進(jìn)行廣度優(yōu)先搜索，先將a入隊(duì)，并把a(bǔ)標(biāo)記為已訪問。此時(shí)隊(duì)列非空，將隊(duì)頭結(jié)點(diǎn)a出隊(duì)，由于結(jié)點(diǎn)b和結(jié)點(diǎn)c都與結(jié)點(diǎn)鄰接且未被訪問過，故將結(jié)點(diǎn)b和結(jié)點(diǎn)c入隊(duì)；此時(shí)隊(duì)列非空，將隊(duì)頭結(jié)點(diǎn)b出隊(duì)，由于結(jié)點(diǎn)d和結(jié)點(diǎn)e都與結(jié)點(diǎn)b鄰接，故將結(jié)點(diǎn)d和結(jié)點(diǎn)e鄰接；此時(shí)隊(duì)列非空，將隊(duì)頭結(jié)點(diǎn)c出隊(duì)，由于結(jié)點(diǎn)f、g、h與結(jié)點(diǎn)c鄰接，故將結(jié)點(diǎn)f、g、h入隊(duì)；此時(shí)隊(duì)列非空，將隊(duì)頭結(jié)點(diǎn)d入隊(duì)，由于沒有結(jié)點(diǎn)與其鄰接，故繼續(xù)循環(huán)出隊(duì)；當(dāng)結(jié)點(diǎn)f作為隊(duì)頭結(jié)點(diǎn)出隊(duì)時(shí)，由于結(jié)點(diǎn)i與其鄰接，故將結(jié)點(diǎn)i入隊(duì)……最終取出隊(duì)頭結(jié)點(diǎn)i之后，隊(duì)列為空，從而循環(huán)結(jié)束。此次遍歷的結(jié)果為abcdefghi。從上述演示的過程中，不難發(fā)現(xiàn)圖的廣度優(yōu)先搜索和二叉樹的層次遍歷是類似的，這也說明了圖的廣度優(yōu)先搜索算法是二叉樹的層次遍歷算法的擴(kuò)展。實(shí)現(xiàn)廣度優(yōu)先搜索算法總是需要一個(gè)輔助隊(duì)列Q，n個(gè)頂點(diǎn)均需入隊(duì)一次，在最壞情況下，空間復(fù)雜度為O(|V|)。采用鄰接表存儲方式時(shí)，每個(gè)頂點(diǎn)均需搜索一次（或入隊(duì)一次），故時(shí)間復(fù)雜度為O(|V|)，在搜索任一頂點(diǎn)的鄰接點(diǎn)時(shí)，每條邊至少被訪問一次，故時(shí)間復(fù)雜度為O(|E|)，則算法總的時(shí)間復(fù)雜度為O(|V|+|E|)。采用鄰接矩陣存儲方式時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)的時(shí)間復(fù)雜度為O(|V|)，故算法中的時(shí)間復(fù)雜度為O(|V|2)。6.2.2深度優(yōu)先搜索深度優(yōu)先搜索算法（Depth-FirstSearch，DFS）是一種用于遍歷或搜索樹或圖的算法。這個(gè)算法會盡可能深地搜索一個(gè)圖。首先訪問某一起始結(jié)點(diǎn)v，然后由結(jié)點(diǎn)v出發(fā)，去訪問與結(jié)點(diǎn)v鄰接且未被訪問過的任一結(jié)點(diǎn)v1，再去訪問與結(jié)點(diǎn)v1鄰接且未被訪問過的任一結(jié)點(diǎn)v2……重復(fù)如上過程。當(dāng)不能再往下繼續(xù)訪問時(shí)，搜索將回溯到最近被訪問的結(jié)點(diǎn)，如果該節(jié)點(diǎn)還有未被訪問的鄰接結(jié)點(diǎn)，則繼續(xù)朝該鄰接結(jié)點(diǎn)搜索下去，直至圖中所有的結(jié)點(diǎn)都已經(jīng)被訪問過。深度優(yōu)先搜索算法由于其向下搜索并且需要回溯的特性，通常以遞歸的形式來實(shí)現(xiàn)，遞歸形式的實(shí)現(xiàn)代碼也比較簡潔。深度優(yōu)先搜索算法由于其向下搜索并且需要回溯的特性，通常以遞歸的形式來實(shí)現(xiàn)，遞歸形式的實(shí)現(xiàn)代碼也比較簡潔。

深度優(yōu)先搜索的遞歸形式算法如下：下面通過實(shí)例來演示圖的深度優(yōu)先搜索的過程，遍歷過程如圖6.8所示。假設(shè)從結(jié)點(diǎn)a開始進(jìn)行深度優(yōu)先搜索，把結(jié)點(diǎn)a標(biāo)記為已訪問；向下訪問結(jié)點(diǎn)a的第一個(gè)鄰接結(jié)點(diǎn)b，把結(jié)點(diǎn)b標(biāo)記為已訪問；繼續(xù)向下訪問結(jié)點(diǎn)b的第一個(gè)鄰接結(jié)點(diǎn)d，把結(jié)點(diǎn)d標(biāo)記為已訪問；發(fā)現(xiàn)結(jié)點(diǎn)d沒有鄰接結(jié)點(diǎn)，則回溯到結(jié)點(diǎn)b，尋找是否存在與結(jié)點(diǎn)b鄰接的未訪問結(jié)點(diǎn)，如不存在則繼續(xù)回溯……最終最上層的遞歸程序結(jié)束，所有的結(jié)點(diǎn)都被訪問完畢。此次遍歷的結(jié)果為abdecfigh。

從深度優(yōu)先搜索的過程中不難發(fā)現(xiàn)，圖的深度優(yōu)先搜索和二叉樹的先序遍歷是有相通之處的，都是從初始結(jié)點(diǎn)開始，逐步往深處搜索。

深度優(yōu)先搜索算法是一個(gè)遞歸算法，需要借助一個(gè)遞歸工作棧，故其空間復(fù)雜度為O(|V|)。當(dāng)圖以鄰接表表示時(shí)，查找所有頂點(diǎn)的鄰接點(diǎn)所需的時(shí)間為O(|E|)，訪問頂點(diǎn)所需的時(shí)間為O(|V|)，此時(shí)，總的時(shí)間復(fù)雜度為O(|V|+|E|)。當(dāng)圖以鄰接矩陣表示時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需的時(shí)間為O(|V|)，故總的時(shí)間復(fù)雜度為O(|V|2)。6.3圖的應(yīng)用6.3.1最小生成樹最小生成樹是一幅連通加權(quán)無向圖中一棵權(quán)值最小的生成樹。在一給定的帶權(quán)無向圖G=(V,E)中，生成樹不同，每棵樹的權(quán)（即樹中所有邊上的權(quán)值之和）也可能不同。設(shè)S為G的所有生成樹的集合，若T為S中邊的權(quán)值之和最小的那棵生成樹，則T成為G的最小生成樹（MinimumSpanningTree,MST）。一個(gè)連通圖可能有多個(gè)生成樹。當(dāng)圖中的邊具有權(quán)值時(shí)，總會有一個(gè)生成樹的邊的權(quán)值之和小于或者等于其它生成樹的邊的權(quán)值之和。廣義上而言，對于非連通無向圖來說，它的每一連通分量同樣有最小生成樹，它們的并被稱為最小生成森林。以有線電視電纜的架設(shè)為例，若只能沿著街道布線，則以街道為邊，而路口為頂點(diǎn)，其中必然有一最小生成樹能使布線成本最低。實(shí)現(xiàn)最小生成樹的算法主要有Prim（普里姆）算法和Kruskal（克魯斯卡爾）算法。1．Prim算法該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克發(fā)現(xiàn)；并在1957年由美國計(jì)算機(jī)科學(xué)家羅伯特·普里姆獨(dú)立發(fā)現(xiàn)；1959年，艾茲格·迪科斯徹再次發(fā)現(xiàn)了該算法。Prim算法步驟如下：1）輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為V，邊集合為E；2）初始化：Vnew={x}，其中x為集合V中的任一結(jié)點(diǎn)（起始點(diǎn)），Enew={},為空；3）重復(fù)下列操作，直到Vnew=V：a.在集合E中選取權(quán)值最小的邊<u,v>，其中u為集合Vnew中的元素，而v不在Vnew集合當(dāng)中，并且v∈V（如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一）；b.將v加入集合Vnew中，將<u,v>邊加入集合Enew中；4）輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。Prim算法構(gòu)造最小生成樹的過程如圖所示。初始時(shí)取頂點(diǎn)1加入樹T，此時(shí)樹中只含有一個(gè)頂點(diǎn)，之后再選擇一個(gè)與當(dāng)前T中頂點(diǎn)集合中距離最近的頂點(diǎn)，并將該頂點(diǎn)和相應(yīng)的邊加入樹T，每次操作后樹T的頂點(diǎn)數(shù)和邊數(shù)都加一。以此類推，直到圖中所有頂點(diǎn)都被加入到樹T中，得到的樹T就是最小生成樹。如在第一輪中，與V1相連的點(diǎn)有V2、V3、V4，其中V1到V3的距離最近，故將V3和該邊加入樹中；在第二輪中，在V1和V3相連的邊中再取距離最近的邊，故將V6和V3到V6的邊加入樹中……直至構(gòu)造最小生成樹完成。Prim算法的時(shí)間復(fù)雜度為O(|V|2)，不依賴于邊數(shù)，故該算法更適合求解邊稠密的圖的最小生成樹。2．Kruskal算法Kruskal算法由JosephKruskal在1956年發(fā)表。與Prim算法從頂點(diǎn)開始擴(kuò)展最小生成樹不同，Kruskal算法是一種按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹的方法。Kruskal算法步驟如下：1）新建圖G，G中擁有原圖中相同的結(jié)點(diǎn)，但沒有邊；2）將原圖中所有的邊按權(quán)值從小到大排序；3）從權(quán)值最小的邊開始，如果這條邊連接的兩個(gè)結(jié)點(diǎn)于圖G中不在同一個(gè)連通分量中，則添加這條邊到圖G中；4）重復(fù)3，直至圖G中所有的結(jié)點(diǎn)都在同一個(gè)連通分量中。Kruskal算法構(gòu)造最小生成樹的過程如圖所示。

通常在Kruskal算法中，采用堆來存放邊的集合，因此每次選擇最小權(quán)值邊只需O(log|E|)的時(shí)間，故總的時(shí)間復(fù)雜度為O(|E|log|E|)。由于Kruskal算法的時(shí)間復(fù)雜度與圖中的邊數(shù)相關(guān)，故Kruskal算法適合于邊稀疏而頂點(diǎn)較多的圖。6.3.2最短路徑最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。其中帶權(quán)有向圖G的最短路徑問題一般可分類為兩種：一是單源最短路問題，即已知起始結(jié)點(diǎn)，求最短路徑的問題，在邊權(quán)非負(fù)時(shí)適合使用Dijkstra算法，若邊權(quán)為負(fù)時(shí)則適合使用Floyd算法；二是求每對頂點(diǎn)間的最短路徑，可通過Floyd算法來求解。1．Dijkstra算法Dijkstra（迪杰斯特拉）算法是荷蘭計(jì)算機(jī)科學(xué)家EdsgerWybeDijkstra在1956年發(fā)現(xiàn)的算法，并于3年后在期刊上發(fā)表。迪杰斯特拉算法使用類似廣度優(yōu)先搜索的方法解決賦權(quán)圖的單源最短路徑問題

下面通過實(shí)例來演示Dijkstra算法的過程，如圖和表所示。算法執(zhí)行過程的說明如下。

初始化：集合S初始為{v1}，v1可到達(dá)v2和v5，不能到達(dá)v3和v4，故dist[]數(shù)組各元素的初始值依次設(shè)置為dist[2]=10，dist[3]=∞，dist[4]=∞，dist[5]=5。

第一輪：選出dist[]中的最小值dist[5]，將頂點(diǎn)v5并入集合S，即此時(shí)已經(jīng)找到v1到v5的最短路徑。當(dāng)v5加入到集合S后，從v1到集合V-S中可達(dá)頂點(diǎn)的最短路徑長度可能會發(fā)生變化，因此需要更新dist[]數(shù)組。v5可以到達(dá)v2，由于v1→v5→v4的距離8比dist[2]=10要小，故更新dist[2]為8；v5可以到達(dá)v3，由于v1→v5→v3的距離14比dist[3]=∞要小，故更新dist[3]為14；v5可以到達(dá)v4，由于v1→v5→v4的距離7比dist[4]=∞要小，故更新dist[4]為7。

第二輪：選出最小值dist[4]，將頂點(diǎn)v4并入集合S，繼續(xù)更新dist[]數(shù)組。v4不可到達(dá)v2，則dist[2]不變；v4可到達(dá)v3，v1→v5→v4→v3的距離13比dist[3]=14要小，故更新dist[3]為13。

第三輪：選出最小值dist[2]，將頂點(diǎn)v2并入集合S，繼續(xù)更新dist[]數(shù)組。v2可到達(dá)v3，v1→v5→v2→v3的距離9比dist[3]小，故更新dist[3]為9。

第四輪：選出唯一的最小值dist[3]，將頂點(diǎn)v3并入集合S，此時(shí)全部的頂點(diǎn)都已包含在S中。

從過程說明中可以發(fā)現(xiàn)，Dijkstra算法是基于貪心策略的。在使用鄰接矩陣或鄰接表存儲方法存儲圖時(shí)，Dijkstra算法的時(shí)間復(fù)雜度都為O(|V|2)。Dijkstra算法有一個(gè)值得注意的缺點(diǎn)，當(dāng)邊上帶有負(fù)權(quán)值時(shí)該算法并不適用。若允許邊上帶有負(fù)權(quán)值，則在與S（已求得最短路徑的頂點(diǎn)集）內(nèi)某點(diǎn)（記為v1）以負(fù)邊相連的點(diǎn)（記為v2）確定其為最短路徑時(shí)，其最短路徑長度加上這條負(fù)邊的權(quán)值結(jié)果可能小于v1原先確認(rèn)的最短路徑長度，而此時(shí)v1在Dijkstra算法下是無法更新的。2．Floyd算法Floyd（弗洛伊德）算法是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)（但不可存在負(fù)權(quán)回路）的最短路徑問題。Floyd算法的原理是動態(tài)規(guī)劃。其算法步驟如下：1）設(shè)Di,j,k為從i到j(luò)的只以（1..k）集合中的結(jié)點(diǎn)為中間結(jié)點(diǎn)的最短路徑長度。2）若最短路徑經(jīng)過點(diǎn)k，則Di,j,k=Di,k,k-1+Dk,j,k-1;若最短路徑不經(jīng)過點(diǎn)k，則Di,j,k=Di,j,k-1。3）Di,j,k=min(Di,j,k-1,Di,k,k-1,Dk,j,k-1)。Floyd算法的時(shí)間復(fù)雜度為O(|V|3)。6.3.3拓?fù)渑判蛟谡麄€(gè)工程中，有些子工程(活動)必須在其它有關(guān)子工程完成之后才能開始，也就是說，一個(gè)子工程的開始是以它的所有前序子工程的結(jié)束為先決條件的，但有些子工程沒有先決條件，可以安排在任何時(shí)間開始。為了形象地反映出整個(gè)工程中各個(gè)子工程(活動)之間的先后關(guān)系，可用一個(gè)有向圖來表示，圖中的頂點(diǎn)代表活動(子工程)，圖中的有向邊代表活動的先后關(guān)系，即有向邊的起點(diǎn)的活動是終點(diǎn)活動的前序活動，只有當(dāng)起點(diǎn)活動完成之后，其終點(diǎn)活動才能進(jìn)行。通常，我們把這種頂點(diǎn)表示活動、邊表示活動間先后關(guān)系的有向圖稱作頂點(diǎn)活動網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)。一個(gè)AOV網(wǎng)應(yīng)該是一個(gè)有向無環(huán)圖，即不應(yīng)該帶有回路，因?yàn)槿魩в谢芈?，則回路上的所有活動都無法進(jìn)行。在AOV網(wǎng)中，若不存在回路，則所有活動可排列成一個(gè)線性序列，使得每個(gè)活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓?fù)湫蛄?Topologicalorder)，由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫做拓?fù)渑判?Topologicalsort)。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?，滿足上述定義的任一線性序列都稱作它的拓?fù)湫蛄小Ｓ葾OV網(wǎng)構(gòu)造出拓?fù)湫蛄械膶?shí)際意義是：如果按照拓?fù)湫蛄兄械捻旤c(diǎn)次序，在開始每一項(xiàng)活動時(shí)，能夠保證它的所有前驅(qū)活動都已完成，從而使整個(gè)工程順序進(jìn)行，不會出現(xiàn)沖突的情況。在圖論中，由一個(gè)有向無環(huán)圖的頂點(diǎn)組成的序列，當(dāng)且僅當(dāng)滿足下列條件時(shí)，才能稱為該圖的一個(gè)拓?fù)渑判颍═opologicalsorting）：

1）序列中包含每個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)只出現(xiàn)一次；2）若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。有向無環(huán)圖的拓?fù)渑判蜻^程如圖所示。每一輪選擇一個(gè)入度為0的頂點(diǎn)并輸出，然后刪除該頂點(diǎn)和所有以它為起點(diǎn)的有向邊，所以該圖最后得到的拓?fù)渑判蚪Y(jié)果為{1,3,4,5,2}。由于拓?fù)渑判蛑休敵雒總€(gè)頂點(diǎn)的同時(shí)還要刪除以它為起點(diǎn)的邊，故拓?fù)渑判虻臅r(shí)間復(fù)雜度為O(|V|+|E|)。6.3.4關(guān)鍵路徑關(guān)鍵路徑通常是決定項(xiàng)目工期的進(jìn)度活動序列。它是項(xiàng)目中最長的路徑，即使很小浮動也可能直接影響整個(gè)項(xiàng)目的最早完成時(shí)間。關(guān)鍵路徑的工期決定了整個(gè)項(xiàng)目的工期。關(guān)鍵路徑上的活動稱為關(guān)鍵活動。關(guān)鍵路徑在1950年代由杜邦的MorganR.Walker和JamesE.Kelley提出。用頂點(diǎn)表示事件，弧表示活動，弧上的權(quán)值表示活動持續(xù)時(shí)間的帶權(quán)有向圖叫AOE（ActivityOnEdgeNetwork）網(wǎng)。AOE網(wǎng)有以下特點(diǎn)：1）只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊所代表的活動才能開始。2）只有在進(jìn)入某一頂點(diǎn)的各有向邊所代表的活動都已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生。在AOE網(wǎng)中，僅有一個(gè)入度為0的頂點(diǎn)，稱為開始頂點(diǎn)（源點(diǎn)），它表示整個(gè)工程的開始；網(wǎng)中也僅存在一個(gè)出度為0的頂點(diǎn)，稱為結(jié)束頂點(diǎn)（匯點(diǎn)），它表示整個(gè)工程的結(jié)束。在AOE網(wǎng)中，有些活動是可以并行進(jìn)行的。從源點(diǎn)到匯點(diǎn)的有向路徑可能有多條，并且這些路徑長度可能不同。完成不同路徑上的活動所需的時(shí)間雖然不同，但是只有所有路徑上的活動都已經(jīng)完成，整個(gè)工程才算結(jié)束。因此從源點(diǎn)到匯點(diǎn)的所有路徑中，具有最大路徑長度的路徑稱為關(guān)鍵路徑，而把關(guān)鍵路徑上的活動稱為關(guān)鍵活動。完成整個(gè)工程的最短時(shí)間就是關(guān)鍵路徑的長度，即關(guān)鍵路徑上各活動花費(fèi)開銷的總和。這是因?yàn)殛P(guān)鍵活動影響了整個(gè)工程的時(shí)間，若關(guān)鍵活動不能按時(shí)完成，則整個(gè)工程的完成時(shí)間就會延長。所以說找到了關(guān)鍵路徑，就能得出整個(gè)工程的最短完成時(shí)間。尋找關(guān)鍵活動時(shí)會用到幾個(gè)參量的定義。1．事件vk的最早發(fā)生時(shí)間ve(k)它是指從源點(diǎn)v1到頂點(diǎn)vk的最長路徑長度。事件vk的最早發(fā)生事件決定了所有從vk開始的活動能夠開工的最早事件?？捎靡韵碌倪f推公式來計(jì)算：ve(源點(diǎn))=0ve(k)=Max{ve(j)+Weight(vj,vk)}，其中vk為vj的任意后繼，Weight(vj,vk)表示<vj,vk>上的權(quán)值。2．事件vk的最遲發(fā)生時(shí)間vl(k)它是指在不推遲整個(gè)工程完成的前提下，即保證它的后繼事件vj在其最遲發(fā)生時(shí)間vl(j)能夠發(fā)生時(shí)，該事件最遲必須發(fā)生的時(shí)間?？捎靡韵碌倪f推公式來計(jì)算：vl(匯點(diǎn))=ve(匯點(diǎn))vl(k)=Min(vl(j)–Weight(vk,vj))，其中vk為vj的任意前驅(qū)。

3．活動ai的最早開始時(shí)間e(i)它是指該活動弧的起點(diǎn)所表示的事件的最早發(fā)生時(shí)間。若邊<vk,vj>表示活動ai，則有e(i)=ve(k)。

4．活動ai的最遲開始時(shí)間l(i)它是指該活動弧的終點(diǎn)所表示事件的最遲發(fā)生時(shí)間與該活動所需時(shí)間之差。若邊<vk,vj>表示活動ai，則有l(wèi)(i)=vl(i)–Weight(vk,vj)。5．一個(gè)活動ai的最遲開始時(shí)間l(i)和其最早開始時(shí)間e(i)的差額d(i)=l(i)–e(i)它是指該活動完成的時(shí)間余量，即在不增加完成整個(gè)工程所需總時(shí)間的情況下，活動ai可以拖延的時(shí)間。若一個(gè)活動的時(shí)間余量為0，則說明該活動必須要如期完成，否則就會拖延整