數(shù)據(jù)結(jié)構(gòu)-第6章-圖

6.1圖的基本概念第6章圖圖是一種非線性結(jié)構(gòu)，它比樹型結(jié)構(gòu)更復(fù)雜。在線性表中，數(shù)據(jù)元素之間是一對一的關(guān)系，即除第一個元素外的每個元素都有一個唯一的直接前驅(qū)，除最后一個元素外的每個元素都有一個唯一的直接后繼。在樹中，數(shù)據(jù)元素是一對多的關(guān)系，即每個結(jié)點最多只能有一個直接前驅(qū)（即雙親結(jié)點），每個結(jié)點都可能有多個直接后繼（即孩子結(jié)點）。在圖中，數(shù)據(jù)元素之間是多對多的關(guān)系，即任何兩個元素之間都可能存在關(guān)系。圖的應(yīng)用十分廣泛，電路分析、交通運輸管理、線路的鋪設(shè)、集成電路板布線、工作安排等很多問題都可以用圖來表示。近年來，圖的應(yīng)用研究已經(jīng)滲入到計算機科學(xué)、工程技術(shù)、社會科學(xué)和管理學(xué)等多個領(lǐng)域。6.1圖的基本概念第6章圖6.1.1圖的定義為了與樹型結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點稱為頂點（vertex），將頂點間的連線（關(guān)系）稱為邊（edge）。1.圖（Graph）由頂點集合和連接這些頂點的邊組成。即G=(V，E)其中，V是圖G中的頂點集合，E是邊的集合。如圖6-1（a）所示有4個頂點，V={v0，v1，v2，v3}，5條邊，E={(v0，v1)，(v0，v2)，（v0，v3），（v1，v3），（v2，v3）}。2.如果頂點v，w間有邊存在，并且邊沒有方向，則可以表示成無序偶對（v，w），那么稱這條邊為無向邊；若圖中任意兩頂點間的邊都是無向的，則稱該圖為無向圖（undirectedgraph）。如圖6-1（a）為一無向圖。6.1圖的基本概念第6章圖3.如果頂點v，w間有邊存在，并且邊有方向，則可以表示成有序偶對<v，w>，那么稱這條邊為有向邊或弧，其中，v稱為弧尾，w稱為弧頭；若圖中任意兩頂點間的邊都是有向的，則稱該圖為有向圖（directedgraph）。如圖6-1（b）所示有4個頂點，V={v0，v1，v2，v3}，5條弧，E={<v0，v3>，<v1，v0>，<v2，v0>，<v2，v3>，<v3，v1>}。4.有向圖的邊或弧上具有與它相關(guān)的數(shù)，這種數(shù)叫做權(quán)（Weight）。這些權(quán)可以表示從一個頂點到另一個頂點的時間、距離、造價等等。這種帶權(quán)的圖稱為網(wǎng)（Network）或帶權(quán)圖，網(wǎng)可分為有向網(wǎng)和無向網(wǎng)。如圖6-1（c）所示為一個有4個頂點，V={v0，v1，v2，v3}，5條弧的有向網(wǎng)，在網(wǎng)中表示邊或弧時要給出權(quán)值，E={<v0，v3，2>，<v1，v0，5>，<v2，v0，10>，<v2，v3，6>，<v3，v1，1>}。6.1圖的基本概念第6章圖5.設(shè)有兩個圖G＝(V，E)和G’＝(V’，E’)。若V’íV且E’íE,則稱圖G’是圖G的子圖(subgraph)。如圖6-1（d）是圖6-1（a）的子圖，有3個頂點，V={v0，v1，v2}，2條邊，E={(v0，v1)，(v0，v2)}。6.1圖的基本概念第6章圖6.1.2相關(guān)術(shù)語1. 無向完全圖（undirectedcompletegraph）n個頂點的無向圖最大邊數(shù)是n(n-1)/2，具有n(n-1)/2條邊的無向圖稱為無向完全圖。圖6-2（a）中，頂點數(shù)為4，邊數(shù)n(n-1)/2=4*（4-1）/2=6，每個頂點都和其它頂點相連。2. 有向完全圖（directedcompletegraph）具有n(n-1)條弧的有向圖稱為有向完全圖。在有向完全圖中，任意兩頂點之間均有方向相反的兩條弧。圖6-2（b）中，頂點數(shù)為3，邊數(shù)n(n-1)=3*（3-1）=6。6.1圖的基本概念第6章圖3. 稀疏圖（sparegraph）邊數(shù)較少的圖稱為稀疏圖。4. 密集圖（densegraph）邊數(shù)較多的圖稱為密集圖。5. 相鄰頂點、相關(guān)聯(lián)弧或邊在圖G=(V，E)中，若<v，w>íE或(v，w)íE，則v，w是相鄰頂點(adjacent)，弧<v，w>或邊(v，w)是與頂點v和w相關(guān)聯(lián)(incident)的弧或邊。圖6-2（a）中，頂點v3和頂點v0、v1、v2相關(guān)連。6. 度（degree）與頂點相關(guān)聯(lián)的邊的數(shù)目稱為該頂點的度，記為TD（V）。對于有向圖，則把以頂點V為弧尾的數(shù)目稱為頂點V的出度，記為OD（V），把以頂點V為弧頭的弧的數(shù)目稱為頂點V的入度，記為ID（V）。頂點V的度為：TD（V）=ID（V）+OD（V）圖6-2（a）中，各頂點的度均為3，圖6-1（b）中，頂點v3的入度為2、出度為1。6.1圖的基本概念第6章圖7. 路徑(path)在圖G＝(V，E)中，若存在一個頂點序列vp1，vp2，…，vpm，使得(vi，vp1)、(vp1，vp2)、???、(vpm，vj)均屬于E，則稱頂點vi到vj存在一條路徑。路徑長度定義為路徑上邊或弧的數(shù)目。圖6-2（a）中，從v0到v3的路徑有v0、v3或v0、v1、v3或v0、v2、v3。若一條路徑上除了vi和vj可以相同外，其余頂點均不相同，則稱此路徑為一條簡單路徑。起點和終點相同的簡單路徑稱為簡單回路或簡單環(huán)。不帶回路的圖稱為無圈（環(huán)）圖；不帶回路的有向圖稱為有向無圈（環(huán)）圖。6.2圖的存儲結(jié)構(gòu)第6章圖6.2.1圖的順序存儲——鄰接矩陣圖的鄰接矩陣存儲也稱數(shù)組表示法。使用一個數(shù)組vertex存儲圖中的頂點信息，用一個二維數(shù)組arc存儲頂點之間的鄰接關(guān)系，這個二維數(shù)組稱為鄰接矩陣。對于具有n個頂點的圖G=(V，E)來說，它的鄰接矩陣是一個n階方陣，且滿足：6.2圖的存儲結(jié)構(gòu)第6章圖6.2.2圖的鏈?zhǔn)酱鎯Α徑颖懋?dāng)圖中的邊數(shù)少于頂點個數(shù)時，鄰接矩陣中出現(xiàn)大量的零元素，如果存儲這些零元素，將浪費大量的存儲空間。改進的一種方法是采用前面介紹過的三元組來存儲實現(xiàn)，另一種方法是將鄰接矩陣的n行改為n個單鏈表，即對圖中每個頂點vi建立一個單鏈表，稱此單鏈表為頂點vi的鄰接表，在vi的鄰接表中將所有與vi相鄰頂點的序號鏈接起來。鄰接表中的結(jié)點稱為表結(jié)點，每個結(jié)點均包含兩個域：鄰接點域adjvex和指針域next。adjvexnext鄰接點域用于存放與頂點vi相鄰接的頂點序號，指針域用于指向下一個表結(jié)點。同時，使用一個一維數(shù)組vertices存儲圖中的頂點信息，頂點數(shù)組元素除存儲頂點vi本身外，還設(shè)置了指針域，作為鄰接表的表頭指針，圖的頂點元素如下：vertexlink6.3圖的遍歷第6章圖與樹的遍歷類似，圖的遍歷（graphtraversal）是從某個頂點出發(fā)訪問圖中所有頂點，且使得每一個頂點僅被訪問一次。圖的遍歷是圖的運算中較為重要的運算，圖的許多運算均以遍歷運算為基礎(chǔ)。例如領(lǐng)土問題：假設(shè)有許多國家，有些國家兩兩相互連接，要求從某個指定的起始國出發(fā)，通過國家之間的連接，從一國到另一國，最后到達指定的終點國。通常情況下，起始國和終點國之間并不直接相連。圖遍歷的典型算法是從某一個起點出發(fā)，試探性的訪問其余頂點。但在遍歷過程中可能出現(xiàn)下列問題，首先，從起點出發(fā)可能到達不了其它所有頂點，非連通圖就會出現(xiàn)這種情況；其次，有些圖存在回路，這時必須在算法中保證不會因回路而陷入死循環(huán)。6.3圖的遍歷第6章圖6.3.1深度優(yōu)化遍歷圖的深度優(yōu)先遍歷（depth-firstsearch或DFS）的基本思想是從圖中某個頂點V出發(fā)，訪問此頂點；然后依次從V的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V有路徑的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。對圖按深度優(yōu)先遍歷得到的遍歷序列稱為DFS序列。一個圖的DFS序列不一定唯一，這與算法、圖的存儲結(jié)構(gòu)及選定的起始點都有關(guān)。6.3圖的遍歷第6章圖6.3.2廣度優(yōu)化遍歷廣度優(yōu)先遍歷（breadth-firstsearch或BFS）的基本思想是從圖中某個頂點V出發(fā)，訪問此頂點V后，依次訪問V的各個未曾訪問過的鄰接點w1、w2、????；然后再依次訪問w1、w2、????的未被訪問的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。對圖按廣度優(yōu)先遍歷得到的遍歷序列稱為BFS序列。一個圖的BFS序列不一定唯一，這與算法、圖的存儲結(jié)構(gòu)及選定的起始點都有關(guān)。6.3圖的遍歷第6章圖6.3.3遍歷的應(yīng)用1.可達性在圖G=(V，E)中，如果從頂點vi到頂點vj有路徑存在，那么就說從頂點vi到頂點vj是可達的。對于一般圖而言，未必任意一對頂點都有可達性。如圖6-11中的有向圖，從v0到其它頂點都是可達的，而從其它頂點都無法到達v0。6.3圖的遍歷第6章圖2.計算非連通圖的連通子圖個數(shù)在無向圖中，所有可達的頂點組成了圖中的一個連通子圖。為了計算某個圖中連通子圖的個數(shù)，我們對該圖的頂點進行迭代，對每一個未訪問過的頂點都調(diào)用遍歷算法。由于每一個未訪問過的頂點都是與那些已經(jīng)訪問過的頂點不可達的，所以調(diào)用遍歷算法的次數(shù)就是連通子圖的個數(shù)。6.4最小生成樹第6章圖生成樹和生成森林對于一個擁有n個頂點的無向連通圖G，它的邊數(shù)一般大于等于n-1條。若從中選擇n-1條邊，使得無向圖仍然連通，則由n個頂點及這n-1條邊所組成的子圖G’稱為原無向圖的生成樹。G’是G的極小連通子圖。生成樹具有以下特點：（1）在生成樹中去掉任何一條邊，此子圖就會變成非連通圖；（2）任意兩個頂點之間有且僅有一條路徑，如再增加一條邊就會出現(xiàn)回路；（3）遍歷連通圖時經(jīng)過的頂點和邊構(gòu)成的子圖是原圖的生成樹。由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹，簡稱為DFS生成樹；由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹，簡稱為BFS生成樹。6.4最小生成樹第6章圖（1）普里姆（Prim）算法prim算法的基本思想是：假設(shè)N=（V，E)是連通網(wǎng)，令T=(U，TE)是N的最小生成樹。算法的基本思想是：T初始狀態(tài)為U={v0}(v0?V)，TE={}，重復(fù)執(zhí)行下述操作：①在所有u∈U,v∈V－U的邊(u，v)?E中，找一條代價最小的邊（ui，vj）并入集合TE，同時將vj并入U中；②如此不斷重復(fù)，直到U＝V為止。此時TE必有n-1條邊，則T（V，TE）為N的最小生成樹。6.4最小生成樹第6章圖（2）克魯斯卡爾（Kruskal)算法Kruskal算法的基本思想是：假設(shè)連通網(wǎng)N=（V，{E}），則令最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=（V，{}），圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。依次類推，直至T中所有頂點都在同一連通分量上為止。6.5拓?fù)渑判虻?章圖1．AOV網(wǎng)用頂點表示活動，弧表示活動之間優(yōu)先關(guān)系的有向圖，稱為頂點表示活動的網(wǎng)（ActivityOnVertexNetwork），簡稱AOV網(wǎng)。由上述的描述可以看出，AOV網(wǎng)的特點是在網(wǎng)中一定不能有有向回路，即是一個有向無環(huán)圖。檢測網(wǎng)中是否存在回路，我們采用拓?fù)渑判虻姆椒ā?.5拓?fù)渑判虻?章圖2．拓?fù)渑判蛲負(fù)渑判颍╰opologicalsort）是有向無環(huán)圖的一個重要應(yīng)用。在給定的有向圖G中，若頂點序列vi1，vi2，???，vin滿足下列條件：若在有向圖G中從頂點vi到頂點vj有一條路徑，則在序列中頂點vi必在頂點vj之前，便稱這個序列為一個拓?fù)湫蛄?。求一個有向圖拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。拓?fù)渑判蚴菍OV網(wǎng)中的各個頂點排列成一個有序序列，即將非線性結(jié)構(gòu)的有向圖進行線性化的重要手段。對于AOV網(wǎng)不應(yīng)該存在有向回路，因為如果存在回路就意味著某項活動的開始是以自己工作的完成為先決條件的，這種死鎖的現(xiàn)象會導(dǎo)致工程不可進行。而任何無回路的AOV網(wǎng)的所有頂點都可以排成一個拓?fù)湫蛄校⑶彝負(fù)湫蛄胁皇俏ㄒ坏摹?.5拓?fù)渑判虻?章圖3．拓?fù)渑判蛩惴ㄍ負(fù)渑判蛩惴ǖ幕舅枷胧牵海?）在有向圖中選一個沒有前驅(qū)的頂點且輸出之；（2）從圖中刪除該頂點和所有以它為尾的?。唬?）重復(fù)（1）、（2）兩步，直至全部頂點均已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點為止。6.6最短路徑第6章圖最短路徑問題是有向網(wǎng)的一個典型應(yīng)用問題，在交通網(wǎng)絡(luò)、工程設(shè)計、通訊工程等領(lǐng)域被廣泛應(yīng)用。例如，給定A、B、C、D四個城市，那么在哪個城市建立急救中心，使得急救中心到最遠的城市的距離最近。這就是設(shè)計人員經(jīng)常遇到的醫(yī)院選址問題。在各城市間有交通通道如高速公路等，圖6-21（a）給出A、B、C、D四個城市間的交通圖，考慮到交通圖的有向性（如高速公路，從A城市到B城市的距離可能不等于從B城市到A城市的距離），我們用箭頭標(biāo)識出公路的方向同時在公路上表示出它的長度。6.6最短路徑第6章圖1．單源最短路徑我們要研究的第一個問題是單源最短路徑（single-sourceshortestpath）問題，它是指：對于給定的有向網(wǎng)G=(V，E)及某個給定的源點v(v∈V)到圖中其余所有頂點的最短路經(jīng)。假設(shè)圖6-22所示的有向網(wǎng)絡(luò)表示計算機網(wǎng)絡(luò)的傳輸圖，頂點代表網(wǎng)絡(luò)中的計算機，弧上的權(quán)代表向一個網(wǎng)絡(luò)鄰居發(fā)送一條信息所需要的時間，怎樣找到一種最節(jié)省時間的方式從一臺計算機向網(wǎng)上所有其它計算機發(fā)送一條信息。這實際上就是求有向網(wǎng)的單源最短路徑問題。6.6最短路徑第6章圖2．每對頂點間的最短路徑問題下面我們分析每對頂點間的最短路徑問題（all-pairsshortest-paths），即對于給定的一個帶權(quán)有向圖G=(V，E)，找出V中每一對頂點間最短路徑。解決此問題的一種方法是每次以一個頂點為源點，重復(fù)執(zhí)行Dijkstra算法n次，因此其時間性能是O(n3)。另一種是弗洛伊德（Floyd）算法，它是解決關(guān)于密集圖的每對頂點間最短路徑問題的動態(tài)程序設(shè)計方法（也是一個貪心算法），它有效地利用了鄰接矩陣。設(shè)有一個帶權(quán)圖G=(V，E)，有n個頂點，W(u，v)是弧<u，v>上的權(quán)值，各頂點按從1到n的順序編號，即V={v1，v2，???，vn}，而且設(shè)Vk是由V中前K個頂點組成的集合，即Vk={v1，v2，???，vk}(0≤k≤n)，其中k=0時為空集。6.6最短路徑第6章圖設(shè)Pk（u，v）是從頂點u到v且只經(jīng)過Vk中頂點的最短路徑，即有：

設(shè)Dk(u，v)是路徑Pk（u，v）的長度，即

由于，因此，路徑P0對應(yīng)于網(wǎng)中的弧，即

而路徑長度D0對應(yīng)于網(wǎng)中弧上的權(quán)值，即

6.6最短路徑第6章圖用Floyd算法可計算出序列D0，D1，???，Dn，由于Vi+1=Vi∪{vi+1}，所以只要考慮經(jīng)過頂點vi+1的路徑，就可從Di獲得Di+1。如圖6-24所示。6.7關(guān)鍵路徑第6章圖有向無環(huán)圖的另一個重要應(yīng)用就是關(guān)于關(guān)鍵路徑的分析。關(guān)鍵路徑的分析在許多問題中都會遇到，比如對一個建筑施工計劃的安排來說，在灌注基礎(chǔ)之前，先要挖土方；在主體結(jié)構(gòu)完成之后，才能考慮水電氣設(shè)施。對于這每一項工作都要花費一定的時間。我們可以用一個帶權(quán)有向圖G=(V，E)來描述建筑施工計劃的安排，其中用頂點表示事件，用弧表示一項任務(wù)及事件安排的先后關(guān)系，它的權(quán)值表示完成這項任務(wù)所需要的時間。一項工程的施工計劃如圖6-27所示。在這項工程中，有9項任務(wù)，用ai表示（i=1、2、???、9），7個事件，用A、B、???、G表示，事件A表示整個工程開始；事件G表示整個工程結(jié)束。圖6-27施工計劃安排6.7關(guān)鍵路徑第6章圖1．AOE網(wǎng)用頂點表示事件，但事件僅僅是可以明確定義的時間點，而不消耗時間；弧表示一項任務(wù)或活動，弧上的權(quán)值表示活動持續(xù)的時間，這種有向無環(huán)圖稱為邊表示活動的網(wǎng)(ActivityOnEdge)，簡稱AOE網(wǎng)。由于一個工程只有一個開始點和一個完成點，所以在正常情況下，AOE網(wǎng)中只有一個入度為零的頂點，稱為源點；也只有一個出度為零的頂點，稱為匯點。AOE網(wǎng)具有以下兩個性質(zhì)：（1）只有在某頂點代表的事件發(fā)生后，從該頂點出發(fā)的各項活動才能開始；（2）只有在進入該頂點的各項活動都已經(jīng)完成，該頂點代表的事件才能發(fā)生。6.7關(guān)鍵路徑第6章圖（1）事件的最早發(fā)生時間（earliesteventtime）通常假定源點的最早發(fā)生時間是vet[0]=0，那么，第k個事件的最早發(fā)生時間vet[k]首先應(yīng)考慮鄰接到該事件的所有事件vj及活動<vj，vk>的持續(xù)時間，如圖6-28（a）所示，并計算vj的最早開始時間與相應(yīng)活動的持續(xù)時間之和，那么這些和中的最大值即為vet[k]，也就是說，vet[k]是從源點到頂點vk的最大路徑長度，即

其中，是所有以頂點vk為弧頭的弧的集合，是弧上的權(quán)值。6.7關(guān)鍵路徑第6章圖（2）事件的最遲發(fā)生時間（latesteventtime）事件的最遲發(fā)生時間vlt是指不影響整個工程工期的情況下事件允許的最晚發(fā)生時間。故匯點事件的最遲發(fā)生時間是vlt[n-1]=vet[n-1]，即匯點事件的最早發(fā)生時間和最遲發(fā)生時間相同才不至于延遲工期。那么，第k個事件的最遲發(fā)生時間vlt[k]同樣首先應(yīng)考慮鄰接于該事件的所有事件vj及活動<vk，vj>的持續(xù)時間，如圖6-28（b）所示，計算vj的最遲開始時間與相應(yīng)活動的持續(xù)時間之差，這些差中的最小值即為vlt[k]，即6.7關(guān)鍵路徑第6章圖（3）活動的最早開始時間（earliestactivitytime）假設(shè)活動ai是由弧<vk，vj>表示，如圖6-29所示。根據(jù)AOE的性質(zhì)（1），只有事件vk發(fā)生后活動ai才能開始，即活動ai最早開始時間et[i]應(yīng)等于事件vk的最早發(fā)生時間，因此有圖6-29弧<vk，vj>上的活動ai6.7關(guān)鍵路徑第6章圖（4）活動的最遲開始時間假設(shè)活動ai是由弧<vk，vj>表示，活動ai的最遲開始時間lt[i]是指不推遲工程工期的情況下活動允許的最晚開始時間，所以活動ai的最遲開始時間要保證事件vj的最遲發(fā)生時間不拖后，因此有其中，是弧上的權(quán)值。我們定義活動可延遲而又不影響工程進度的時間為松弛時間（slacktime），則對應(yīng)于弧<vk，vj>的活動ai的松弛時間為6.7