數(shù)據(jù)結(jié)構(gòu)(C語言描述)第7章-圖07課件

1、第7章 圖 理解圖的基本概念及有關(guān)術(shù)語，掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法； 熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、設(shè)計步驟，并能列出按上述兩種遍歷算法得到的序列； 理解最小生成樹的概念，能按Prim構(gòu)造最小生成樹； 領(lǐng)會求最短路徑、拓?fù)渑判蛞约瓣P(guān)鍵路徑的算法思想。學(xué)習(xí)要點(diǎn)7.1 圖的基本概念 圖是由一個頂點(diǎn)集 V和一個描述頂點(diǎn)之間關(guān)系（邊或者弧）的集合R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Graph = ( V , VR )其中，VR| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱 v 為弧尾或初始點(diǎn)，w 為弧頭或終端點(diǎn)。 謂詞 P(v,w)

2、定義了弧 的意義或信息。 圖的定義 圖的應(yīng)用舉例例1 交通圖（公路、鐵路） 頂點(diǎn)：地點(diǎn) 邊：連接地點(diǎn)的公路例2 電路圖 頂點(diǎn)：元件 邊：連接元件之間的線路例3 各種流程圖 如產(chǎn)品的生產(chǎn)流程圖 頂點(diǎn)：工序 邊：各道工序之間的順序關(guān)系 V0V4 V3V1V2 V0V2 V3V17.1.2 圖的術(shù)語G1=V1=v0, v1, v2, v3, v4 E1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4) V0V4 V3V1V2在圖中，若用箭頭標(biāo)明了邊是有方向性的，則稱這樣的圖為有向圖，否則稱為無向圖。在無向圖中，一條邊（x,y）與（y,x）表示的結(jié)果相同，

3、用圓括號表示。例如：在有向圖中，一條邊與表示的結(jié)果不相同，用尖括號表示。表示從頂點(diǎn)x出發(fā)向頂點(diǎn)y的邊，x為始點(diǎn)，y為終點(diǎn)。例如：G2=V2=v0, v1, v2, v3A2=, , , V0V2 V3V1 有向圖和無向圖 頂點(diǎn)、邊、弧、弧頭、弧尾VWVW圖中的數(shù)據(jù)元素通常稱為頂點(diǎn)； 若VR,則表示從v到w的一條弧，且稱v為弧尾或初始點(diǎn),稱w為弧頭或終端點(diǎn)。 若VR，必有則VR，即VR是對稱的，則以無序?qū)?v,w)代替這兩個有序?qū)?，表示從v和w的一條邊。 在一個無向圖中，如果任意兩頂點(diǎn)都有一條直接邊相連接，則稱該圖為無向完全圖。 在一個有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接,

4、則稱為有向完全圖。 若一個圖接近完全圖，稱為稠密圖；稱邊數(shù)很少的圖為稀疏圖。 有向完全圖無向完全圖312312 完全圖、稠密圖、稀疏圖7126543523641 度、入度、出度在圖中，一個頂點(diǎn)依附的邊或弧的數(shù)目，稱為該頂點(diǎn)的度。在有向圖中，以頂點(diǎn)V為起點(diǎn)的有向邊數(shù)稱為頂點(diǎn)V的出度，以頂點(diǎn)V為終點(diǎn)的有向邊數(shù)稱為頂點(diǎn)V的入度，入度和出度之和稱為該頂點(diǎn)的度。 邊的權(quán)、網(wǎng) 1254317632458BCA21435(a) 無向網(wǎng)(b)有向網(wǎng)與邊有關(guān)的數(shù)據(jù)信息稱為權(quán)。邊上帶權(quán)的圖稱為網(wǎng)。 路徑、路徑長度 V0V4 V3V1V2V0V1 無向圖中從頂點(diǎn)v到v的路徑是一個頂點(diǎn)序列(v=vi,0,vi,1,v

5、i,m=v)，其中(vi,j-1,vi,j)E(G) 。在有向圖中路徑也是有向的，它是由若干條弧組成。路徑上邊或弧的數(shù)目稱為路徑長度。 回路、簡單路徑、簡單回路 V0V4 V3V1V2 V0V2 V3V1無向圖G1有向圖G2起點(diǎn)和終點(diǎn)相同的路徑稱為回路或者環(huán)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除第一個頂點(diǎn)與最后一個頂點(diǎn)之外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡單回路。 子圖 V0V4 V3V1V2 V0V4 V3V1V2 V0 V3V1(a)(b)(c)若有兩個圖G和G，G=(V,E),G=(V,E )， 滿足如下條件：VV,EE，即V為V的子集, E為E的子集，稱圖G為圖G的子圖。例 (b)

6、、(c) 是 (a) 的子圖 連通圖、連通分量 V0 V4 V3 V1 V2 V0 V2 V3 V1 V5 V4連通圖G1非連通圖G2G2的兩個連通分量 在無向圖G中，如果從頂點(diǎn)v到頂點(diǎn)v有路徑，則稱v和v是連通的。若圖中任意兩個頂點(diǎn)都是連通的，則稱G為連通圖。無向圖中的極大連通子圖稱該圖的連通分量。 強(qiáng)連通圖、強(qiáng)連通分量 V0 V1 V2 V3 V0 V1 V2 V3強(qiáng)連通圖G1非強(qiáng)連通圖G2 V1 V0 V2 V3G2的兩個強(qiáng)連通分量在有向圖G中，如果對于任意一對頂點(diǎn)vj和vi 均有從一個頂點(diǎn)vj到另一個頂點(diǎn)vi有路徑，也有從vi到 vj的路徑，則稱該有向圖是強(qiáng)連通圖。 有向圖的極大強(qiáng)連通

7、子圖稱為強(qiáng)連通分量。 生成樹、生成森林 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2連通圖 G1G1的生成樹連通圖G的生成樹，是G的包含其全部n 個頂點(diǎn)的一個極小連通子圖。它必定包含且僅包含G的n-1條邊。 極小連通子圖意思是：該子圖是G 的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。非連通圖的生成樹則組成一個生成森林。若圖中有n個頂點(diǎn)，m個連通分量，則生成森林中有n-m條邊。圖是一種結(jié)構(gòu)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，表現(xiàn)在不僅各個頂點(diǎn)的度可以千差萬別，而且頂點(diǎn)之間的邏輯關(guān)系也錯綜復(fù)雜。從圖的定義可知，一個圖的信息包括兩部分，即圖中頂點(diǎn)的信息以及描述頂點(diǎn)之間

8、的關(guān)系（邊或者?。┑男畔?。因此無論采用什么方法建立圖的存儲結(jié)構(gòu)，都要完整、準(zhǔn)確地反映這兩方面的信息。圖通常有鄰接矩陣、鄰接表、鄰接多重表和十字鏈表等表示方法。7.2 圖的存儲結(jié)構(gòu) 7.2.1 鄰接矩陣 定義：在鄰接矩陣表示中，除了用一維數(shù)組存放頂點(diǎn)本身信息外，還用一個矩陣表示各個頂點(diǎn)之間的鄰接關(guān)系。這個矩陣稱為鄰接矩陣。假設(shè)圖G(V, E)有n個確定的頂點(diǎn)，即Vv0,v1, vn-1 ，則表示G中各頂點(diǎn)相鄰關(guān)系為一個nn的矩陣，矩陣的元素為 ：Aij= 1 若(vi,vj)或是E(G)中的邊 0 若(vi,vj)或不是E(G)中的邊 V0V1V2V30110000000011000A= 例 V

9、0V4V3V1V20101010101010111010001100B= 鄰接矩陣 V0V2V1V3V4856793436534648958797C= 若G是帶權(quán)圖，則鄰接矩陣定義為： wij 若(vi,vj)或是E(G)中的邊 若(vi,vj)或不是E(G)中的邊 其中wij表示邊上的權(quán)值；表示大于所有邊上權(quán)值的數(shù)。 Aij= 鄰接矩陣 從無向圖的鄰接矩陣可以得出如下結(jié)論：矩陣是對稱的；第i行或第i 列1的個數(shù)為頂點(diǎn)i 的度；矩陣中1的個數(shù)的一半為圖中邊的數(shù)目；很容易判斷頂點(diǎn)i和頂點(diǎn)j之間是否有邊相連(看矩陣中i行j列值是否為1)。 鄰接矩陣 從有向圖的鄰接矩陣可以得出如下結(jié)論：矩陣不一定是

10、對稱的；第i 行中1的個數(shù)為頂點(diǎn)i 的出度；第i列中1的個數(shù)為頂點(diǎn) i的入度；矩陣中1的個數(shù)為圖中弧的數(shù)目；很容易判斷頂點(diǎn)i和頂點(diǎn)j是否有弧相連。 鄰接矩陣 圖的鄰接矩陣數(shù)據(jù)類型描述：在用鄰接矩陣存儲圖時，除了用一個二維數(shù)組存儲用于表示頂點(diǎn)間相鄰關(guān)系的鄰接矩陣外,還需用一個一維數(shù)組來存儲頂點(diǎn)信息,另外還有圖的頂點(diǎn)數(shù)和邊數(shù)。故可將其形式描述如下：#define INFINITY 1000#define MAX_VERTEX_NUM 20簡化后的鄰接矩陣的存儲表示： 鄰接矩陣 7.2.2 鄰接表 鄰接表是圖的一種順序存儲與鏈?zhǔn)酱鎯Y(jié)合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。 就是對于圖G

11、中的每個頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)鏈成一個單鏈表，這個單鏈表就稱為頂點(diǎn)vi的鄰接表，再將所有的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。其中，單鏈表中的結(jié)點(diǎn)稱為表結(jié)點(diǎn)，每個單鏈表設(shè)的一個頭結(jié)點(diǎn)稱為頂點(diǎn)結(jié)點(diǎn)。 對圖中每個頂點(diǎn)Vi建立一個單鏈表，鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊，每個鏈表結(jié)點(diǎn)為兩個域：每個鏈表附設(shè)一個頭結(jié)點(diǎn)，頭結(jié)點(diǎn)結(jié)構(gòu)為：其中：頂點(diǎn)域data存放頂點(diǎn)信息； 表頭指針firstarc指向鏈表的第一個結(jié)點(diǎn)。頂點(diǎn)域表頭指針datafirstarc鄰接點(diǎn)域指針域adjvexnextarc 無向圖的鄰接表頂點(diǎn)：通常按編號順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲在一維數(shù)組中；與同一頂點(diǎn)關(guān)聯(lián)的邊：用線性鏈表存

12、儲特點(diǎn)：設(shè)無向圖中頂點(diǎn)數(shù)為n，邊數(shù)為e， 則它的鄰接表需要n個頭結(jié)點(diǎn)和2e個表結(jié)點(diǎn)。 頂點(diǎn)Vi的度 TD(Vi)=鏈表i中的表結(jié)點(diǎn)數(shù)。 V0V4V3V1V20V01V12V23V34V4213422110034下標(biāo) 編號 link返回n個頂點(diǎn),e條弧的有向圖,需n個表頭結(jié)點(diǎn),e個表結(jié)點(diǎn)。用鏈表存儲同一頂點(diǎn)為起點(diǎn)的弧 在有向圖中,第i個鏈表中的結(jié)點(diǎn)個數(shù)是頂點(diǎn)vi的出度。要求某個結(jié)點(diǎn)的入度，必須遍歷整個鄰接表。在所有鏈表中其鄰接點(diǎn)域的值為i的結(jié)點(diǎn)的個數(shù)是頂點(diǎn)vi的入度。 有向圖鄰接表 V0 V1 V2 V30V01V1 2V23V31230為了便于確定頂點(diǎn)的入度或以頂點(diǎn)vi為頭的弧，可以建立一個有

13、向圖的逆鄰接表，即對每個頂點(diǎn)vi建立一個以vi為頭的弧尾結(jié)點(diǎn)組成的鏈表。 用鏈表存儲同一頂點(diǎn)為起點(diǎn)的弧 有向圖的逆鄰接表 V0 V1 V2 V30V01V1 2V23V33002 結(jié)論 對于無向圖的鄰接表來說，一條邊對應(yīng)兩個單鏈 表結(jié)點(diǎn)，鄰接表結(jié)點(diǎn)總數(shù)是邊數(shù)的2倍。 在無向圖的鄰接表中，各頂點(diǎn)對應(yīng)的單鏈表的結(jié) 點(diǎn)數(shù)（不算表頭結(jié)點(diǎn)）就等于該頂點(diǎn)的度數(shù)。 在有向圖鄰接表中，一條弧對應(yīng)一個表結(jié)點(diǎn)，表 結(jié)點(diǎn)的數(shù)目和弧的數(shù)目相同。 在有向圖鄰接表中，單鏈表的結(jié)點(diǎn)數(shù)就等于相應(yīng) 頂點(diǎn)的出度數(shù)。 要求有向圖中某頂點(diǎn)的入度數(shù)，需掃視鄰接表的 所有單鏈表，統(tǒng)計與頂點(diǎn)標(biāo)號相應(yīng)的結(jié)點(diǎn)個數(shù)。 建立的鄰接表不是唯一的,與

14、鍵盤輸入邊的順序 有關(guān)，輸入的邊的順序不同，則得到的鏈表也不 同。 在鄰接表中容易找任一頂點(diǎn)的第一個鄰接點(diǎn)和下 一個鄰接點(diǎn)，但要判定任意兩頂點(diǎn)之間是否有邊 或弧，則需搜索第i個或第j個鏈表，不及鄰接矩 陣方便。 結(jié)論7.2.3 十字鏈表 十字鏈表是將有向圖的鄰接表和逆鄰接表結(jié)合起來的一種有向圖鏈?zhǔn)酱鎯Y(jié)構(gòu)。結(jié)點(diǎn)結(jié)構(gòu) 有向圖的每一條弧有一個弧結(jié)點(diǎn)，每一個頂點(diǎn)必有一個頂點(diǎn)結(jié)點(diǎn)，其結(jié)構(gòu)為： 弧結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)tailvexheadvexinfohlinktlinkdatafirstinfirstout建立有向圖的十字鏈表：void CreateDG(OLGraph *G) scanf(&G-vernum

15、,&G-arcnum); for(i=0;ivexnum;+i)scanf(&G-xlisti.data);G-xlisti.firstin=G-xlisti.firstout =NULL; for(k=0;kxlisti.firstout=G-xlistj.fisrtin=p; 7.2.4 鄰接多重表 鄰接多重表是無向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。每一個頂點(diǎn)有一個頂點(diǎn)結(jié)點(diǎn)，頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)為：圖的每一條邊有一個邊結(jié)點(diǎn)，邊結(jié)點(diǎn)的結(jié)構(gòu)為：datafirstedgeivexilinkjvexjlinkmark圖的鄰接多重表數(shù)據(jù)類型描述：#define MAX_VERTEX_NUM 20typedef emn

16、u unvisited,visited VisitIf;typedef struct EBoxVisitIf mark;int ivex,jvex;struct EBox ilink, jlink;EBox;typedef struct VexBoxVertexType data;EBox fistedge;VexBox;typedef structVexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;/*訪問標(biāo)記*/*該邊依附的兩個頂點(diǎn)的位置*/*指向依附這兩個頂點(diǎn)的下一條邊*/*指向第一條依附該頂點(diǎn)的邊*/*無向圖的當(dāng)前頂點(diǎn)數(shù)

17、和邊數(shù)*/7.3 圖的遍歷 和樹的遍歷類似，圖的遍歷也是從某個頂點(diǎn)出發(fā)，沿著某條搜索路徑對圖中所有頂點(diǎn)各作一次訪問。圖訪問的四個難點(diǎn)：首結(jié)點(diǎn) 、非連通圖 、回路、多個相連頂點(diǎn)我們可以設(shè)置一個全局型標(biāo)志數(shù)組visited來標(biāo)志某個頂點(diǎn)是否被訪過，未訪問的值為0，訪問過的值為1。根據(jù)搜索路徑的方向不同，圖的遍歷有兩種方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。深度優(yōu)先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪問過，在G中任選一個頂點(diǎn)v作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遍歷可定義如下： 7.3.1 深度優(yōu)先搜索首先訪問頂點(diǎn)v，并將其訪問標(biāo)記置為訪問過，即visitedv=TRUE ；然后搜

18、索與頂點(diǎn)v有邊相連的下一個頂點(diǎn)w，若w未被訪問過，則訪問它，并將w的訪問標(biāo)記置為訪問過，然后從w開始重復(fù)此過程；若w已訪問，再訪問與v有邊相連的其它頂點(diǎn)；若與v有邊相連的頂點(diǎn)都被訪問過，則退回到前一個訪問頂點(diǎn)并重復(fù)剛才過程，直到圖中所有頂點(diǎn)都被訪問完止。深度優(yōu)先搜索是一種遞歸的過程從圖中某頂點(diǎn)v出發(fā)： V0 V7 V6 V5 V4 V3 V2 V1訪問頂點(diǎn)v；依次從v的未被訪問的鄰接點(diǎn)出發(fā)，對圖進(jìn)行深度優(yōu)先遍歷；先序遍歷（DLR）若二叉樹非空訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹；深度優(yōu)先遍歷如果將圖頂點(diǎn)的鄰接點(diǎn)看作二叉樹結(jié)點(diǎn)的左、右孩子深度優(yōu)先遍歷與先序遍歷是不是很類似？深度遍歷：V1

19、V2 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5V6V1V2V4V5V3V7V8V1V2V4V5V3V7V6V8由于沒有規(guī)定訪問鄰接點(diǎn)的順序,深度優(yōu)先序列不是唯一的對某頂點(diǎn)的深度優(yōu)先遍歷的遞歸算法：Boolean visitedMAX;void DFSTraverse(Graph G,int v) for(v=0;vG.vexnum;+v) visitedv=FALSE;for(v=0;v=0;w=NextAdjVex(G,v,w)if (!visitedw)DFS (G,w);以v為起點(diǎn)對G進(jìn)行DFS搜索/訪問頂點(diǎn)v/對v的尚未訪問過的鄰 接點(diǎn)

20、w遞歸調(diào)用DFS在遍歷時，對圖中每個頂點(diǎn)至多調(diào)用一次DFS 函數(shù)，因?yàn)橐坏┠硞€頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。因此，遍歷圖的過程實(shí)質(zhì)上是對每個頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時間則取決于所采用的存儲結(jié)構(gòu)。深度優(yōu)先搜索的算法復(fù)雜度：廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問，在G 中任選一頂點(diǎn)v作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是：首先訪問頂點(diǎn)v，并將其訪問標(biāo)志置為已被訪問，即visitedv=TRUE ；接著依次訪問與頂點(diǎn)v有邊相連的所有頂點(diǎn)W1，W2，Wt；然后再按順序訪問與W1，W2，Wt有邊相連又未曾訪問過的頂點(diǎn)；依此類推，直到圖中所有頂點(diǎn)都被訪

21、問完為止 。 7.3.2 廣度優(yōu)先搜索即廣度優(yōu)先搜索遍歷圖的過程中以v為起始點(diǎn)，由近至遠(yuǎn)，依次訪問和v有路徑相通且路徑長度為1，2，的頂點(diǎn)。 V6V1V2V4V5V3V7V8 V0 V7 V6 V5 V4 V3 V2 V1V0 V1 V3 V2 V7 V6 V5 V4在遍歷過程中所經(jīng)過的路徑求圖G 的以V0起點(diǎn)的的廣度優(yōu)先序列： V0,V1,V2,V3,V4,V5,V6,V7由于沒有規(guī)定訪問鄰接點(diǎn)的順序,廣度優(yōu)先序列不是唯一的從圖中某頂點(diǎn)v出發(fā)：訪問頂點(diǎn)v ；(容易實(shí)現(xiàn))訪問v的所有未被訪問的鄰接點(diǎn)w1,w2,wk；(容易實(shí)現(xiàn))依次從這些鄰接點(diǎn)(在步驟2）訪問的頂點(diǎn))出發(fā)，訪問它們的所有未被訪

22、問的鄰接點(diǎn); 依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；為實(shí)現(xiàn) 3)，需要保存在步驟2）中訪問的頂點(diǎn)，而且訪問這些頂點(diǎn)鄰接點(diǎn)的順序?yàn)椋合缺４娴捻旤c(diǎn)，其鄰接點(diǎn)先被訪問。 V0 V7 V6 V5 V4 V3 V2 V1廣度優(yōu)先遍歷算法（類似于樹的按層遍歷）在廣度優(yōu)先遍歷算法中，需設(shè)置一隊(duì)列Q，保存已訪問的頂點(diǎn)，并控制遍歷頂點(diǎn)的順序。7.4 最小生成樹1、問題提出 要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)頂點(diǎn) 表示城市權(quán) 城市間建立通信線路所需花費(fèi)代價 希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價）最小最小代價生成樹1654327131791812752410最小生成樹1

23、6543271317918127524102、問題分析 n個城市間，最多可設(shè)置n(n-1)/2條線路； n個城市間建立通信網(wǎng)，只需n-1條線路； 問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把 所有城市（頂點(diǎn)）均連起來，且總耗費(fèi)（各邊權(quán)值之和）最小。3、定義 對于帶權(quán)的連通圖G，其生成樹也是帶權(quán)的。我們把生成樹各邊的權(quán)值總和稱為該生成樹的權(quán)。并且將權(quán)最小的生成樹稱為最小生成樹。Prim方法構(gòu)造過程V1V6V5V4V3V26513566425V1V31V1V6V314V1V6V4V3142V1V1V6V4V3V21425V1V6V5V4V3V214253Prim算法可用下述過程描述： （1）U

24、u1，T= ； （2）while （UV）do （u，v）minwuv；uU，vVU TT（u，v） UUv （3）結(jié)束。普里姆(Prim)算法輔助數(shù)組各分量值的變化：有關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)設(shè)置一個輔助數(shù)組closedge, 它包括兩個域：lowcost用來保存集合V-U中各頂點(diǎn)與集合U中各頂點(diǎn)構(gòu)成的邊中具有最小權(quán)值的邊的權(quán)值；adjvex用來保存依附于該邊的在集合U中的頂點(diǎn)。V1V6V5V4V3V26513566425 普里姆(Prim)算法void Prim(Mgraph G,VertexType u)k=LocateVex(G,u);for(j=0;kG.vexnum;+j)if(j!=k)

25、 closedgej=u,G.arcskj;closedgek.lowcost=0;for (i=1;iG.vexnum;+i)k=minmum(closedge);printf(closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for (j=0;jG.vexnum;+j)if (G.arcskjcolsedgej.lowcost)closedgej=G.vexsk,G.arcskj;輔助數(shù)組初始化初始U=u尋找當(dāng)前最小權(quán)值第k個頂點(diǎn)歸并到集合U新頂點(diǎn)并入U后重新選擇最小邊克魯斯卡爾(Kruskal)算法 初始條件：假設(shè)G = (V,E) 是一個具有n

26、個頂點(diǎn)的連通網(wǎng)絡(luò)， G=(U,T)是G 的最小生成樹，U的初值等于V，即包含有G中的全部頂點(diǎn)，T的初值為空集。 基本思想：將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊使生成樹G不形成環(huán)路，則把它并入T中，保留作為生成樹G的一條邊，若選取的邊使生成樹G形成環(huán)路，則將其舍棄，如此進(jìn)行下去，直到T中包含n-1條邊為止。此時的T即為最小生成樹。1654326513566425問題提出 用帶權(quán)的有向圖表示一個交通運(yùn)輸網(wǎng)，圖中： 頂點(diǎn)表示城市 邊表示城市間的交通聯(lián)系 權(quán)表示此線路的長度 問題：如何找到城市A到城市B之間一條距離最近的通路？ 數(shù)學(xué)模型：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中

27、，各邊上權(quán)值之和最小的一條路徑最短路徑7.5 最短路徑51643208562301371732913長度最短路徑8131921207.5.2 單源點(diǎn)最短路徑依最短路徑的長度遞增的次序求得各條路徑其中，從源點(diǎn)到頂點(diǎn)v的最短路徑是所有最短路徑中長度最短者。源點(diǎn)v1v2迪杰斯特拉算法 在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。 路徑長度最短的最短路徑的特點(diǎn)： 它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。下一條路徑長度次短的最短路徑的特點(diǎn)：其余最短路徑的特點(diǎn)： 它可能的情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是

28、從源點(diǎn)經(jīng)過頂點(diǎn)v1、v2 中的一點(diǎn)或兩點(diǎn)再到達(dá)該頂點(diǎn)(由多條弧組成) 。 它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。再下一條路徑長度次短的最短路徑的特點(diǎn):迪杰斯特拉算法求最短路徑的迪杰斯特拉算法： 設(shè)置輔助數(shù)組Dist，其中每個分量Distk 表示 當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。一般情況下，Distk = 或者 = + 。迪杰斯特拉算法1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的Distk值。假設(shè)求得最短路徑的頂點(diǎn)為w，若 Distw+G.arcswkDistk則將 Distk 改

29、為 Distw+G.arcswk。V0和Vi之間存在弧V0和Vi之間不存在弧其中的最小值即為最短路徑的長度。迪杰斯特拉算法1383032V2:813-133032V1:13-13302220V3:13-192220V4:19終點(diǎn) 從V0到各終點(diǎn)的最短路徑及其長度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329迪杰斯特拉算法頂點(diǎn)對之間的最短路徑概念 所有頂點(diǎn)對之間的最短路徑是指：對于給定的有向網(wǎng)G=(V,E),要對G中任意一對頂點(diǎn)有序?qū)、v(uv),找出u到v的最短距離和v到u的最短距離。解決此問題的一個有效方法是:輪流以每一個頂點(diǎn)為源點(diǎn),重復(fù)執(zhí)行迪杰

30、斯特拉算法n次,即可求得每一對頂點(diǎn)之間的最短路徑,總的時間復(fù)雜度為O(n3)。下面將介紹用弗洛伊德(Floyd)算法來實(shí)現(xiàn)此功能,時間復(fù)雜度仍為O(n3),但該方法比調(diào)用n次迪杰斯特拉方法更直觀一些。7.5.3 每一對頂點(diǎn)對之間的最短路徑頂點(diǎn)對之間的最短路徑概念 弗洛伊德算法使用前面定義的圖的鄰接矩陣G.arcsNN來存儲帶權(quán)有向圖。算法的基本思想是: 設(shè)置一個N*N的矩陣DNN，其中除對角線的元素都等于0外，其它元素Dij的值表示頂點(diǎn)i到頂點(diǎn)j的最短路徑長度，運(yùn)算步驟為： 開始時，以任意兩個頂點(diǎn)之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為，此時, Dij=G.arcsij, 以后

31、逐步嘗試在原路徑中加入其它頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為： 第一步，讓所有邊上加入中間頂點(diǎn)0，取Dij與Di0+D0j中較小的值作Dij的值. 第二步，讓所有邊上加入中間頂點(diǎn)1，取Dij與Di1+D1j中較小的值，完成后得到Dij ，如此進(jìn)行下去，當(dāng)?shù)趎步完成后，得到 Dij ,即為我們所求結(jié)果, Dij表示頂點(diǎn)i到頂點(diǎn)j的最短距離。因此，弗洛伊德算法可以描述為: D(-1)ij=G.arcsij; /G.arcs為圖的鄰接矩陣 D(k)ij=minD(k-1) ij, D(k-1) ik+D(k-1)

32、kj其中 k=0,1,2, n-1弗洛伊德算法311426BCA弗洛伊德算法7.6 有向無環(huán)圖及其應(yīng)用 一個無環(huán)的有向圖稱做有向無環(huán)圖，簡稱DAG圖。下面是有向樹、DAG圖和有向圖的例子。 有向樹 DAG圖 有向圖有向無環(huán)圖可以用來描述含有公共子式的表達(dá)式。例如下述表達(dá)式： (a+b)(b(c+d)+(c+d)e)(c+d)e) 二叉樹描述表達(dá)式 有向無環(huán)圖描述7.6.1 有向無環(huán)圖有向無環(huán)圖也是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具。對整個工程和系統(tǒng)，人們關(guān)心兩個方面的問題：一是工程能否順利進(jìn)行：二是估算整個工程完成所必須的最短時間。 下面我們通過對有向圖進(jìn)行拓?fù)渑判蚝完P(guān)鍵路徑操作來解決這兩

33、個問題。 有向無環(huán)圖的應(yīng)用在工程實(shí)踐中，一個工程項(xiàng)目往往由若干個子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系： 先后關(guān)系，即必須在一子項(xiàng)目完成后，才能開始實(shí)施另一個子項(xiàng)目； 子項(xiàng)目之間無次序要求，即兩個子項(xiàng)目可以同時進(jìn)行，互不影響。我們把這些子項(xiàng)目、工序、課程看成一個個頂點(diǎn)稱之為活動。這種用頂點(diǎn)表示活動、弧表示活動間優(yōu)先關(guān)系的有向無環(huán)圖稱為頂點(diǎn)表示活動的網(wǎng)(Activity On Vertex network )，簡稱AOV網(wǎng)。7.6.2 拓?fù)渑判蛉缦聢D存在環(huán)路，則表示頂點(diǎn)之間的先后關(guān)系進(jìn)入了死循環(huán)。如果用AOV網(wǎng)描述的是一項(xiàng)工程，那么這個AOV網(wǎng)一定不能存在環(huán)。因此，對給定的AOV網(wǎng)絡(luò)首先要判定網(wǎng)

34、絡(luò)中是否存在環(huán)路。V3V2V0V1在AOV網(wǎng)中，如果從頂點(diǎn)Vi到Vj之間存在有向邊,則表示活動i必須先于活動j進(jìn)行。如果頂點(diǎn)Vi到頂點(diǎn)Vj存在一條有向路徑時，稱Vi為Vj的前趨，Vj為Vi的后繼。這種前趨后繼關(guān)系有傳遞性。課程流程圖C1C2C3C4C5C6C7C8C9C10C11C12程序設(shè)計離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言算法分析計算機(jī)原理編譯方法操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)電子電路數(shù)值分析無 C1C1,C2C1C3,C4C11C5,C3C3,C6無C9C9C9,C10,C1課程編號 課程名稱 先決條件 C4C1C2C3C12C9C10C11C6C7C8C5所謂“拓?fù)渑判颉本褪菍OV網(wǎng)中的各個頂點(diǎn)(各

35、個活動)排列成一個線性有序序列，使得所有要求的前趨、后繼關(guān)系都能得到滿足。由于AOV網(wǎng)絡(luò)中有些頂點(diǎn)之間沒有次序要求，它們在拓?fù)溆行蛐蛄兄械奈恢每梢匀我忸嵉?，所以拓?fù)渑判虻慕Y(jié)果一般并不是唯一的。通過拓?fù)渑判蜻€可以判斷出此AOV網(wǎng)絡(luò)是否包含有有向環(huán)路，若有向圖G所有頂點(diǎn)都在拓?fù)渑判蛐蛄兄校瑒tAOV網(wǎng)絡(luò)必定不包含有有向環(huán)路。如上例，可以得到不止一個拓?fù)渑判颍篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8 顯然，對于任何一項(xiàng)工程中各個活動的安排，必須按拓?fù)溆行蛐蛄兄械捻樞蜻M(jìn)行才是可行的。 C4C

36、1C2C3C12C9C10C11C6C7C8C5對于給定的AOV網(wǎng)拓?fù)渑判虻牟襟E：任選一個入度為0的頂點(diǎn)輸出；刪除此頂點(diǎn)和以它為出發(fā)點(diǎn)的所有弧；重復(fù)執(zhí)行上述兩步，直至圖中無入度為0的頂點(diǎn)；若輸出頂點(diǎn)數(shù)小于圖中頂點(diǎn)數(shù)，則說明圖中存在環(huán)，無法產(chǎn)生其拓?fù)渑判?，否則輸出的頂點(diǎn)序列即為此圖的一個拓?fù)渑判?。拓?fù)渑判虻牟襟EV2V3V1V4V6V5V2V2V5V2V3V5V2V3V4V6V5V2V3V6V5輸出V1輸出V4輸出V6輸出V3輸出V5拓?fù)湫蛄袨椋篤1,V4,V6,V3,V5,V2AOV網(wǎng)上的輸出拓?fù)渑判蛩惴▽?shí)現(xiàn)firstarc 4 4 3 2adjvexnextarc14 1 3012345v1v

37、2v3v4v5v6dataV2V3V1V4V6V5Status Topo_Sort (AlGraph G)FindInDegree(G,indegree);InitStack(S);for (i=0;iverticesi.data);+count;for(p=G.verticesi.firstarc;p;p=p-nextarc) k=p-adjvex;if(!(-indegreek) Push(S,k); if(countG.vexnum) return ERROR;else return OK;void FindInDegree(ALGraph G,int indegreeMAX);for

38、(i=0;iG.vexnum;+i)indegreei=0;for (i=0;iadjvex+; p=p-nextarc; 初始化找以頂點(diǎn)i為起點(diǎn)的第一條弧將找到的以頂點(diǎn)i為起點(diǎn)的弧的入度加1找以頂點(diǎn)i為起點(diǎn)的下一條弧7.6.3 關(guān)鍵路徑1、什么是AOE網(wǎng)？ 如果在無環(huán)的帶權(quán)有向圖中, 用有向邊表示一個工程中的活動，用邊上權(quán)值表示活動持續(xù)時間, 用頂點(diǎn)表示事件(每個事件表示在它之前的活動已完成，在它之后的活動可以開始)，則這樣的有向圖叫做用邊表示活動的網(wǎng)絡(luò), 簡稱 AOE (Activity On Edges)網(wǎng)絡(luò)。 AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例 設(shè)一個工程有11項(xiàng)活動，9個事件事件V1表示整個工程開始事件V9表示整個工程結(jié)束整個工程只有一個開始點(diǎn)和一個完成點(diǎn)，在正常情況下，網(wǎng)中只一個入度為零的點(diǎn)（稱為源點(diǎn)）和一個出度為零的點(diǎn)（稱為匯點(diǎn)）。問題: (1) 完成整