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

第七章:圖

第一節(jié):圖的基本概念無向圖G是一個(gè)有序?qū)Γ╒，E），V是一個(gè)有限個(gè)頂點(diǎn)的集合，E是由V中兩個(gè)不同元素組成的子集的集合，E中的元素稱為邊。若G中，若i≠j，i,j∈V,(I,j)∈E，稱i和j相鄰接有向圖：圖G是一個(gè)有序?qū)?，（V，E），V是一個(gè)有限個(gè)頂點(diǎn)的集合，E是由V中兩個(gè)不同元素組成的有序?qū)Φ募希珽中的元素稱為邊.若G中，i≠j，I,j∈V<I,j>∈E，<I,J>是G中的一條邊，那么稱I是這條邊的尾頂點(diǎn)，J是這條邊的頭頂點(diǎn)，稱I是鄰接到J的頂點(diǎn)，J是鄰接于I的頂點(diǎn)。對(duì)圖：用V（G）表示頂點(diǎn)的集合，E（G）表示邊的集合：V（G1）={1，2，3，4，5}E（G1）={（1，2），（1，3），（1，4），（2，3），（2，5），（3，4），（3，5），（4，5）}V（G2）={1，2，3，4，5}E（G2）={<1,2>,<1,4>,<2,1>,<2,5>,<3,2>,<3,5>,<4,3>,<5,4>}設(shè)：有兩個(gè)圖G和G’。G=（V，E），G’=（V’,E’）且滿足V’包含于V,E’包含于E,則稱G’是G的子圖每對(duì)頂點(diǎn)之間都有一條邊的無向圖，稱為完全無向圖。每對(duì)頂點(diǎn)I和J之間都有邊<I,J>和<J,I>的有向圖，稱為完全有向圖。無向圖G=（V，E）中，若從頂點(diǎn)V到頂點(diǎn)W的一條路徑是由不同頂點(diǎn)組成的頂點(diǎn)序列（V0，V1，……VK）,其中V0=V，VK=W，且（Vi,Vi+1）∈V（G），（0≤i≤K）,通常用（V0，V1，……VK）表示這條路徑，稱這條路徑的長(zhǎng)度為K，只有一個(gè)頂點(diǎn)時(shí)，稱V到自身的路徑長(zhǎng)度為零。若無向圖G中，每對(duì)頂點(diǎn)V和W都有從V到W的路徑，那么稱為無向圖G是連通的，稱無向圖G中的極大連通子圖為圖G的連通分量有向圖G=（V，E）中，從頂點(diǎn)V到W的一條路徑（V0，V1，……VK）其中V0=V，VK=W，且（Vi,Vi+1）∈V（G），（1≤i≤K）稱（V0，V1，……VK）是V到W的路徑，路徑長(zhǎng)度為K，只有一個(gè)頂點(diǎn)時(shí)，V到自身的路徑長(zhǎng)度為零。若有向圖G中每對(duì)頂點(diǎn)V和W都有從V到W的路徑，稱G是強(qiáng)連通的，若從頂點(diǎn)V到W只有一個(gè)路徑，稱有向圖G是弱連通的。有向圖的強(qiáng)連通分量有向圖的弱連通分量回路（環(huán)）{無向回路、有向回路無向圖G中，若v∈V（G），那么與V鄰接的頂點(diǎn)個(gè)數(shù)稱為頂點(diǎn)V的度。有向圖G中，如果v∈V（G），那么鄰接到V的頂點(diǎn)個(gè)數(shù)為頂點(diǎn)V的入度,鄰接于V的頂點(diǎn)個(gè)數(shù)為頂點(diǎn)V的出度第二節(jié):圖的存貯結(jié)構(gòu)鄰接矩陣若無向圖G=（V，E）是具有n(n≥1)個(gè)頂點(diǎn)的無向圖,那么鄰接矩陣A的大小是n*n若有向圖G=（V，E）是具有n個(gè)頂點(diǎn)的有向圖。無向圖的鄰接矩陣是對(duì)稱的，因而可用上三角形（或下三角）陳來存貯，所需空間為n(n+1)/2二、鄰接表出度，直接查結(jié)點(diǎn)個(gè)數(shù)但入度，必須掃描整個(gè)鏈接表，查看I個(gè)結(jié)點(diǎn)的出現(xiàn)次數(shù)，該出現(xiàn)次數(shù)即為入度。制作一個(gè)逆鄰接表，這樣計(jì)算入度方便邊上帶權(quán)的圖：帶權(quán)圖Wij表示<I,J>邊上的權(quán)鄰接矩陣A的表示法無向圖有向圖第三節(jié)圖的遍歷與圖的鏈接分量G是連通圖從圖中某一頂點(diǎn)出發(fā)，沿著G的邊訪問到G中所有頂點(diǎn)，且每個(gè)頂點(diǎn)只訪問一次稱作圖的遍歷。一深度優(yōu)先搜索法深度遍歷過程：首先訪問v選擇一個(gè)與V相鄰接w且visit[w]==0，再從W開始深度搜索每當(dāng)?shù)竭_(dá)一個(gè)其所有相鄰結(jié)點(diǎn)都被訪問過了，就退回到上一個(gè)有未被訪問過的鄰接結(jié)點(diǎn)上面過程直到所有頂點(diǎn)都被訪問過了，或再也無法到達(dá)未曾訪問過的頂點(diǎn)。深度優(yōu)先：從頂點(diǎn)1出發(fā)得到的頂點(diǎn)序列：{1，2，4，5，8，3，6，9，7}廣度優(yōu)先：從頂點(diǎn)為出發(fā)得到的頂點(diǎn)序列：{1，2，4，5，3，8，6，7，9}廣度優(yōu)先搜索法實(shí)現(xiàn)遍歷過程①把隊(duì)列置空②打印出發(fā)頂點(diǎn)，置該頂點(diǎn)已訪問過③讓出發(fā)點(diǎn)進(jìn)隊(duì)④若隊(duì)列不空，則(a)取出隊(duì)組的中頂點(diǎn)V(b)在鄰接表中，依次取得與頂點(diǎn)V鄰接的各個(gè)頂點(diǎn)(i)若當(dāng)前取得的鄰接頂點(diǎn)未被訪問，則(1)打印該頂點(diǎn)，置該頂點(diǎn)被訪問標(biāo)志。(2)該頂點(diǎn)進(jìn)隊(duì)(ii)取下一個(gè)鄰接頂點(diǎn)(c)轉(zhuǎn)④⑤若隊(duì)列空，則處理過程結(jié)束。二求圖的連通分量求無向圖的連通分量是圖的遍歷的一種應(yīng)用。若無向圖是不連通的，則從V出發(fā)遍歷圖不能訪問該圖的所有頂點(diǎn)，只能訪問包含V的極大連通子圖（連通分量）中的所有結(jié)點(diǎn)。若從無向圖的每個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)遍歷圖，則可求得無向圖的所有連通分量。借助dfs和bfs可求得圖中的所有連通分量第四節(jié):生成樹和最?。ù鷥r(jià)）生成樹生成樹：若G是一個(gè)連通無向圖，若G’是包含G中所有頂點(diǎn)的一個(gè)無回路的連通子圖，則稱G’為G的一棵生成樹。具有n個(gè)頂點(diǎn)的連通無向圖至少有n-1條邊，而生成樹恰好有n-1條邊，在生成樹中，任意添加一條邊，則會(huì)形成回路。用dfs和bfs生成的生成樹若G是無向的連通圖，頂點(diǎn)表示城市，邊表示城市之間的通信線路，若有n個(gè)城市，至少要有n-1條線路，則G的生成樹表示了這n個(gè)城市之間可行的通信線路。若G是帶權(quán)的連通無向圖，那么可用頂點(diǎn)表示城市，而邊上的權(quán)表示兩個(gè)城市之間的距離，在n個(gè)城市間最多可建造n(n-1)/2條線路，選擇其中的n-1條線路，使其總的代價(jià)最小。這就是最小代價(jià)生成樹的概念。帶權(quán)連通無向圖G的最小代價(jià)生成樹是G的所有生成樹中邊上的權(quán)之和最小的一棵生成樹。一Prim算法已經(jīng)G=（V，E），是一個(gè)帶權(quán)連通無向圖，頂點(diǎn)V={1，2，……n}，為V中構(gòu)成最小代價(jià)生成樹的頂點(diǎn)集合，初始時(shí)V={V0}，V0∈V，T為構(gòu)成最小代價(jià)生成樹邊的集合，初始時(shí)T為空，若邊（u，v）具有最小代價(jià)，且u∈V，v∈V-U,那么最小代價(jià)生成樹包含（u，v），即把u加到U中，把（u，v）加入T中，這個(gè)過程一直進(jìn)行下去，直到U=V時(shí)為止。這時(shí)T即成為最小代價(jià)生成樹。生成步驟：（1）設(shè)T是帶權(quán)無向圖G的最小代價(jià)生成樹，初始時(shí)T=NOLL，U為最小代價(jià)生成樹的頂點(diǎn)集合。初始時(shí)U={V0}，V0是指定的某一頂點(diǎn)。（2）若U=V，則算法終止；否則，從E中選一條代價(jià)最小的邊（u,v），使得u∈U,v∈V-U,將頂點(diǎn)v加到U中，并將（u,v）加到T中，轉(zhuǎn)(2)二Kruskal算法給出一種按權(quán)值的遞增次序選擇合適邊來構(gòu)造最?。ù鷥r(jià)）生成樹的方法：已知圖G=（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖，設(shè)T是G的最小代價(jià)生成樹，初始時(shí)T=（V，φ）中，即T有n個(gè)連通分量構(gòu)成，每個(gè)連通分量只有一個(gè)頂點(diǎn)，沒有邊。首先把E中的邊按代價(jià)（即權(quán)）的遞增次序進(jìn)行排序，然后按排序的順序選取邊。即反復(fù)執(zhí)行下面的選擇步驟。這樣的過程一直進(jìn)行到包含有（n-1）條邊為止，算法結(jié)束。這時(shí)的T便是我們所求的最小代價(jià)生成樹。選擇步驟：若當(dāng)前被選擇的邊的兩個(gè)頂點(diǎn)在不同的連通分量中，則把這條邊加到T中，選取這樣的邊可以保證不會(huì)構(gòu)成回路。第七節(jié)最短路徑帶權(quán)的有向圖表示交通網(wǎng)絡(luò)城市u和城市v之間１．有無公路可通２．在有n條公路的情況下，那一條路最短帶權(quán)有向圖,假定權(quán)總是正的(wij>=0),稱路徑的開始頂點(diǎn)為源點(diǎn),稱路徑的最后頂點(diǎn)為終點(diǎn)。路徑的長(zhǎng)度是該路徑各邊之和。求解路徑的兩個(gè)算法。（１）求從某個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。（２）求每一對(duì)頂點(diǎn)之間的最短路徑。求某個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。V是圖G的指定源點(diǎn)，找出從V到其他頂點(diǎn)的最短路徑。Dijkstra算法:S表示已求出最短路徑頂點(diǎn)的集合（第一組）其余頂點(diǎn)作為另一個(gè)頂點(diǎn)集合（第二組）按最短路徑長(zhǎng)度的遞增次序逐個(gè)地把第二組的頂點(diǎn)加入到S中，直到從V出發(fā)可以到達(dá)的所有頂點(diǎn)都在S中，在這處過程中，始終保持從V到S中各頂點(diǎn)的最短路徑長(zhǎng)度都不得大于從V到第二組的任何頂點(diǎn)的最短路徑長(zhǎng)度。另外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離：S中的頂點(diǎn)的距離是從V到此頂點(diǎn)的最短路徑長(zhǎng)度，第二組頂點(diǎn)的距離是從V到此頂點(diǎn)的只包括S中頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。點(diǎn)對(duì)應(yīng)一個(gè)距離：S中的頂點(diǎn)的距離是從V到此頂點(diǎn)的最短路徑長(zhǎng)度，第二組頂點(diǎn)的距離是從V到此頂點(diǎn)的只包括S中頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。具體做法：初始時(shí)S={V}，即S中包含源點(diǎn)V，V的距離為零，第二組包括其他所有頂點(diǎn)而這一組的頂點(diǎn)距離為：若圖中有邊<V,W>，則W的距離就是這條邊的權(quán)；否則W的距離為一個(gè)很大的數(shù)。然后，從第二組的頂點(diǎn)中選取一個(gè)距離最小的頂點(diǎn)K，把K加入S中，每次加入一個(gè)頂點(diǎn)到S中后，就要對(duì)第二組的各個(gè)頂點(diǎn)的距離進(jìn)行一次修改。若加進(jìn)頂點(diǎn)K做中間結(jié)點(diǎn)，從頂點(diǎn)V到頂點(diǎn)j(j€V-S)的距離比原來不經(jīng)過K的距離短，則修改頂點(diǎn)J的距離值。修改后，再選區(qū)距離最小的頂點(diǎn)加入S中，并對(duì)V-S中的頂點(diǎn)的距離進(jìn)行修改，這樣的過程連續(xù)進(jìn)行下去，直至G中所有頂點(diǎn)都包含在S中，或再也沒有可加入的頂點(diǎn)存在。n個(gè)頂點(diǎn)的帶權(quán)有向圖，用鄰接矩陣cost表示G從源點(diǎn)V到其他頂點(diǎn)的最短路徑：把頂點(diǎn)V放在集合S中按如下步驟逐個(gè)求得從V到其他頂點(diǎn)的最短路徑，直至把所有頂點(diǎn)的最短路徑都求出為止。選取不在S中，且具有最小距離的頂點(diǎn)K把頂點(diǎn)K加入到集合S中修改不在S中的頂點(diǎn)的距離二求每一對(duì)頂點(diǎn)之間的最短路徑方法1：依次把帶權(quán)有向圖中n個(gè)頂點(diǎn)作為源點(diǎn)，執(zhí)行前面的方法n次，就可得到每對(duì)頂點(diǎn)之間的最短路徑。方法2：（Floyd方法）產(chǎn)生一個(gè)矩陣序列A（0）A（1）A（2）……A(n)其中A（0）為給定的代價(jià)鄰接矩陣，A（K）（i,j）(1<=i,j<=n)表示從頂點(diǎn)i到頂點(diǎn)j的中間頂點(diǎn)序號(hào)不大于k的最短路徑長(zhǎng)度。若從i到j(luò)的路徑?jīng)]有中間頂點(diǎn)，則對(duì)于1<=k<=n，有A(K)(i,j)=A(0)(i,j)=cost(i,j),遞推地產(chǎn)生A（0）A（1）A（2）……A(n)的過程就是逐步允許越來越多的頂點(diǎn)作為路徑的中間頂點(diǎn)，直至找到所有允許作為中間頂點(diǎn)的頂點(diǎn)，算法結(jié)束，最短路徑就全求出。設(shè)A（k-1）（i，j）（1<=i,j<=n）,這時(shí)，A（k）（i，j）由如下兩種情況求出。(1)若從頂點(diǎn)i到頂點(diǎn)j最短路徑不經(jīng)過頂點(diǎn)k，那么由A（k）（i，j）的定義可知從i到j(luò)的中間頂點(diǎn)序號(hào)不大于k的最短路徑長(zhǎng)度就是A（K-1）（i，j）(2)若從頂點(diǎn)i到頂點(diǎn)j的最短路徑經(jīng)過頂點(diǎn)k，那么這一條路徑由i到k和由k到j(luò)所組成，若A（k-1）（i，k）+A（k-1）（k，j）<A（K-1）（i，j）則A（k-1）（i，j）+A（k-1）（k，j）必定是從i到j(luò)的中間頂點(diǎn)序號(hào)不大于k的最短路徑長(zhǎng)度，即A(K)（i，j）=A（K-1）（i，k）+A（k-1）（k，j）從頂點(diǎn)1到頂點(diǎn)2的最短路徑為<1，3，2>，其長(zhǎng)度為7。從頂點(diǎn)1到頂點(diǎn)3的最短路徑為<1，3>，其長(zhǎng)度為5從頂點(diǎn)2到頂點(diǎn)1的最短路徑為記<2，1>，其長(zhǎng)度為4。從頂點(diǎn)Z到頂點(diǎn)3的最短路徑為<2，1，3>，其長(zhǎng)度為9。從頂點(diǎn)3到頂點(diǎn)1的最短路徑為<3，2，1>，其長(zhǎng)度為6。從頂點(diǎn)3到頂點(diǎn)2的最短路徑為<3，2>，其長(zhǎng)度為2 第六節(jié):拓?fù)渑判蛟O(shè)S是一個(gè)集合，K是S上的一個(gè)關(guān)系，a,b是S中的元素，若（a,b）€K，則a是b關(guān)于K前趨元素，b是a的后繼元素設(shè)S是一個(gè)集合，K是S上的一個(gè)關(guān)系，a,bc是S中的元素，若（a,b）€K,(b,c)€K，則必有（a,c）€K，那么稱K是S上的一個(gè)傳遞關(guān)系。若對(duì)于S的任一元素a，不存在（a,a）€k，則稱K是S上的一個(gè)非自反關(guān)系，若S上的一個(gè)關(guān)系K是傳遞的和非自反的，則稱K是S上的一個(gè)半序關(guān)系，在任何一個(gè)具有半序關(guān)系K的有限集合中，至少有一個(gè)元素沒有前趨，也至少有一個(gè)元素沒有后繼。若K是集合S上的一個(gè)半序關(guān)系，A=a1,a2,……an是S中元素的一個(gè)序列，且當(dāng)（ai,aj）€k時(shí)，有I<j，則稱A是相對(duì)于K的一個(gè)拓?fù)湫蛄小Ｗ⒁猓篴i和aj關(guān)于K毫無關(guān)系，那么ai和aj

在A中的排序不受限制，稱獲得拓樸序列的過程為拓?fù)渑判?。有向圖G往往可以用來表示某工程的施工圖，或產(chǎn)品的生產(chǎn)流程圖，或某系統(tǒng)的執(zhí)行流程圖，有向邊則表示工程子項(xiàng)目，或子系統(tǒng)之間的先后關(guān)系。在一個(gè)有向圖中，若用頂點(diǎn)表示活動(dòng)或任務(wù)，用邊表示活動(dòng)（任務(wù)）之間的先后關(guān)系則稱此有向圖為ＡＯＶ網(wǎng)絡(luò)（用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)ActivityonVertexnetwork）拓?fù)湫蛄校海?，２，３，４，６，５，７或：１，３，２，５，６，４，７具有回路的有向圖的頂點(diǎn)不能排成拓?fù)湫蛄腥魏螞]有回路的有向圖，其頂點(diǎn)可以排成一個(gè)拓?fù)湫蛄兴惴?1）在網(wǎng)絡(luò)中選一個(gè)沒有前趨的頂點(diǎn)，且把它輸出(2)從網(wǎng)絡(luò)中刪除該頂點(diǎn)和以它為尾的所有有向邊工程不可行工程可行重復(fù)(1)(2)直到所有的頂點(diǎn)都被輸出，或者直到遺留在網(wǎng)絡(luò)上的頂點(diǎn)都有前趨通過檢查頂點(diǎn)的入度進(jìn)行。工程可行工程不可行第七節(jié)關(guān)鍵路徑在帶權(quán)的有向圖中，頂點(diǎn)表示事件（狀態(tài)），有向邊表示活動(dòng)，權(quán)表示活動(dòng)所天的時(shí)間，ＡＯＥ－網(wǎng)絡(luò)（有邊表示活動(dòng)的網(wǎng)絡(luò)，ActivityonedgeNetwork）尾頂點(diǎn)表示活動(dòng)可以開始的狀態(tài)頭頂點(diǎn)表示活動(dòng)已經(jīng)完成的狀態(tài)開始活動(dòng)完成關(guān)鍵路徑：１，２，４，５，７，９或：１，３，４，５，８，９關(guān)心的問題：完成整個(gè)工程至少需要多少時(shí)間：哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？由于ＡＯＥ－網(wǎng)絡(luò)中某些活動(dòng)可以并行地進(jìn)行，所以完成工程的最小時(shí)間是從開始頂點(diǎn)到結(jié)束頂點(diǎn)的最長(zhǎng)路徑長(zhǎng)度。在這里，路徑的長(zhǎng)度等于完成這條路徑上各個(gè)活動(dòng)所需時(shí)間之和，稱從開始頂點(diǎn)到結(jié)束頂點(diǎn)之間的最長(zhǎng)路徑為關(guān)鍵路徑。關(guān)鍵路徑上的所有活動(dòng)稱為關(guān)鍵活動(dòng)。事件Ｖi能夠發(fā)生的最早時(shí)間ee[i]是從開始頂點(diǎn)１到頂點(diǎn)I的最長(zhǎng)路徑長(zhǎng)度。事件Ｖi允許的最遲發(fā)生時(shí)間le[i]等于ee[n]減去頂點(diǎn)i到頂點(diǎn)n的最長(zhǎng)路徑長(zhǎng)度。若活動(dòng)ai是由邊<j,k>表示的，那么ai的最早開始時(shí)間e[i]等于從開始頂點(diǎn)１到表示Ｖj的頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度：即e[i]=ee[j]活動(dòng)ai允許的最遲開始時(shí)間L[j]等于le[k]-ai所需的時(shí)間稱e[I]=l[I]的活動(dòng)為關(guān)鍵活動(dòng),若ai拖延時(shí)間，則整個(gè)工程要拖延時(shí)間。L[i]-e[i]為活動(dòng)ai的最大可利用時(shí)間，它是在不增加完成工程所需時(shí)間的情況下，活動(dòng)ai

可以拖延時(shí)間L[I]-e[I]>0即使提早完成任務(wù)（L[I]-e[I]天）也不能加快整個(gè)工程進(jìn)度，但若提早完成時(shí)間>L[I]-e[I],則關(guān)鍵路徑可能會(huì)發(fā)生變化。Ee[k]和le[k]在向前階段在向后階段算法：輸入E條弧<j,k>建立AOE的存貯結(jié)構(gòu)。從源點(diǎn)V1出發(fā)令ee[1]=0，按拓?fù)浯涡蚯笃溆喔黜旤c(diǎn)的ee[i]從終點(diǎn)Vn出發(fā)令Le[n]=ee[n]，按拓?fù)淠嫘蚯笃溆喔黜旤c(diǎn)的最遲開始時(shí)間Le[i]根據(jù)各頂點(diǎn)的eeel值求每條弧的最早開始時(shí)間e[i]和最遲開始時(shí)間L[i]。若某條弧滿足條件e[I]=L[I]則為關(guān)鍵活動(dòng)。習(xí)題7．1對(duì)于圖題7．1的無向圖，給出：（1）表示該圖的鄰接矩陣。（2）表示該圖的鄰接表。（3）圖中每個(gè)頂點(diǎn)的度。7．2對(duì)于圖題7．1的無向圖，給出：（1）從頂點(diǎn)1出發(fā)，按深度優(yōu)先搜索法遍（2）從頂點(diǎn)1出發(fā)，按廣度優(yōu)先搜索法遍歷圖時(shí)所得到的頂點(diǎn)序列。7．3對(duì)于圖題7．3的有向圖，給出：（1）表示該圖的鄰接矩陣。(2)表示該圖的鄰接表。（3）圖中每個(gè)頂點(diǎn)的入度和出度。7．4對(duì)于圖題7．3的有向圖，給出：（1）從頂點(diǎn)1出發(fā)，按深度優(yōu)先搜索法遍歷圖時(shí)所得到的頂點(diǎn)序列。（2）從頂點(diǎn)1出發(fā)，按廣度優(yōu)先搜索法遍歷圖時(shí)所得到的頂點(diǎn)序列。7．5對(duì)于圖題7．1的無向圖，試問它是（1）連通圖嗎？（2）完全圖嗎？7．6對(duì)于圖題7．3的有向圖，試問它是（1）弱連通圖嗎？（2）強(qiáng)連通圖嗎？7．7圖題7