數(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)先搜索算法，理解圖的連通性及連通分量概念理解圖的生成樹概念，掌握求圖最小代價(jià)生成樹的兩個(gè)算法理解有向無環(huán)圖的概念，掌握?qǐng)D的拓?fù)渑判蛩惴ɡ斫庾疃搪窂礁拍睿莆盏辖芩固乩惴ǖ那蠼膺^程了解各算法的時(shí)間復(fù)雜度本章主要內(nèi)容圖的基本概念12圖基本操作的實(shí)現(xiàn)3圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷4圖的生成樹56單源最短路徑7DAG圖及拓?fù)渑判虻谝还?jié)圖的基本概念圖（graph）由頂點(diǎn)和邊組成一般地，用G=(V,E)來表示，其中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)之間允許有邊，但不能超過一條基本概念圖G=(V,E)中，頂點(diǎn)總數(shù)記為|V|，邊的總數(shù)記為|E|如果圖中邊的數(shù)目較少（相對(duì)于頂點(diǎn)數(shù)來說），則圖稱為稀疏圖邊數(shù)較多的圖稱為密集圖或是稠密圖至于邊數(shù)多到多少是密集圖或少到多少是稀疏圖，并沒有嚴(yán)格的界定當(dāng)圖中邊數(shù)的數(shù)量級(jí)不高于頂點(diǎn)數(shù)的數(shù)量級(jí)時(shí)，就可以認(rèn)為圖是稀疏圖基本概念當(dāng)圖中的邊限定為從一個(gè)頂點(diǎn)指向另一個(gè)頂點(diǎn)時(shí)，稱為有向邊，或稱為?。╝rc）不限定方向的邊稱為無向邊一條無向邊可以看成是兩條方向相反的有向邊組成有向邊的偶對(duì)看作是有序的組成無向邊的偶對(duì)是無序的基本概念有向邊(u,v)表示從頂點(diǎn)u指向頂點(diǎn)v的邊，弧的方向是從u指向v，u稱為弧尾（tail），v稱為弧頭（head）對(duì)于有向邊，(u,v)與(v,u)不同無向邊(u,v)既可以表示從頂點(diǎn)u指向頂點(diǎn)v，也可以表示從頂點(diǎn)v指向頂點(diǎn)u對(duì)于無向邊，(u,v)與(v,u)是等價(jià)的基本概念含有向邊的圖稱為有向圖（directedgraph或簡(jiǎn)寫為digraph）如果圖中的邊都是無向邊，則圖稱為無向圖（undirectedgraph或簡(jiǎn)寫為undigraph）如果一個(gè)圖中既含有有向邊，又含有無向邊，則可以將其中所有的無向邊表示為一對(duì)方向相反的有向邊提到有向圖時(shí)，表明其中所含的邊全部都是有向邊基本概念若無向圖G中含有邊(u,v)，則u和v互為鄰接點(diǎn)（adjacent）邊(u,v)稱為與頂點(diǎn)u和v相關(guān)聯(lián)（incident），也可以說邊(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ù)無向圖中兩個(gè)頂點(diǎn)之間最多只能有一條邊有向圖中兩個(gè)頂點(diǎn)之間最多有兩條方向相反的弧圖中不包含(i,i)形式的邊，即沒有頂點(diǎn)自身到自身的邊在無向圖中，與頂點(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)的無向圖中，其邊數(shù)最多可達(dá)n(n-1)/2有向圖中由于邊具有方向性，所以可能的最大邊數(shù)比無向圖多了一倍，含n個(gè)頂點(diǎn)的有向圖中最大邊數(shù)為n(n-1)

包含了所有可能邊的圖稱為完全圖（completegraph）假設(shè)無向圖G=(V,E)中含有n個(gè)頂點(diǎn)，e條邊，每個(gè)頂點(diǎn)的度為di(0≤i≤n-1)，則下列關(guān)系式成立：若兩個(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)成的圖示例對(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)不帶回路的圖稱為無環(huán)圖。不帶回路的有向圖稱為有向無環(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ì)于無向圖G，如果頂點(diǎn)u和頂點(diǎn)v之間有路徑，則稱這兩個(gè)頂點(diǎn)是連通的如果無向圖G中任意一個(gè)頂點(diǎn)到其他任意頂點(diǎn)都至少存在一條路徑，也就是說，圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱圖G為連通圖（connectedgraph）無向圖中的極大連通子圖稱為連通分量（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）示例圖的基本操作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)以鄰接矩陣（adjacencymatrix）為代表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以鄰接表（adjacencylist）為代表鄰接矩陣設(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ì)稱性用鄰接矩陣表示圖時(shí)，可以很容易地判定圖中任意兩頂點(diǎn)之間是否存在邊（或?。┤艟仃囋谹[i][j]為1或wij，就表示從vi到vj有一條邊（或?。?，否則從vi到vj沒有邊（或?。┐嬖诮柚卩徑泳仃嚕苋菀椎玫綀D中各頂點(diǎn)的度對(duì)于無向圖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ù)無關(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è)域，用來存儲(chǔ)兩個(gè)頂點(diǎn)間這條邊的權(quán)表結(jié)點(diǎn)結(jié)構(gòu)用鄰接表表示有n個(gè)頂點(diǎn)和e條邊的無向圖時(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)建無向圖創(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)過一定的路線訪問圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)被訪問且只訪問一次，這一過程稱為圖的遍歷深度優(yōu)先搜索（depthfirstsearch,DFS）遍歷廣度優(yōu)先搜索（breadthfirstsearch,BFS）遍歷深度優(yōu)先搜索選擇圖中任意指定頂點(diǎn)為起始頂點(diǎn)，將其設(shè)為當(dāng)前頂；訪問當(dāng)前頂點(diǎn)v，輸出關(guān)于v的相關(guān)信息將v的訪問標(biāo)志置為VISITED如果v的鄰接點(diǎn)中存在未被訪問的頂點(diǎn)w，則將w設(shè)為當(dāng)前頂點(diǎn)，轉(zhuǎn)②繼續(xù)；否則轉(zhuǎn)⑤回退到最近被訪問過的且仍有未被訪問鄰接點(diǎn)的頂點(diǎn)u，轉(zhuǎn)④繼續(xù)；不能回退時(shí)，轉(zhuǎn)⑥如果所有頂點(diǎn)均已訪問，則遍歷結(jié)束，否則，選擇未被訪問的另一個(gè)頂點(diǎn)作為起始頂點(diǎn)，繼續(xù)上述過程v0,v1,v3,v7,v4,v5,v2,v6DFS算法當(dāng)圖是連通圖時(shí)，使用DFS算法從某個(gè)頂點(diǎn)出發(fā)，可以訪問到圖中的所有頂點(diǎn)。如果圖不連通，則一次調(diào)用DFS不能訪問圖中的全部頂點(diǎn)，只能訪問初始頂點(diǎn)所在的連通分量中的所有頂點(diǎn)廣度優(yōu)先搜索選擇圖中指定的頂點(diǎn)v為起始頂點(diǎn)，將其入隊(duì)列，且其訪問標(biāo)志置為VISITED隊(duì)列為空時(shí)，轉(zhuǎn)⑤；隊(duì)列不為空時(shí)，出隊(duì)列，設(shè)出隊(duì)列的頂點(diǎn)為w輸出關(guān)于w的相關(guān)信息找到與頂點(diǎn)w相鄰接的且訪問標(biāo)志不是VISITED的頂點(diǎn)序列w1,w2,…,wk，依次入隊(duì)列，轉(zhuǎn)②如果所有頂點(diǎn)均已訪問，則遍歷結(jié)束，否則，選擇未被訪問的一個(gè)頂點(diǎn)作為起始頂點(diǎn)，繼續(xù)上述過程廣度優(yōu)先搜索過程中，使用了一個(gè)隊(duì)列作為輔助存儲(chǔ)結(jié)構(gòu)，頂點(diǎn)是一批批加入隊(duì)列的如果圖是不連通的，則這個(gè)過程也不能訪問圖中的全部頂點(diǎn)，而只能遍歷圖中某個(gè)連通分量中的所有頂點(diǎn)BFS算法第五節(jié)圖的生成樹設(shè)G=(V,E)是一個(gè)連通的無向圖，包含圖中全部頂點(diǎn)的極小連通子圖稱為圖的生成樹極小連通子圖是指含有圖中所有頂點(diǎn)并使圖仍保持連通性的最小子圖從圖中任一頂點(diǎn)出發(fā)，按照深度優(yōu)先搜索策略或是廣度優(yōu)先搜索策略，可以訪問到圖中的全部頂點(diǎn)。在遍歷的過程中，所經(jīng)過的邊集設(shè)為T(G)，沒有經(jīng)過的邊集設(shè)為B(G)。T(G)即構(gòu)成G的一棵生成樹生成樹中所含的邊數(shù)必定是n-1進(jìn)行深度優(yōu)先搜索時(shí)得到的生成樹稱為深度優(yōu)先生成樹進(jìn)行廣度優(yōu)先搜索時(shí)得到的生成樹稱為廣度優(yōu)先生成樹進(jìn)行遍歷時(shí)可能會(huì)得到不同的頂點(diǎn)序列，實(shí)際上，圖的生成樹也可能是不唯一的同一個(gè)圖的深度優(yōu)先生成樹，也可能不是唯一的廣度優(yōu)先生成樹，也可能不是唯一的示例兩棵深度優(yōu)先生成樹圖的最小代價(jià)生成樹帶權(quán)圖的每條邊上都有一個(gè)非負(fù)的權(quán)值，稱邊權(quán)值之和最小的生成樹為最小代價(jià)生成樹（minimum_costspanningtree，MST）。簡(jiǎn)稱為最小生成樹給定一個(gè)無向連通圖G，則MST是一個(gè)包括G的所有頂點(diǎn)及其邊子集的圖，邊的子集滿足下列條件這個(gè)子集中所有邊的權(quán)之和為所有滿足條件的子集中最小的子集中的邊能夠保證圖是連通的最小生成樹性質(zhì)它含有圖G中的所有n個(gè)頂點(diǎn)它沒有回路。因?yàn)閺臉?gòu)成回路的各邊中去掉一條邊，仍能保證其連通性，而所得的權(quán)值總和可以進(jìn)一步地減少它含有的邊數(shù)為n-1去掉最小生成樹中的一條邊，換上不在最小生成樹中的另外一條邊，在仍要求連通的前提下，所得的權(quán)值總和都不會(huì)小于原最小生成樹的權(quán)值總和普里姆算法設(shè)連通的帶權(quán)圖G=(V,E)，V是頂點(diǎn)集合，E是邊的集合設(shè)T是圖G的最小生成樹的邊集合，U是最小生成樹的頂點(diǎn)集合，設(shè)由頂點(diǎn)v1開始，初始時(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)值的邊，逐步生成最小生成樹普里姆算法共進(jìn)行n-1輪的選邊操作，每輪選邊時(shí)，最多從n-1條邊中選中權(quán)最小的邊。故對(duì)于含|V|個(gè)頂點(diǎn)的圖，算法的時(shí)間復(fù)雜度為O(|V|2)當(dāng)圖是一個(gè)邊稠密的圖時(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|)。所以，克魯斯卡爾算法適宜求稀疏圖的最小生成樹第六節(jié)有向無環(huán)圖及拓?fù)渑判驁D中不存在回路的有向圖稱為有向無環(huán)圖（directedacyclinegraph），簡(jiǎn)稱為DAG圖比如，表達(dá)式樹可表示為DAG圖拓?fù)渑判蛴邢驘o環(huán)圖G=(V,E)的拓?fù)湫蛄惺荊中頂點(diǎn)的一個(gè)線性序列，并且滿足以下關(guān)系：對(duì)于圖G中的所有頂點(diǎn)v和w，如果(v,w)∈E，則在線性序列中v排在w之前求有向無環(huán)圖拓?fù)湫蛄械倪^程稱為拓?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)開始之前結(jié)束，即vj活動(dòng)必須在vi活動(dòng)結(jié)束之后才能開始在AOV網(wǎng)中不允許出現(xiàn)回路，因此AOV網(wǎng)必是有向無環(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沒有有向路徑，則在拓?fù)湫蛄兄校瑅i與vj的先后次序可以任意五門課程排成的拓?fù)湫蛄袨?C1,C2,C3,C4,C5還可以排列成 C1,C2,C5,C3,C4課程代號(hào)課程名稱先導(dǎo)課C1高等數(shù)學(xué)無C2程序設(shè)計(jì)基礎(chǔ)無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ù)組來記錄各個(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è)沒有前驅(qū)（入度為0）的頂點(diǎn)，輸出之從圖中刪除該頂點(diǎn)和以它為尾的所有的弧，即將輸出頂點(diǎn)的所有后繼頂點(diǎn)的入度值減1。轉(zhuǎn)②步驟②、③重復(fù)執(zhí)行，每輸出一個(gè)頂點(diǎn)，就修改入度值數(shù)組，然后再選擇滿足條件的頂點(diǎn)輸出，再修改數(shù)組直至輸出全部頂點(diǎn)或者還沒有輸出全部頂點(diǎn)，但已找不到?jīng)]有前驅(qū)的頂點(diǎn)（即入度值為0的頂點(diǎn)）為止第一種情況表示拓?fù)渑判蛞呀?jīng)完成第二種情況表明原有向圖中含有回路第七節(jié)單源最短路徑對(duì)于帶權(quán)圖，修改路徑長(zhǎng)度概念兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度定義為兩頂點(diǎn)間路徑上各邊的權(quán)值之和路徑的開始頂點(diǎn)稱為源點(diǎn)，目的頂點(diǎn)稱為終點(diǎn)求從某個(gè)源點(diǎn)到圖中其他各頂點(diǎn)的最短路徑稱為單源最短路徑（single-sourceshortestpaths）問題，即，已知圖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)度不減的次序