數(shù)據(jù)結(jié)構(gòu)與算法 課件 第六章圖結(jié)構(gòu)

全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第六章圖結(jié)構(gòu)學(xué)習(xí)目標(biāo)理解圖的定義和相關(guān)的基本概念掌握?qǐng)D的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)掌握?qǐng)D基本操作的實(shí)現(xiàn)掌握并實(shí)現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先搜索算法，理解圖的連通性及連通分量概念理解圖的生成樹(shù)概念，掌握求圖最小代價(jià)生成樹(shù)的兩個(gè)算法理解有向無(wú)環(huán)圖的概念，掌握?qǐng)D的拓?fù)渑判蛩惴?，掌握關(guān)鍵路徑算法理解最短路徑概念，掌握迪杰斯特拉算法和弗洛伊德算法的求解過(guò)程了解各算法的時(shí)間復(fù)雜度本章主要內(nèi)容圖的基本概念12圖基本操作的實(shí)現(xiàn)3圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷4圖的生成樹(shù)56最短路徑7DAG圖及其應(yīng)用第一節(jié)圖的基本概念圖（graph）由頂點(diǎn)和邊組成一般地，用G=(V,E)來(lái)表示，其中V表示頂點(diǎn)（vertex）集，是一個(gè)有窮非空集合；E表示邊（edge）集，E中的每條邊都是V中某一對(duì)頂點(diǎn)的連接當(dāng)頂點(diǎn)分別是u和v時(shí)，連接這兩個(gè)頂點(diǎn)的邊可以表示為一個(gè)二元組(u,v)，有時(shí)也將邊稱為頂點(diǎn)的偶對(duì)圖中任意兩個(gè)不同頂點(diǎn)之間允許有邊，但不能超過(guò)一條基本概念圖G=(V,E)中，頂點(diǎn)總數(shù)記為|V|，邊的總數(shù)記為|E|如果圖中邊的數(shù)目較少（相對(duì)于頂點(diǎn)數(shù)來(lái)說(shuō)），則圖稱為稀疏圖邊數(shù)較多的圖稱為密集圖或是稠密圖至于邊數(shù)多到多少是密集圖或少到多少是稀疏圖，并沒(méi)有嚴(yán)格的界定當(dāng)圖中邊數(shù)的數(shù)量級(jí)不高于頂點(diǎn)數(shù)的數(shù)量級(jí)時(shí)，就可以認(rèn)為圖是稀疏圖基本概念當(dāng)圖中的邊限定為從一個(gè)頂點(diǎn)指向另一個(gè)頂點(diǎn)時(shí)，稱為有向邊，或稱為弧（arc）不限定方向的邊稱為無(wú)向邊一條無(wú)向邊可以看成是兩條方向相反的有向邊組成有向邊的偶對(duì)看作是有序的組成無(wú)向邊的偶對(duì)是無(wú)序的基本概念有向邊(u,v)表示從頂點(diǎn)u指向頂點(diǎn)v的邊，弧的方向是從u指向v，u稱為弧尾（tail），v稱為弧頭（head）對(duì)于有向邊，(u,v)與(v,u)不同無(wú)向邊(u,v)既可以表示從頂點(diǎn)u指向頂點(diǎn)v，也可以表示從頂點(diǎn)v指向頂點(diǎn)u對(duì)于無(wú)向邊，(u,v)與(v,u)是等價(jià)的基本概念含有向邊的圖稱為有向圖（directedgraph或簡(jiǎn)寫(xiě)為digraph）如果圖中的邊都是無(wú)向邊，則圖稱為無(wú)向圖（undirectedgraph或簡(jiǎn)寫(xiě)為undigraph）如果一個(gè)圖中既含有有向邊，又含有無(wú)向邊，則可以將其中所有的無(wú)向邊表示為一對(duì)方向相反的有向邊提到有向圖時(shí)，表明其中所含的邊全部都是有向邊基本概念若無(wú)向圖G中含有邊(u,v)，則u和v互為鄰接點(diǎn)（adjacent）邊(u,v)稱為與頂點(diǎn)u和v相關(guān)聯(lián)（incident），也可以說(shuō)邊(u,v)依附于頂點(diǎn)u和v對(duì)于有向圖中的有向邊(u,v)，稱頂點(diǎn)v是頂點(diǎn)u的鄰接點(diǎn)頂點(diǎn)u鄰接到頂點(diǎn)v，或頂點(diǎn)v鄰接自頂點(diǎn)u可以給邊賦予一個(gè)非負(fù)的數(shù)值，這個(gè)非負(fù)數(shù)值稱為邊的權(quán)（weight），相應(yīng)的圖稱為帶權(quán)圖（weightedgraph）或是加權(quán)圖可以讓各頂點(diǎn)帶有標(biāo)號(hào)，這樣的圖稱為標(biāo)號(hào)圖（labedledgraph）本章討論的圖大多是標(biāo)號(hào)圖，標(biāo)號(hào)可以作為頂點(diǎn)的名稱示例圖中兩個(gè)頂點(diǎn)之間的邊不能有重復(fù)無(wú)向圖中兩個(gè)頂點(diǎn)之間最多只能有一條邊有向圖中兩個(gè)頂點(diǎn)之間最多有兩條方向相反的弧圖中不包含(i,i)形式的邊，即沒(méi)有頂點(diǎn)自身到自身的邊在無(wú)向圖中，與頂點(diǎn)v相關(guān)聯(lián)的邊的數(shù)目稱為頂點(diǎn)的度（degree）在有向圖中，頂點(diǎn)的度分為出度和入度以某頂點(diǎn)為弧頭的弧稱為該頂點(diǎn)的入邊，入邊的數(shù)目稱為該頂點(diǎn)的入度以某頂點(diǎn)為弧尾的弧稱為該頂點(diǎn)的出邊，出邊的數(shù)目稱為該頂點(diǎn)的出度一個(gè)頂點(diǎn)的出度和入度之和稱為該頂點(diǎn)的度有n個(gè)頂點(diǎn)的無(wú)向圖中，其邊數(shù)最多可達(dá)n(n-1)/2有向圖中由于邊具有方向性，所以可能的最大邊數(shù)比無(wú)向圖多了一倍，含n個(gè)頂點(diǎn)的有向圖中最大邊數(shù)為n(n-1)

包含了所有可能邊的圖稱為完全圖（completegraph）

若兩個(gè)圖G=(V,E)和G'=(V',E')，滿足條件：V’V，E’E且E'中邊依附的頂點(diǎn)均屬于V'，則稱G'為G的子圖（subgraph）一個(gè)圖G的子圖是指由圖G中選出其頂點(diǎn)集的一個(gè)子集Vs以及僅與Vs中頂點(diǎn)相關(guān)聯(lián)的一些邊所構(gòu)成的圖例6-3對(duì)于圖G，圖G1、G2、G3和G4都是它的子圖；特別地，圖G1與圖G完全一樣，它也是圖G的子圖，即圖本身也是它自身的子圖；同時(shí)，圖G2也是圖G4的子圖。而圖G5不是圖G的子圖在圖G=(V,E)中，如果(vi0,vi1),(vi1,vi2),…,(vim-2,vim-1)都是E中的邊，則頂點(diǎn)序列(vi0,vi1,…,vim-1)稱為從頂點(diǎn)vi0到頂點(diǎn)vim-1的路徑（path）若圖G是有向圖，則路徑也要求是有向的，且有向邊必須是方向一致的，即有向路徑(vi0,vi1,…,vim-1)是由E中的弧(vi0,vi1),(vi1,vi2),…,(vim-2,vim-1)組成的路徑(vi0,vi1,…,vim-1)中包含的邊或弧的數(shù)目m稱為路徑長(zhǎng)度如果路徑上各頂點(diǎn)均不同，則稱此路徑為簡(jiǎn)單路徑（simplepath）第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路（cycle），也稱為環(huán)如果一個(gè)回路中除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)均不相同，則稱為簡(jiǎn)單回路（simplecycle）或簡(jiǎn)單環(huán)不帶回路的圖稱為無(wú)環(huán)圖。不帶回路的有向圖稱為有向無(wú)環(huán)圖從頂點(diǎn)0到頂點(diǎn)3到頂點(diǎn)4再到頂點(diǎn)1構(gòu)成一條有向簡(jiǎn)單路徑(0,3,4,1)，路徑長(zhǎng)度為3從頂點(diǎn)2到頂點(diǎn)3到頂點(diǎn)4再回到頂點(diǎn)2構(gòu)成一個(gè)簡(jiǎn)單有向回路(2,3,4,2)從頂點(diǎn)2到頂點(diǎn)0再到頂點(diǎn)3，雖然其中均有邊相連，但由于邊的方向不一致，所以不能構(gòu)成有向路徑對(duì)于無(wú)向圖G，如果頂點(diǎn)u和頂點(diǎn)v之間有路徑，則稱這兩個(gè)頂點(diǎn)是連通的如果無(wú)向圖G中任意一個(gè)頂點(diǎn)到其他任意頂點(diǎn)都至少存在一條路徑，也就是說(shuō)，圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱圖G為連通圖（connectedgraph）無(wú)向圖中的極大連通子圖稱為連通分量（connectedcomponent）有向圖G中，如果每對(duì)頂點(diǎn)u與v之間均有從u到v的有向路徑，則稱G為強(qiáng)連通圖（stronglyconnectedgraph）有向圖的最大強(qiáng)連通子圖稱為強(qiáng)連通分量如果對(duì)于每對(duì)頂點(diǎn)u和v，存在頂點(diǎn)序列vi0,vi1,…,vim-1，這里u=vi0，v=vim-1，并且(vij,vij+1)∈E或(vij+1,vij)∈E(0≤j≤m-2)，則稱圖G為弱連通圖（weaklyconnectedgraph）示例例6-5設(shè)無(wú)向圖G含有10個(gè)頂點(diǎn)和6條邊，則G中連通分量的個(gè)數(shù)最多可能是多少？最少可能是多少？要讓G中連通分量最多，可以讓某些頂點(diǎn)與盡可能多的邊相關(guān)聯(lián)，且這些頂點(diǎn)組成盡可能少的連通分量。6條邊可以讓4個(gè)頂點(diǎn)組成完全圖，其余的6個(gè)頂點(diǎn)均為孤立頂點(diǎn)，則G含有7個(gè)連通分量圖的基本操作VType表示頂點(diǎn)類型MEdge表示邊的類型圖的基本操作定義頂點(diǎn)使用單字符表示，保存在頂點(diǎn)表verticesList[MaxVtxNum]中，使用兩個(gè)輔助方法，在頂點(diǎn)字符與頂點(diǎn)表下標(biāo)之間進(jìn)行轉(zhuǎn)換intVerToNum(MGraphg,VTypeu) //返回頂點(diǎn)u在頂點(diǎn)表verticesList中的下標(biāo)值VTypeNumToVer(MGraphg,inti) //返回頂點(diǎn)表verticesList中下標(biāo)i對(duì)應(yīng)的頂點(diǎn)第二節(jié)圖的存儲(chǔ)結(jié)構(gòu)圖也有兩類基本的存儲(chǔ)方式，即順序存儲(chǔ)結(jié)構(gòu)及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)以鄰接矩陣為代表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以鄰接表為代表鄰接矩陣設(shè)圖G=(V,E)，|V|=n，圖的鄰接矩陣是一個(gè)n

n矩陣，矩陣元素表示圖中各頂點(diǎn)之間的鄰接關(guān)系，鄰接矩陣也稱為相鄰矩陣設(shè)各頂點(diǎn)為v0,v1,…,vn-1，如果從vi到vj存在一條邊，則鄰接矩陣中位于i行j列的元素值為1，否則值為0這樣的一個(gè)矩陣可以表示圖中所有頂點(diǎn)之間的鄰接關(guān)系鄰接矩陣的存儲(chǔ)空間與頂點(diǎn)個(gè)數(shù)有關(guān)，為O(|V|2)鄰接矩陣是一個(gè)二維數(shù)組對(duì)于帶權(quán)圖鄰接矩陣是對(duì)稱矩陣有向圖的鄰接矩陣不能保證對(duì)稱性例6-7若無(wú)向圖G中含有n個(gè)頂點(diǎn)和e條邊，則它的鄰接矩陣中0的個(gè)數(shù)是多少？根據(jù)圖鄰接矩陣的定義，因?yàn)閳DG中含有n個(gè)頂點(diǎn)，所以鄰接矩陣中元素個(gè)數(shù)為n2。無(wú)向圖的鄰接矩陣是對(duì)稱矩陣，對(duì)G中的任一條邊(vi,vj)，在鄰接矩陣中都會(huì)對(duì)應(yīng)兩個(gè)1，即A[i][j]和A[j][i]均為1。所以圖G的鄰接矩陣中有2e個(gè)1，0的個(gè)數(shù)為n2-2e用鄰接矩陣表示圖時(shí)，可以很容易地判定圖中任意兩頂點(diǎn)之間是否存在邊（或弧）若矩陣元素A[i][j]為1或wij，就表示從vi到vj有一條邊（或?。?，否則從vi到vj沒(méi)有邊（或?。┐嬖诮柚卩徑泳仃?，很容易得到圖中各頂點(diǎn)的度對(duì)于無(wú)向圖G，鄰接矩陣i行或i列中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的度對(duì)于有向圖G，鄰接矩陣i行中非零（也不等于∞）元素的個(gè)數(shù)為頂點(diǎn)vi的出度而i列中非零（也不等于∞）元素的個(gè)數(shù)為頂點(diǎn)vi的入度i行非零（也不等于∞）元素的個(gè)數(shù)加上i列非零（也不等于∞）元素的個(gè)數(shù)為頂點(diǎn)vi的度設(shè)用鄰接矩陣表示有n個(gè)頂點(diǎn)的圖G，計(jì)算G中有多少條邊時(shí)，需要檢查矩陣中的所有元素，因此時(shí)間復(fù)雜度為O(n2)存儲(chǔ)空間僅與圖G中的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)，即為O(n2)設(shè)圖G=(V,E)，則G的鄰接表由一個(gè)一維數(shù)組和n=|V|個(gè)鏈表組成一維數(shù)組包含n個(gè)元素，每個(gè)元素包含表示頂點(diǎn)信息的域和一個(gè)指針域與頂點(diǎn)vi(0≤i≤n-1)相鄰接的所有頂點(diǎn)組成一個(gè)單鏈表，其表頭指針保存在一維數(shù)組下標(biāo)為i的元素的指針域中鄰接表鄰接表表結(jié)點(diǎn)的結(jié)構(gòu)對(duì)于帶權(quán)圖，可以擴(kuò)展鄰接表的結(jié)構(gòu)，在單鏈表的每個(gè)表結(jié)點(diǎn)中增加一個(gè)域，用來(lái)存儲(chǔ)兩個(gè)頂點(diǎn)間這條邊的權(quán)表結(jié)點(diǎn)結(jié)構(gòu)對(duì)于有向圖，如果將所有有向弧的方向轉(zhuǎn)向，則得到的新圖的鄰接表稱為原圖的逆鄰接表例6-8無(wú)向圖的鄰接表有向圖的鄰接表和逆鄰接表用鄰接表表示有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖時(shí)，需要一個(gè)由n個(gè)元素組成的順序表（表頭結(jié)點(diǎn)表）和由總共2e個(gè)結(jié)點(diǎn)組成的n個(gè)單鏈表表示有n個(gè)頂點(diǎn)e條弧的有向圖時(shí)，需要一個(gè)由n個(gè)元素組成的順序表和由總共e個(gè)結(jié)點(diǎn)組成的n個(gè)單鏈表鄰接表的空間復(fù)雜度為O(n+e)當(dāng)圖中頂點(diǎn)個(gè)數(shù)經(jīng)常變化時(shí)，為便于頂點(diǎn)的插入和刪除，也可以將圖的全部頂點(diǎn)保存在一個(gè)單鏈表中，而不是一維數(shù)組中。單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)如下所示指向下一頂點(diǎn)的指針指向鄰接點(diǎn)表的指針頂點(diǎn)信息第三節(jié)圖基本操作的實(shí)現(xiàn)采用鄰接矩陣存儲(chǔ)的圖的定義頂點(diǎn)表的相應(yīng)查詢查詢邊的權(quán)值創(chuàng)建圖創(chuàng)建無(wú)向圖創(chuàng)建有向帶權(quán)圖驗(yàn)證圖構(gòu)建函數(shù)的正確性找到某頂點(diǎn)的第一個(gè)鄰接點(diǎn)查找下一個(gè)鄰接點(diǎn)獲取頂點(diǎn)個(gè)數(shù)及邊數(shù)intgetNumVertices(MGraphg){ returng.numVertices;}intgetNumEdges(MGraphg){ returng.numEdges;}第四節(jié)圖的遍歷定義6-1給定一個(gè)連通圖G=(V,E)，從圖中的某個(gè)頂點(diǎn)出發(fā)，經(jīng)過(guò)一定的路線訪問(wèn)圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)被訪問(wèn)且只訪問(wèn)一次，這一過(guò)程稱為圖的遍歷深度優(yōu)先搜索（depthfirstsearch,DFS）遍歷廣度優(yōu)先搜索（breadthfirstsearch,BFS）遍歷深度優(yōu)先搜索選擇圖中任意指定頂點(diǎn)為起始頂點(diǎn)，將其設(shè)為當(dāng)前頂；訪問(wèn)當(dāng)前頂點(diǎn)v，輸出關(guān)于v的相關(guān)信息將v的訪問(wèn)標(biāo)志置為VISITED如果v的鄰接點(diǎn)中存在未被訪問(wèn)的頂點(diǎn)w，則將w設(shè)為當(dāng)前頂點(diǎn)，轉(zhuǎn)②繼續(xù)；否則轉(zhuǎn)⑤回退到最近被訪問(wèn)過(guò)的且仍有未被訪問(wèn)鄰接點(diǎn)的頂點(diǎn)u，轉(zhuǎn)④繼續(xù)；不能回退時(shí)，轉(zhuǎn)⑥如果所有頂點(diǎn)均已訪問(wèn)，則遍歷結(jié)束，否則，選擇未被訪問(wèn)的另一個(gè)頂點(diǎn)作為起始頂點(diǎn)，繼續(xù)上述過(guò)程v0,v1,v3,v7,v4,v5,v2,v6DFS算法當(dāng)圖是連通圖時(shí)，使用DFS算法從某個(gè)頂點(diǎn)出發(fā)，可以訪問(wèn)到圖中的所有頂點(diǎn)。如果圖不連通，則一次調(diào)用DFS不能訪問(wèn)圖中的全部頂點(diǎn)，只能訪問(wèn)初始頂點(diǎn)所在的連通分量中的所有頂點(diǎn)廣度優(yōu)先搜索選擇圖中指定的頂點(diǎn)v為起始頂點(diǎn)，將其入隊(duì)列，且其訪問(wèn)標(biāo)志置為VISITED隊(duì)列為空時(shí)，轉(zhuǎn)⑤；隊(duì)列不為空時(shí)，出隊(duì)列，設(shè)出隊(duì)列的頂點(diǎn)為w輸出關(guān)于w的相關(guān)信息找到與頂點(diǎn)w相鄰接的且訪問(wèn)標(biāo)志不是VISITED的頂點(diǎn)序列w1,w2,…,wk，依次入隊(duì)列，轉(zhuǎn)②如果所有頂點(diǎn)均已訪問(wèn)，則遍歷結(jié)束，否則，選擇未被訪問(wèn)的一個(gè)頂點(diǎn)作為起始頂點(diǎn)，繼續(xù)上述過(guò)程廣度優(yōu)先搜索過(guò)程中，使用了一個(gè)隊(duì)列作為輔助存儲(chǔ)結(jié)構(gòu)，頂點(diǎn)是一批批加入隊(duì)列的如果圖是不連通的，則這個(gè)過(guò)程也不能訪問(wèn)圖中的全部頂點(diǎn)，而只能遍歷圖中某個(gè)連通分量中的所有頂點(diǎn)BFS算法第五節(jié)圖的生成樹(shù)設(shè)G=(V,E)是一個(gè)連通的無(wú)向圖，包含圖中全部頂點(diǎn)的極小連通子圖稱為圖的生成樹(shù)極小連通子圖是指含有圖中所有頂點(diǎn)并使圖仍保持連通性的最小子圖從圖中任一頂點(diǎn)出發(fā)，按照深度優(yōu)先搜索策略或是廣度優(yōu)先搜索策略，可以訪問(wèn)到圖中的全部頂點(diǎn)。在遍歷的過(guò)程中，所經(jīng)過(guò)的邊集設(shè)為T(mén)(G)，沒(méi)有經(jīng)過(guò)的邊集設(shè)為B(G)。T(G)即構(gòu)成G的一棵生成樹(shù)生成樹(shù)中所含的邊數(shù)必定是n-1進(jìn)行深度優(yōu)先搜索時(shí)得到的生成樹(shù)稱為深度優(yōu)先生成樹(shù)進(jìn)行廣度優(yōu)先搜索時(shí)得到的生成樹(shù)稱為廣度優(yōu)先生成樹(shù)進(jìn)行遍歷時(shí)可能會(huì)得到不同的頂點(diǎn)序列，實(shí)際上，圖的生成樹(shù)也可能是不唯一的同一個(gè)圖的深度優(yōu)先生成樹(shù)，也可能不是唯一的廣度優(yōu)先生成樹(shù)，也可能不是唯一的示例兩棵深度優(yōu)先生成樹(shù)圖的最小代價(jià)生成樹(shù)帶權(quán)圖的每條邊上都有一個(gè)非負(fù)的權(quán)值，稱邊權(quán)值之和最小的生成樹(shù)為最小代價(jià)生成樹(shù)（minimum_costspanningtree，MST）。簡(jiǎn)稱為最小生成樹(shù)給定一個(gè)無(wú)向連通圖G，則MST是一個(gè)包括G的所有頂點(diǎn)及其邊子集的圖，邊的子集滿足下列條件這個(gè)子集中所有邊的權(quán)之和為所有滿足條件的子集中最小的子集中的邊能夠保證圖是連通的最小生成樹(shù)性質(zhì)它含有圖G中的所有n個(gè)頂點(diǎn)它沒(méi)有回路。因?yàn)閺臉?gòu)成回路的各邊中去掉一條邊，仍能保證其連通性，而所得的權(quán)值總和可以進(jìn)一步地減少它含有的邊數(shù)為n-1去掉最小生成樹(shù)中的一條邊，換上不在最小生成樹(shù)中的另外一條邊，在仍要求連通的前提下，所得的權(quán)值總和都不會(huì)小于原最小生成樹(shù)的權(quán)值總和普里姆算法設(shè)連通的帶權(quán)圖G=(V,E)，V是頂點(diǎn)集合，E是邊的集合設(shè)T是圖G的最小生成樹(shù)的邊集合，U是最小生成樹(shù)的頂點(diǎn)集合，設(shè)由頂點(diǎn)v1開(kāi)始，初始時(shí)T=Ф，U={v1}在所有u∈U，v∈V-U的邊(u,v)∈E中選擇一條權(quán)最小的邊(ui,vj)，將vj并入U(xiǎn)中，將邊(ui,vj)并入T中重復(fù)②，直到U=V時(shí)結(jié)束示例程序普里姆算法是貪心算法的一個(gè)實(shí)例，每次選出一條連接U中頂點(diǎn)及V-U中頂點(diǎn)的具有最小權(quán)值的邊，逐步生成最小生成樹(shù)普里姆算法共進(jìn)行n-1輪的選邊操作，每輪選邊時(shí)，最多從n-1條邊中選中權(quán)最小的邊。故對(duì)于含|V|個(gè)頂點(diǎn)的圖，算法的時(shí)間復(fù)雜度為O(|V|2)當(dāng)圖是一個(gè)邊稠密的圖時(shí)，適合使用普里姆算法求圖的最小生成樹(shù)克魯斯卡爾算法設(shè)E1的初值：E1=Φ，T中只含有圖中的所有頂點(diǎn)，頂點(diǎn)個(gè)數(shù)為n=|V|當(dāng)E1中邊數(shù)小于n-1時(shí)，重復(fù)執(zhí)行下面的步驟在圖G的邊集E中選擇權(quán)值最小的邊(u,v)，并從E中刪除它如果u和v分別屬于T中不同的連通分量，則將邊(u,v)加入到E1中去，否則丟掉該邊，選擇E中的下一條權(quán)值最小的邊邊權(quán)值(6,8)2(7,8)2(5,8)3(1,3)4(3,4)5(4,7)5(1,4)6(1,2)6(3,7)6(2,5)7(2,6)7(5,6)10(4,5)14程序克魯斯卡爾算法中，從|E|條邊中選出權(quán)值最小的邊(u,v)，并檢測(cè)u和v是不是在同一連通分量上，時(shí)間花費(fèi)為O(|E|log|E|)。所以，克魯斯卡爾算法適宜求稀疏圖的最小生成樹(shù)第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用圖中不存在回路的有向圖稱為有向無(wú)環(huán)圖（directedacyclinegraph），簡(jiǎn)稱為DAG圖比如，表達(dá)式樹(shù)可表示為DAG圖拓?fù)渑判蛴邢驘o(wú)環(huán)圖G=(V,E)的拓?fù)湫蛄惺荊中頂點(diǎn)的一個(gè)線性序列，并且滿足以下關(guān)系：對(duì)于圖G中的所有頂點(diǎn)v和w，如果(v,w)∈E，則在線性序列中v排在w之前求有向無(wú)環(huán)圖拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判蛟谟邢驁D中，以頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（activityonvertexnetwork），簡(jiǎn)稱為AOV網(wǎng)在AOV網(wǎng)中，若從頂點(diǎn)vi到vj有一條有向路徑，則稱vi是vj的前驅(qū)，vj是vi的后繼若(vi,vj)是AOV網(wǎng)中的一條弧，則稱vi是vj的直接前驅(qū)，vj是vi的直接后繼如果vi是vj的前驅(qū)或直接前驅(qū)，則vi活動(dòng)必須在vj活動(dòng)開(kāi)始之前結(jié)束，即vj活動(dòng)必須在vi活動(dòng)結(jié)束之后才能開(kāi)始在AOV網(wǎng)中不允許出現(xiàn)回路，因此AOV網(wǎng)必是有向無(wú)環(huán)圖拓?fù)渑判蚩梢詫OV網(wǎng)中的各個(gè)活動(dòng)排序，它把AOV網(wǎng)中各頂點(diǎn)按照它們之間的先后關(guān)系排成一個(gè)線性序列在AOV網(wǎng)中，如果從頂點(diǎn)vi到頂點(diǎn)vj存在有向路徑，則在拓?fù)湫蛄兄?，vi必定排在vj的前面；如果從頂點(diǎn)vi到頂點(diǎn)vj沒(méi)有有向路徑，則在拓?fù)湫蛄兄?，vi與vj的先后次序可以任意五門(mén)課程排成的拓?fù)湫蛄袨?C1,C2,C3,C4,C5還可以排列成 C1,C2,C5,C3,C4課程代號(hào)課程名稱先導(dǎo)課C1高等數(shù)學(xué)無(wú)C2程序設(shè)計(jì)基礎(chǔ)無(wú)C3數(shù)據(jù)結(jié)構(gòu)C2C4編譯原理C3C5算法分析C1,C2遵循的原則在拓?fù)湫蛄兄?，每個(gè)頂點(diǎn)都必須排在它的后繼頂點(diǎn)之前。那么排在最前面的頂點(diǎn)一定不能是其他任何頂點(diǎn)的后繼有向圖中一個(gè)頂點(diǎn)的直接前驅(qū)數(shù)即是頂點(diǎn)的入度值，可以使用一個(gè)一維數(shù)組來(lái)記錄各個(gè)頂點(diǎn)的入度值如果一個(gè)頂點(diǎn)不是其他任何頂點(diǎn)的后繼，就意味著該頂點(diǎn)的入度值為0初始化時(shí)，數(shù)組中填入各頂點(diǎn)的入度值，可以將入度值看作是一個(gè)頂點(diǎn)的約束條件個(gè)數(shù)基于廣度優(yōu)先搜索策略實(shí)現(xiàn)拓?fù)渑判蛲負(fù)渑判蜃裱脑瓌t是，在拓?fù)湫蛄兄校總€(gè)頂點(diǎn)都必須排在它的后繼頂點(diǎn)之前有向圖中一個(gè)頂點(diǎn)的直接前驅(qū)數(shù)即是頂點(diǎn)的入度值，可以使用一個(gè)一維數(shù)組來(lái)記錄各個(gè)頂點(diǎn)的入度值如果一個(gè)頂點(diǎn)不是其他任何頂點(diǎn)的后繼，就意味著該頂點(diǎn)的入度值為0初始化時(shí)，數(shù)組中填入各頂點(diǎn)的入度值，可以將入度值看作是一個(gè)頂點(diǎn)的約束條件個(gè)數(shù)求AOV網(wǎng)的拓?fù)湫蛄械牟襟E初始化：記錄AOV網(wǎng)中所有頂點(diǎn)的入度值選一個(gè)沒(méi)有前驅(qū)（入度為0）的頂點(diǎn)，輸出之從圖中刪除該頂點(diǎn)和以它為尾的所有的弧，即將輸出頂點(diǎn)的所有后繼頂點(diǎn)的入度值減1。轉(zhuǎn)②步驟②、③重復(fù)執(zhí)行，每輸出一個(gè)頂點(diǎn)，就修改入度值數(shù)組，然后再選擇滿足條件的頂點(diǎn)輸出，再修改數(shù)組直至輸出全部頂點(diǎn)或者還沒(méi)有輸出全部頂點(diǎn)，但已找不到?jīng)]有前驅(qū)的頂點(diǎn)（即入度值為0的頂點(diǎn)）為止第一種情況表示拓?fù)渑判蛞呀?jīng)完成第二種情況表明原有向圖中含有回路建立入度值表靜態(tài)鏈表在入度值表中，那些入度值為0的頂點(diǎn)的“入度值”域的值都是0，所以可以用這個(gè)域在入度值表中建立一個(gè)靜態(tài)鏈表，專門(mén)將入度值為0的頂點(diǎn)鏈接起來(lái)來(lái)，方便后面的選擇初始建立入度值表時(shí)，將入度值為0的頂點(diǎn)逐一插入到這個(gè)靜態(tài)鏈表中入度值表建立完成時(shí)，靜態(tài)鏈表的初始化也即完成當(dāng)同時(shí)有多個(gè)入度值為0的頂點(diǎn)時(shí)，拓?fù)渑判虿⒉粡?qiáng)制輸出其中的哪一個(gè)，所以將滿足要求的頂點(diǎn)插入靜態(tài)鏈表時(shí)，可以插入在表頭位置，這樣的插入效率最高輸出入度值為0的頂點(diǎn)時(shí)，即是從靜態(tài)鏈表的表頭位置刪除一個(gè)結(jié)點(diǎn)，輸出其中保存的頂點(diǎn)根據(jù)存儲(chǔ)結(jié)構(gòu)尋找輸出頂點(diǎn)的鄰接點(diǎn)并修正入度值表時(shí)，遇到修正后值為0的頂點(diǎn)，將其插入到靜態(tài)鏈表的表頭入度值表的結(jié)構(gòu)typedefstruct{ VTypever; intindeg;}IndegreeV;IndegreeVindegreeTable[MaxVtxNum];建立入度值表的實(shí)現(xiàn)first是入度為0的靜態(tài)鏈表的表頭指針程序基于入度值表的拓?fù)渑判蛩惴ǔ绦蚧谏疃葍?yōu)先搜索策略實(shí)現(xiàn)拓?fù)渑判驅(qū)D進(jìn)行深度優(yōu)先搜索時(shí)，改變頂點(diǎn)輸出的條件。不是在遇到一個(gè)頂點(diǎn)時(shí)即刻輸出頂點(diǎn)，而是等到該頂點(diǎn)的所有鄰接點(diǎn)都輸出了才輸出該頂點(diǎn)，將得到的頂點(diǎn)序列逆序，即可得到圖的拓?fù)渑判虺绦蜿P(guān)鍵路徑可以使用帶權(quán)有向圖表示一個(gè)含多個(gè)活動(dòng)的工程。在這樣的圖中，用頂點(diǎn)表示事件，用弧表示活動(dòng)，邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間，這樣組成的網(wǎng)稱為以邊表示活動(dòng)的網(wǎng)，簡(jiǎn)稱為AOE網(wǎng)在AOE網(wǎng)中，通常只有一個(gè)入度為0的點(diǎn)和一個(gè)出度為0的點(diǎn)。入度為0的點(diǎn)稱為起始點(diǎn)或源點(diǎn)，出度為0的點(diǎn)稱為結(jié)束點(diǎn)或匯點(diǎn)一個(gè)工程中的某些子活動(dòng)是可以并行進(jìn)行的；從源點(diǎn)到匯點(diǎn)最長(zhǎng)路徑的長(zhǎng)度，即該路徑上所有活動(dòng)持續(xù)時(shí)間之和，就是完成整個(gè)工程所需的最少時(shí)間將從源點(diǎn)到匯點(diǎn)具有最大長(zhǎng)度的路徑稱為關(guān)鍵路徑關(guān)鍵路徑上的所有活動(dòng)稱為關(guān)鍵活動(dòng)求關(guān)鍵路徑是帶權(quán)有向無(wú)環(huán)圖的一個(gè)重要應(yīng)用一個(gè)含有8個(gè)活動(dòng)的工程，其中頂點(diǎn)1是源點(diǎn)，頂點(diǎn)6是匯點(diǎn)從頂點(diǎn)1到頂點(diǎn)6的所有路徑中，路徑長(zhǎng)度最大為8，表明這項(xiàng)工程至少需要8天才能完成在AOE網(wǎng)中，從源點(diǎn)v1到任意頂點(diǎn)vi的最長(zhǎng)路徑長(zhǎng)度叫做事件vi的最早開(kāi)始時(shí)間。這個(gè)時(shí)間決定了所有以vi為尾的弧所表示的活動(dòng)的最早開(kāi)始時(shí)間另外，在不推遲整個(gè)工程完成的前提下，活動(dòng)ai最遲必須開(kāi)始進(jìn)行的時(shí)間稱作活動(dòng)ai的最遲開(kāi)始時(shí)間用e(i)表示活動(dòng)ai的最早開(kāi)始時(shí)間，l(i)表示其最遲開(kāi)始時(shí)間。兩者之差l(i)-e(i)意味著完成活動(dòng)ai的時(shí)間余量ai的實(shí)際開(kāi)始時(shí)間可以在e(i)到l(i)之間任意調(diào)整，而絲毫不會(huì)影響整個(gè)工程的完成時(shí)間把l(i)=e(i)的活動(dòng)稱作關(guān)鍵活動(dòng)，即關(guān)鍵活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間相等，它們沒(méi)有時(shí)間余量顯然，關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)，關(guān)鍵活動(dòng)的推延將直接導(dǎo)致整個(gè)工程的推延，而提前完成非關(guān)鍵活動(dòng)并不能加快整個(gè)工程的進(jìn)度設(shè)活動(dòng)ai由弧(j,k)表示，其持續(xù)時(shí)間記為dut(j,k)，事件的最早開(kāi)始時(shí)間為ve(j)，最遲開(kāi)始時(shí)間為vl(j)，則有如下關(guān)系：e(i)=ve(j)l(i)=vl(k)-dut(j,k)求ve(j)和vl(j)將采用遞推的方法，分兩步進(jìn)行：①?gòu)膙e(1)=0開(kāi)始向前遞推 ve(j)=max{ve(i)+dut(i,j)}(i,j)∈T，2≤j≤n其中T是所有以頂點(diǎn)j為頭的弧的集合。②從vl(n)=ve(n)起向后遞推 vl(i)=min{vl(j)–dut(i,j)}(i,j)∈S，1≤i≤n-1其中S是所有以頂點(diǎn)i為尾的弧的集合計(jì)算ve時(shí)，從事件1開(kāi)始向前遞推計(jì)算vl時(shí)，從最后一個(gè)事件開(kāi)始，向后遞推求關(guān)鍵路徑的算法①輸入e條弧(j,k)，建立AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)②從源點(diǎn)v1出發(fā)，令ve[1]=0，按拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間ve[i](2≤i≤n)。如果得到的拓?fù)湫蛄兄许旤c(diǎn)個(gè)數(shù)小于AOE網(wǎng)中頂點(diǎn)數(shù)n，則說(shuō)明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟③③從匯點(diǎn)vn出發(fā)，令vl[n]=ve[n]，按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vl[i](n-1≥i≥1)④根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開(kāi)始時(shí)間e(s)和最遲開(kāi)始時(shí)間l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動(dòng)例6-17求下圖所示工程的關(guān)鍵路徑，列出關(guān)鍵活動(dòng)事件vevl100234322466567688活動(dòng)ell-ea1011a2000a3341a4341a5220a6253a7660a8671時(shí)間余量為0的活動(dòng)即是關(guān)鍵活動(dòng)，這些活動(dòng)是a2、a5和a7關(guān)鍵路徑是1、3、4、6，路徑長(zhǎng)度是8第七節(jié)最短路徑對(duì)于帶權(quán)圖，修改路徑長(zhǎng)度概念兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度定義為兩頂點(diǎn)間路徑上各邊的權(quán)值之和路徑的開(kāi)始頂點(diǎn)稱為源點(diǎn)，目的頂點(diǎn)稱為終點(diǎn)求從某個(gè)源點(diǎn)到圖中其他各頂點(diǎn)的最短路徑稱為單源最短路徑（single-sourceshortestpaths）問(wèn)題，即，已知圖G=(V,E)，找出從某個(gè)給定源點(diǎn)s∈V到V中任一其他頂點(diǎn)的最短路徑示例終點(diǎn)最短路徑路徑長(zhǎng)度b(a,d,b)3c(a,c)5d(a,d)2e(a,d,e)5f(a,d,g,f)8g(a,d,g)6Dijkstra算法求帶權(quán)圖單源最短路徑的算法稱為迪杰斯特拉（Dijkstra）算法它按照路徑長(zhǎng)度不減的次序產(chǎn)生最短路徑，也就是生成的各條路徑的長(zhǎng)度越來(lái)越長(zhǎng)基本思想是：把圖中的所有頂點(diǎn)分成兩個(gè)集合，令S表示已求出最短路徑的頂點(diǎn)集合，其余尚未確定最短路徑的頂點(diǎn)組成另一個(gè)集合V-S。初始時(shí)，S中僅含有源點(diǎn)。按最短路徑長(zhǎng)度不減的次序逐個(gè)把第二個(gè)集合V-S中的頂點(diǎn)加入到S中，不斷擴(kuò)大已求出最短路徑的頂點(diǎn)集合，直到從源點(diǎn)出發(fā)可以到達(dá)的所有頂點(diǎn)都在S中為止給圖中每個(gè)頂點(diǎn)定義一個(gè)距離值，分兩種情況S集合中頂點(diǎn)對(duì)應(yīng)的距離值就是從源點(diǎn)到此頂點(diǎn)的最短路徑長(zhǎng)度集合V-S中頂點(diǎn)對(duì)應(yīng)的距離值是從源點(diǎn)到此頂點(diǎn)、且路徑中僅包括S中的頂點(diǎn)為中間頂點(diǎn)的最短路徑的長(zhǎng)度當(dāng)有V-S中的頂點(diǎn)加入S時(shí)，對(duì)S中頂點(diǎn)的距離值沒(méi)有影響，而有可能使V-S中頂點(diǎn)的距離值變小對(duì)于V-S中的所有頂點(diǎn)如果距離值確實(shí)變小了，則以變化后的值替代原來(lái)的值如果距離值沒(méi)有變小，則保持原值不變?cè)O(shè)圖G=(V,E)，源點(diǎn)為v0，引入輔助數(shù)組distdist[i]表示對(duì)應(yīng)于頂點(diǎn)i的距離值dist的初值為Dijkstra算法的步驟（1）初始化

①設(shè)用帶權(quán)的鄰接矩陣cost表示帶權(quán)有向圖G=(V,E)

②cost[i][j]為弧(vi,vj)上的權(quán)值

（若弧(vi,vj)不存在，則該值為∞，一般地取計(jì)算機(jī)中能表示的最大值）

③S為已找到從源點(diǎn)v0出發(fā)的最短路徑的終點(diǎn)集合，其初態(tài)只含有源點(diǎn)v0

④從v0出發(fā)到圖中其余各頂點(diǎn)vi的距離值為 dist[i]=cost[v0][vi] vi∈V（2）選擇vj，使得dist[j]=min{dist[i]|vi∈V-S} vj即當(dāng)前求得的一條從v0出發(fā)的最短路徑的終點(diǎn)。令S=S∪{vj}（3）修改從v0出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度

如果dist[j]+cost[j][k]<dist[k]，則dist[k]=dist[j]+cost[j][k]（4）重復(fù)執(zhí)行（2）、（3），直到再也沒(méi)有可加入到S中的頂點(diǎn)時(shí)為止示例所有頂點(diǎn)間的最短路徑求得所有頂點(diǎn)間的最短路徑，可以用弗洛伊德（Floyd）算法考慮圖中從頂點(diǎn)vi到頂點(diǎn)vj的一條最短路徑，中間經(jīng)過(guò)或不經(jīng)過(guò)一些頂點(diǎn)如果最短路徑不經(jīng)過(guò)任何中間頂點(diǎn)，則這條最短路徑就是從vi到vj的邊反之，假設(shè)中間經(jīng)過(guò)頂點(diǎn)k，則vi到vj的最短路徑分為從vi到vk及從vk到vj的兩段，并且這兩段分別都是相應(yīng)頂點(diǎn)間的最短路徑，否則可以用更短的路徑來(lái)分別替代它們，從而組成從vi到vj之間更短的路