數(shù)據(jù)結(jié)構第七章

1、1第七章 圖地圖染色北京公交查詢系統(tǒng)鋪設線路電網(wǎng)輸電模擬導游系統(tǒng) V5 V01006030102010550 V1 V2 V3 V42第七章 圖圖的定義圖的存儲結(jié)構圖的遍歷圖的應用最小生成樹最短路徑拓撲排序關鍵路徑 V5 V01006030102010550 V1 V2 V3 V43 圖圖是由一個是由一個頂點集頂點集 V 和一個和一個弧集弧集 R構成構成的數(shù)據(jù)結(jié)構。的數(shù)據(jù)結(jié)構。 Graph = (V, R )其中，VR| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱 v 為弧尾弧尾，w 為弧頭弧頭。4 由于“弧”是有方向的，因此稱由頂點集和弧集構成的圖為有向圖有向圖。EACB

2、D例如例如: :G = (V，VR)其中V=A, B, C, D, EVR=, , , , , , 5若VR 必有VR, 則稱頂點v 和頂點w 之間存在一條邊，用邊，用(v,w)表示。BCAFED由頂點集和邊集構成的圖稱作無向無向圖圖。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) 6ABECDAEDBBC設圖G=(V,VR) 和圖 G=(V,VR),且 VV, VRVR,則稱 G 為 G 的子子圖圖。1597211132 弧或邊帶權的圖分別稱作有向有向網(wǎng)網(wǎng)

3、或無向網(wǎng)無向網(wǎng)。7假設圖中有 n 個頂點，e 條邊，則 含有 e=n(n-1)/2 條邊的無向圖稱作完全圖完全圖; 含有 e=n(n-1) 條弧的有向圖稱作 有向完全圖有向完全圖; 若邊或弧的個數(shù) enlogn，則稱作稀疏圖稀疏圖，否則稱作稠密圖稠密圖。8 假若頂點v 和頂點w 之間存在一條邊，則稱頂點v 和w 互為鄰接點鄰接點，例如例如: :D(B) = 3D(A) = 2 邊(v,w) 和頂點v 和w 相關聯(lián)關聯(lián)。頂點頂點v的度：的度：與頂點與頂點v v相相關聯(lián)的邊的數(shù)目邊的數(shù)目。ACDFEB右側(cè)圖中9頂點的出度出度: : 以頂點v 為弧尾的弧的數(shù)目;ABECD對對有向圖有向圖來說來說，頂

4、點的入度入度: : 以頂點v為弧頭的弧的數(shù)目頂點的度度( (D)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1D(B) = 3由于弧有方向性，則有入度入度和出度出度之分10設圖G=(V,VR)中的一個頂點序列 u=vi0,vi1, , vim=w中，(vi,j-1,vi,j)VR 1jm,則稱從頂點u 到頂點w 之間存在一條路徑路徑。路徑上邊的數(shù)目稱作路徑長度路徑長度。ABECD如如:從A到D長度為 3 的路徑A,B,C,D簡單路徑簡單路徑:指序列中頂點不重復出現(xiàn)的路徑。簡單回路簡單回路:指序列中第一個頂點和最后一個頂點相同的路徑。1

5、1若圖G中任意兩個頂點之間都有路徑相通，稱此圖為連通圖連通圖若無向圖為非連通圖，則圖中各個極大極大的連連通通子圖子圖稱作此圖的連連通分量通分量。BACDFEBACDFE12 若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖強連通圖。ABECDABECD對有向圖，對有向圖，否則，其各個強連通子圖稱作它的強連通分量強連通分量BCDAE13BACDFE 假設一個連通圖連通圖有 n 個頂點和 e 條邊，其中n-1 條邊和n 個頂點構成一個極小連極小連通子圖通子圖，稱該極小連通子圖為此連通圖的生成樹生成樹。對非連通圖非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林生成森林。B

6、ACDFEBACDFEBACDFE14一一. 圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示二二. 圖的鄰接表存儲表示圖的鄰接表存儲表示三三. 有向圖的十字鏈表存儲表示有向圖的十字鏈表存儲表示 四四. 無向圖的鄰接多重表存儲表示無向圖的鄰接多重表存儲表示五五. 邊集數(shù)組表示邊集數(shù)組表示15用來表示圖中用來表示圖中頂點間頂點間相鄰關系相鄰關系的矩陣的矩陣網(wǎng)的鄰接矩陣如何表示？網(wǎng)的鄰接矩陣如何表示？Aij=0 (vi ,vj)VR1 (vi ,vj)VRAij= (vi ,vj)VRwij (vi ,vj)VRBACDFE01234501001010001100010100100111000

7、0011100 鄰接矩陣的定義鄰接矩陣的定義16ABECD1597211132有向圖的鄰接矩陣有向圖的鄰接矩陣有向網(wǎng)的鄰接矩陣有向網(wǎng)的鄰接矩陣ABECD012340 1 0 0 10 0 1 0 00 0 0 1 0110 0 00 0 1 0 0 15 9 3 211 7 21 171) 當圖的各頂點的序號確定后，其鄰接矩陣是唯一確定的；2) 無向圖和無向網(wǎng)的鄰接矩陣是一個對稱矩陣；3) 無向圖的鄰接矩陣中第i行(或第i列)的非零元個數(shù)為第i個頂點的度； 鄰接矩陣的性質(zhì)鄰接矩陣的性質(zhì)4)有向圖的鄰接矩陣中第i行非零元個數(shù)為第i個頂點的出度，第i列非零元個數(shù)為第i個頂點的入度；5) 無向圖的邊

8、數(shù)等于矩陣中非零元個數(shù)的一半，有向圖的弧數(shù)等于矩陣中非零元的個數(shù)。1() njD ViA ji1() njD ViA ij或18圖圖的鄰接矩陣的的鄰接矩陣的C語言描述語言描述#define VNUM /圖中頂點的最大數(shù)目圖中頂點的最大數(shù)目typedef struct VertexType vexsVNUM； / 定義頂點定義頂點 int arcsVNUMVNUM； / 定義邊（弧定義邊（?。?int vexnum, arcnum; / 頂點數(shù)，弧數(shù)頂點數(shù)，弧數(shù) Graph ；/定義圖定義圖網(wǎng)網(wǎng)的鄰接矩陣的的鄰接矩陣的C語言描述語言描述#define VNUM /圖中頂點的最大數(shù)目圖中頂點的最大

9、數(shù)目typedef struct VertexType vexsVNUM； / 定義頂點定義頂點 WeightType arcsVNUMVNUM； int vexnum, arcnum; / 定義邊的權值定義邊的權值 NetGraph ； /定義網(wǎng)定義網(wǎng)頂點的信息頂點的信息：用一維數(shù)組一維數(shù)組來存儲。邊的信息邊的信息： 用鄰接矩陣鄰接矩陣來存儲。 圖的圖的鄰接矩陣鄰接矩陣存儲方式存儲方式19例：已知一個無向圖，建立其存儲結(jié)構。例：已知一個無向圖，建立其存儲結(jié)構。void crt_gragh(Gragh &ga ) scanf(&ga.vexnum，&ga.arcnum)

10、；/頂點數(shù)和邊數(shù)頂點數(shù)和邊數(shù) for(i=0；iga.vexnum；i+) scanf(&ga.vexsi)； for(i=0；iga.vexnum；i+) for(j=0；jga.vexnum；j+ ) ga.arcsij=0； for(k=0；k arcnum ；k+) scanf(&i，&j)； / 讀入一條邊讀入一條邊 ga.arcsi-1j-1=1； ga.arcsj-1i-1=1 /crt_gragh 20已知一個有向網(wǎng)，建立其存儲結(jié)構已知一個有向網(wǎng)，建立其存儲結(jié)構。void crt_net(NetGraph &ga) scanf(&ga.v

11、exnum，&ga.arcnum)；/ 頂點數(shù)和弧數(shù)頂點數(shù)和弧數(shù) for(i=0；iga.vexnum；i+) scanf(ga.vexsi)； for(i=0；iga.vexnum；i+) for(j=0；jga.vexnum；j+ ) ga.arcsij= MAXINT； for(k=0；kga.arcnum；k+) scanf(&i，&j，&w)； / 讀入一條弧和弧上的權值讀入一條弧和弧上的權值 ga.arcsi-1j-1= w ； /crt_net 21 鄰接矩陣的特點鄰接矩陣的特點(1) 鄰接矩陣可以采用壓縮存儲方法鄰接矩陣可以采用壓縮存儲方法 無向

12、圖和無向網(wǎng)的鄰接矩陣為對稱矩陣;對于邊(弧)個數(shù)較少的稀疏圖,其鄰接矩陣也稀疏，用行主序存儲矩陣時存儲空間利用率低。(2) 操作特點操作特點 其存儲特點是一種順序存儲結(jié)構。其存儲特點是一種順序存儲結(jié)構。 較為適合操作有：較為適合操作有： 計算頂點的度；求一個頂點的所有鄰接點；插入或刪除一條邊(弧)等； 不太適合的操作有：不太適合的操作有： 頂點的插入和刪除；圖的遍歷等。22方法：方法： 對圖中對圖中每個頂點每個頂點建立一個有建立一個有鄰接關系鄰接關系的頂點的頂點單鏈表單鏈表 頂點鄰接表頂點鄰接表； (2) 用一個用一個數(shù)組數(shù)組存各鄰接表的頭結(jié)點存各鄰接表的頭結(jié)點(頂點結(jié)點頂點結(jié)點) 對于無向圖

13、無向圖：第 i 個鏈表是與Vi相鄰接的所有鄰接點構成的單鏈表； 對于有向圖有向圖：第 i 個鏈表是以Vi為弧尾的所有弧頭結(jié)點構成的單鏈表； data firstarc頂點的結(jié)點頂點的結(jié)點頂點信息頂點信息 頭指針頭指針adjvex nextarc info鄰接表結(jié)點鄰接表結(jié)點( (邊結(jié)點邊結(jié)點) )鄰接點編號鄰接點編號 指針指針 邊的權值邊的權值23typedef struct ArcNode int adjvex； / 該弧所指向的頂點的位置 struct ArcNode *nextarc； / 指向下一條弧的指針 InfoType info； / 該弧相關信息 ArcNode ，*ArcPo

14、inter；鄰接表的組織：鄰接表的組織：typedef struct VertexType vexdata；/頂點信息頂點信息 ArcPointer firstarc；/出邊頭指針，指向第一條出邊出邊頭指針，指向第一條出邊 VexNode；typedef struct VexNode adjlistVnum； / 鄰接表 int vexnum，arcnum；/有向圖的當前頂點數(shù)和弧數(shù) AdjGraph24vexdata firstarc頂點結(jié)點無向圖的鄰接表無向圖的鄰接表 adjvex nextarc弧結(jié)點BACDFE012345102030405060704 1012345ABCDEF35

15、25 01 123 045 無向無向網(wǎng)網(wǎng)的鄰接表的鄰接表 adjvex info nextarc已知圖的鄰接表，如何求無向圖中的頂點vi的度?無向圖中邊的個數(shù)？1 104 30 4 505 20 0 103 605 40 2 403 70 1 200 301 50 2 605 70 25A B C D E 012340 1 2 3 4 A B C D E3 30 2 0 有向圖的鄰接表有向圖的鄰接表有向圖的有向圖的逆逆鄰接表鄰接表如何求有向圖中弧的個數(shù)?如何求有向圖中頂點vi的出度和入度？1 4230 1241 ABECD0123426有向圖的鄰接表：有向圖的鄰接表：0 1 2 3 4 A B

16、 C D E1 4230 12ABECD01234如何生成有向圖的鄰如何生成有向圖的鄰接表結(jié)構？接表結(jié)構？讀入圖的信息：讀入圖的信息：頂點信息頂點信息：A B C D E弧弧(或邊邊)的信息: 例如例如：0，10，41，22，33，03，14，227建立有向圖的鄰接表的算法：建立有向圖的鄰接表的算法：void build_adjlist(AdjGraph &gb) scanf(&gb.vexnum， &gb.arcnum)；/頂點個數(shù)和弧數(shù)頂點個數(shù)和弧數(shù) for(i=0；igb.vexnum；i+) scanf(gb.adjlisti.verdata)； gb.adjl

17、isti.firstarc= NULL； for(k=0；k gb.arcnum ；k+) scanf(&i，&j)； / 讀入一對頂點序號讀入一對頂點序號 p=(ArcPointer)malloc(sizeof(ArcNode)； padjver =j； / 生成結(jié)點生成結(jié)點 pnextarc= gb.adjlisti.firstarc； gb.adjlisti.firstarc = p； / build_adjlist 問：如何建立無向問：如何建立無向圖的鄰接表？圖的鄰接表？281) 圖的鄰接表的表示不是唯一的，它與鄰接點的讀入順序有關；2) 無向圖鄰接表中第i個單鏈表中結(jié)

18、點個數(shù)為第i個頂點的度；3) 有向圖鄰接表中第i個單鏈表中結(jié)點個數(shù)為第i個頂點的出度；其逆鄰接表中第i個單鏈表中結(jié)點個數(shù)為第i個頂點的入度； 鄰接表的性質(zhì)鄰接表的性質(zhì)4) 無向圖的邊數(shù)為鄰接表中結(jié)點個數(shù)的一半，有向圖的弧數(shù)為鄰接表中結(jié)點個數(shù)。29 鄰接表的特點鄰接表的特點 存儲特點：存儲特點： 是一種順序是一種順序+ +鏈式的存儲結(jié)構，鏈式的存儲結(jié)構，當圖中頂點個數(shù)較多，而邊比較少時，可節(jié)省大量的空間。較為適合操作有：較為適合操作有： 計算頂點Vi的出度；求一個頂點的所有鄰接點；插入或刪除一條邊(弧)；求頂點的一個鄰接點的下一個鄰接點等；不太適合的操作有：不太適合的操作有： 頂點的插入和刪除；

19、頂點的入度等。30鏈表結(jié)點鏈表結(jié)點邊起點 邊終點邊終點 下一入邊入邊指針 下一出邊出邊指針弧的權值tailvex headvexhlinktlinkinfo是有向圖有向圖的鄰接表和逆鄰接表結(jié)合結(jié)合起來得到的一種鏈表。表頭結(jié)點表頭結(jié)點頂點信息 入邊頭指針入邊頭指針 出邊頭指針datafirstinfirstout31typedef struct VexNode / 定義頂點定義頂點(頭頭)結(jié)點結(jié)點 VertexType data； ArcNode *firstin，*firstout； VexNode；typedef struct ArcBox / 定義定義弧弧結(jié)點結(jié)點 int tailvex，

20、 headvex； struct ArcBox *hlink， *tlink； InfoType info； ArcNode；十字鏈表的組織：十字鏈表的組織：32#define Vnum 20typedef struct VexNode ortholistVnum； /頂點(表頭)結(jié)點數(shù)組 int vexnum，arcnum； /有向圖的當前頂點數(shù)和弧數(shù) OlGraph；有向圖的結(jié)構表示有向圖的結(jié)構表示(十字鏈表十字鏈表)33ABC2 02 10 20 1弧頭相同弧頭相同012讀入?。?(0,1)、(0,2)、(2,0)、(2,1)弧尾相同弧尾相同 tailvex headvex hlink

21、tlink弧結(jié)點弧結(jié)點data firstin firstout頂點結(jié)點頂點結(jié)點ABC01234ivex ilink jvex jlink邊結(jié)點邊結(jié)點 ilink：指示下一條依附于頂點ivex的邊。 jlink：指示下一條依附于頂點jvex的邊。 data： 存儲和該頂點相關的信息。 firstedge：指示第一條依附于該頂點的邊 data firstedge頂點結(jié)點頂點結(jié)點354 12 42 32 10 30 1 例：對于無向圖，例：對于無向圖，讀入順序如下讀入順序如下邊結(jié)點邊結(jié)點:0 V01 V1 2 V2 3 V3 4 V4V0V1V2V3V4(0,1)；(0,3)；(2,1)；(2,3

22、)；(2,4)；(4,1)。ivex ilink jvex jlink36typedef struct ENode int ivex，jvex； / 頂點序號頂點序號 struct enode *ilink，*jlink； ENode；typedef struct VNode DataType data； / 頂點信息頂點信息 ENode *firstedge；/ 指向第一條依附于該頂點的邊結(jié)點指向第一條依附于該頂點的邊結(jié)點 VNode； / 定義頭結(jié)點定義頭結(jié)點 typedef struct VNode adjmulistVnum； int vexnum，edgenum； / 圖的當前頂點數(shù)

23、和邊數(shù)圖的當前頂點數(shù)和邊數(shù) AMLGrahp； 37方法：方法：用一個一維數(shù)組存儲頂點信息；用一個一維數(shù)組存儲頂點信息；用一個一維數(shù)組存圖中所有的邊用一個一維數(shù)組存圖中所有的邊, 數(shù)組規(guī)模數(shù)組規(guī)模圖邊數(shù)；圖邊數(shù)；每個數(shù)組元素存一條邊的起點、終點、權值，次序任意每個數(shù)組元素存一條邊的起點、終點、權值，次序任意 無向圖，邊起點可以任意選定；無向圖，邊起點可以任意選定；無權圖，省去權值存儲無權圖，省去權值存儲 邊集數(shù)組邊集數(shù)組: 12 3bacA12 3BC12 1646123112起點起點.233終點終點.1234起點起點1123終點終點2332權值權值121646適合：適合：對邊依次處理的運算對

24、邊依次處理的運算38遍歷：遍歷：從某頂點出發(fā), 按一定搜索方法,不重復訪問所有頂點。367984125問題：問題：可能存在多條路徑都能到達同一頂可能存在多條路徑都能到達同一頂點。點。即要解決頂點的重復訪問。解決辦法：解決辦法：對已訪問過的頂點做標記。設輔助數(shù)組: int visitedn；來記錄每個頂點是否被訪問過。訪問過為1，否則為0。397.3.1 連通圖的深度優(yōu)先搜索連通圖的深度優(yōu)先搜索(Depth-First Search) 訪問頂點的次序： V3V2 V4V9V1V6 V5V8V7深度優(yōu)先遍歷：深度優(yōu)先遍歷： 訪問出發(fā)點V0； 任選一個出發(fā)點的一個沒被訪問過的鄰接點，以該點出發(fā)深度優(yōu)

25、先遍歷深度優(yōu)先遍歷； 重復，直到V0沒有鄰接點沒被訪問；36798412540連通圖的深度優(yōu)先遍歷的連通圖的深度優(yōu)先遍歷的邏輯算法邏輯算法：void df_traver(gragh g，int v) /從從v號頂點出發(fā)，深度優(yōu)先遍歷連通圖號頂點出發(fā)，深度優(yōu)先遍歷連通圖 g printf(v)； visitedv=1；for(w=FirstAdjVex(g, v); w; w=NextAdjVex(g, v, w) if(visitedw=0) df_traver(g，w)； / dfs 41typedef struct ArcNode int adjvex； / 該弧所指向的頂點的位置 str

26、uct ArcNode *nextarc； / 指向下一條弧的指針 ArcNode ，*ArcPointer；鄰接表的組織：鄰接表的組織：typedef struct VertexType vexdata；/頂點信息頂點信息 ArcPointer firstarc；/出邊頭指針，指向第一條出邊出邊頭指針，指向第一條出邊 VexNode；typedef struct VexNode adjlistVnum； / 鄰接表 int vexnum，arcnum；/有向圖的當前頂點數(shù)和弧數(shù) AdjGraph42 void df_traver (AdjGraph g，int v)/g的存儲結(jié)構為鄰接表的存

27、儲結(jié)構為鄰接表，v為出發(fā)點編號，標志數(shù)組已初始化為為出發(fā)點編號，標志數(shù)組已初始化為0 printf(g.adjlistv.vexdata)； / 訪問出發(fā)點訪問出發(fā)點 visitedv= 1； / 做標志做標志 p=g.adjlistv.firstarc； / 找鄰接點找鄰接點 while (pNULL) w = padjvex； if (visitedw=0) df_traver (g，w)；/ 遞歸調(diào)用遞歸調(diào)用 p=pnextarc； / 找下一個鄰接點找下一個鄰接點 /dfs 43 從圖中的某個頂點V0出發(fā)，訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次

28、序依次訪問它們的鄰接點。7.3.2連通圖的廣度優(yōu)先搜索連通圖的廣度優(yōu)先搜索(Breadth-First Search) 一層一層二層二層三層三層訪問頂點的次序： V3V2V1V6V4V5V9V8V736798412544顯然，先被訪問的頂點，其鄰接點也先被訪問. 實現(xiàn)時需要設置一個隊列隊列，用于記住訪問頂點的次序：367984125算法：算法： 1. 將初始頂點號入隊；將初始頂點號入隊；2. 隊列不空，則隊列不空，則 隊頭頂點號出隊,訪問訪問； 依次將其鄰接頂點號入隊；3.重復重復2，直到隊列空，直到隊列空，遍歷過程結(jié)束。45鄰接表結(jié)構下連通圖的廣義優(yōu)先遍歷算法：鄰接表結(jié)構下連通圖的廣義優(yōu)先遍

29、歷算法：void bf_traver (AdjGraph g，int v0) / 隊列隊列Q存放已訪問過的頂點編號，存放已訪問過的頂點編號，v0為出發(fā)點編號為出發(fā)點編號 InitQueue(Q)； EnQueue(Q，v0)； while (!Qempty(Q) ) v=OutQueue(Q)； printf(g.adjlistv.vexdata)； visitedv=1； p=g.adjlistv.firstarc； while (p NULL) w=padjvex； / 取鄰接點編號取鄰接點編號 if (visitedw=0) InQueue(Q，w) ； p = pnextarc ； /

30、bfs 46void traver(gragh g) for(v=0；vn；v+) visitedv=0； for(v=0；vn；v+) if (visitedv=0) df_traver(g, v)； /或或bf_travers(g, v) 從圖中的某個頂點V0出發(fā)深度（廣度）優(yōu)先深度（廣度）優(yōu)先遍歷，遍歷，之后另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。7.3.3 非連通圖的深度非連通圖的深度( (廣度）優(yōu)先遍歷：廣度）優(yōu)先遍歷：47 假設要在 n 個城市之間建立通訊聯(lián)絡網(wǎng)，則連通 n 個城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)費的前如何在最節(jié)省

31、經(jīng)費的前提下建立提下建立這個通訊網(wǎng)通訊網(wǎng)？問題：問題：48圖G中的邊集合E(G)分成兩個部分:T(G)與與G中中所有頂點所有頂點構成構成G的極小連通子圖，的極小連通子圖，即是即是G的一棵的一棵生成樹生成樹。深度優(yōu)先生成樹B(G)：剩余的邊集。T(G)：遍歷過程中經(jīng)過的邊集遍歷過程中經(jīng)過的邊集生成樹生成樹367984125367984125廣度優(yōu)先生成樹49已知一個帶權圖，求其生成樹，使得樹中所有邊上的權值之和最小權值之和最小。 0 1 3 2 4 5 651536642最常用的算法： 普里姆普里姆(prim)算法算法 卡魯斯卡爾卡魯斯卡爾(kruskal)算法算法5014231534250V-

32、UU1. 普里姆普里姆(prim)算法算法 設G=(V, E)是連通圖，最小生成樹T的頂點集合為U，邊的集合是TE。首先：首先：U =u0 (u0 V) ， TE = 重復執(zhí)行下述操作：重復執(zhí)行下述操作： 在所有u U， v V-U的邊(u，v) E中找一條代價最小的邊(ui ，v0)并入集合TE，同時v0并入U，直到 U = V為止。 51abcdegf195141827168213127例如例如: :aedcbgf148531621所得生成樹權值和= 14+8+3+5+16+21 = 6752帶權圖帶權圖(網(wǎng)網(wǎng))用鄰用鄰接矩陣表示接矩陣表示。struct VertexType adjvex

33、； / U集中的頂點 WeightType lowcost; / 邊的權值 closedgeVNUM； 最小生成樹用一個結(jié)構數(shù)組數(shù)組(closedge)表表示示，數(shù)組下標表示圖中的頂點序號；對當前VU集中的每個頂點，記錄和頂點集U中頂點相連接的代價最小的邊：typedef struct VertexType vexsVNUM; WeightType arcsVNUMVNUM;int vexnum, arcnum; NetGraph ；53 0123456 0 1 2 3 4 5 6closedge0123456AdjvexLowcost a b c d e f gabcdegf19514182

34、7168213127aedcbaaa19141814e12ee8168d3dd7213c5 51621gf 19 14 1819 5 7 12 5 3 7 3 8 21 14 12 8 16 21 2718 16 27 0162453G.arcsij:a b c d e f g0 1 2 3 4 5 6G.vexsi:54void MiniSpanTree_P(NetGraph G, VertexType u) /帶權的連通圖G的存儲結(jié)構為鄰接矩陣NetGraph， /用普里姆算法從頂點u出發(fā)構造網(wǎng)G的最小生成樹 k=LocateVex (G, u); /確定起點u在圖G中的位置 for (j

35、=0; jG.vexnum; j+) / 輔助數(shù)組初始化 if (jk) closedgej. adjvex = u; closedgej. lowcost= G.arcskj ; closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; i+) 55 k = minimum(closedge); / 求出加入生成樹的下一個頂點(k) printf(closedgek.adjvex, G.vexsk， closedgek.lowcost ); / 輸出生成樹上一條邊 closedgek.lowcost = 0; /第k頂點并入U集 for(j=0;

36、 jG.vexnum; +j) /修改其它頂點的最小邊 if (G.arcskj closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej. lowcost =G.arcskj; /MiniSpanTree_P56設設G=（V， E )是連通圖是連通圖 將邊從小到大排序；將邊從小到大排序； 將將n個頂點分成個頂點分成n棵樹；棵樹； 選最小的一條邊（選最小的一條邊（u，v)，滿，滿足足u，v不在同一連通集不在同一連通集 重復，選夠重復，選夠n-1條邊停止；條邊停止；（0，2）=1 （1，2）=5（3，5）=2 （2，3）=5（1，4）=3

37、（0，1）=6（2，5）=4 （2，4）=6（0，3）=5 （4，5）=6 0 1 3 2 4 5 651536642 X X二、二、克克魯斯卡爾魯斯卡爾(kruskal)算法算法12025314525123457普里姆算法普里姆算法 克魯斯卡爾算法克魯斯卡爾算法時間復雜度時間復雜度O(n2)O(eloge)稠密圖稠密圖稀疏圖稀疏圖算法名算法名適應范圍適應范圍比較兩種算法58給定有向圖G=(V, E)，G中E上的權值為W(e)；設源點的編號為v0， G的存儲結(jié)構為鄰接矩陣鄰接矩陣。 WeightType netNN； V5 V01006030102010550 V1 V2 V3 V4 10 3

38、0 100 5 50 10 20 60 netij=存儲存儲結(jié)構結(jié)構:59Dijkstra算法：算法： 按路徑長度按路徑長度遞增遞增的次序產(chǎn)生最短路徑。的次序產(chǎn)生最短路徑。 如源點到其它每一個頂點都有一條最短路徑： ( v0， ， v1) ( v0， ， v2) ( v0， ， vn) 在上面的路徑中，先求最短的，再求次短的，。首先將網(wǎng)中的所有頂點分成兩個集合首先將網(wǎng)中的所有頂點分成兩個集合S和和T：S：凡以v0為源點，已經(jīng)確定了最短路徑的終點并入集合S。S的初始狀態(tài)只包含v0。T：尚未確定最短路徑的頂點的集合。其初始狀態(tài)包含除源點外的所有頂點。60引進兩個輔助數(shù)組來記源點(設其編號為v0)到

39、其它頂點的最短路徑長度路徑長度和路徑集合路徑集合。 disti：表示v0到頂點vi的最短路徑的長度。 pathi: 表示以上路徑中所經(jīng)過的頂點集合其初始狀態(tài)為： disti = netv0i ； pathi= v0, i，當E ，否則 初始時S=v0，以后不斷地修改以后不斷地修改S和和disti：設第一條最短路徑為(v0，vj):則 distj=min disti |viT，此時 S=v0，j61假設下一條次短路徑的終點是vk，則這條路徑或者是(v0，vk)， 或者是(v0，vj，vk)。所以有必要修改v0號頂點到除j號頂點以外其它頂點的距離，即修改disti(iT)disti=minnetv

40、0i，distj+netjijS,iT重復執(zhí)行下述操作，直到選夠重復執(zhí)行下述操作，直到選夠n-1條路徑：條路徑：（1）設下一條所選路徑的終點為vk ，則：distk= mindistiiT，將k加入到S中。（2）修改disti iTdisti=mindisti，distk+netkikS，iT 62 v1 v2 v3 v4 v5 入選入選S的點的點disti 10 30 100pathi (v0,v2) (v0,v4) (v0,v5) 10 30 100 5 50 10 20 60 netij=從從v0出發(fā)出發(fā) 10(v0,v2)disti / 60 30 100 pathi (v0,v2,v

41、3)disti / 50 / 90pathi (v0,v4,v3) (v0,v4,v5) disti / / / 60pathi (v0,v4,v3,v5) 30(v0,v4) 50(v0,v4,v3) 60(v0,v4,v3,v5)v2v4v3v5 V5 V01006030102010550 V1 V2 V3 V463存儲結(jié)構：存儲結(jié)構：Adjmatrix netnn； 存儲有向網(wǎng)的鄰接矩陣。WeightType distn； disti: 存儲v0到vi的路徑長度。int insetn；若vi在頂點集合S中，則inseti=1，否則inseti=0；初始時：insetv0=1，其它為0。i

42、nt pathnn；二維數(shù)組二維數(shù)組； pathi是一維數(shù)組，存儲源點v0到各頂點vi的最短路徑，若若pathik=1，表示，表示vk在該路徑中。在該路徑中。0 0 0 0 0 00 0 0 0 0 01 0 1 0 0 01 0 0 1 1 01 0 0 0 1 01 0 0 1 1 10 1 2 3 4 5p0p1p2p3p4p564void shortpath(Adjmatrix net， int v0， WeightType &distn，int &pathnn) for (i=0；in；i+) / dist、inset、path初始化初始化 disti= netv0i

43、； inseti=0； /所有頂點都不在所有頂點都不在S中中 pathi0.n-1=0；/所有所有pathi為空路徑為空路徑 if(distiMAXINT) pathiv0=1；pathii=1； /如果如果disti ,讓讓pathi=v0，vi ； / 初始化完成初始化完成 insetv0=1；/初始化集合初始化集合S=v065for(k=0；kn；k+) / 構造至多構造至多n-1條路徑條路徑 min= MAXINT； j=v0； / 初始化一個最短路徑長初始化一個最短路徑長 for(i=0；in；i+) /找入選點及找入選點及min值值 if(inseti=0 & distim

44、in) j=i； min=distj ；/min=mindisti, iT if(jv0) insetj=1；/ S=S+j for(i=0；in；i+) / 修改修改disti, iT if( inseti=0 & (distj+netjidisti) disti=distj + netji； pathi0.n-1= pathj0.n-1； pathii=1； / pathi=pathj+i / end_for k /shortpath T(n)= O(n2)66一個解決辦法是：每次以一個頂點為源點，重復執(zhí)行dijkstra算法n次。 T(n) = O(n3)另一算法：另一算法：由F

45、loyd提出, T(n) = O(n3)，但形式較簡單形式較簡單存儲結(jié)構仍使用鄰接矩陣存儲結(jié)構仍使用鄰接矩陣net。為了描述簡單，設頂點的編號從1n；鄰接矩陣數(shù)組的下標也從1n。67若存在，則存在路徑vi,vj / 路徑中不含其它頂點若,存在，則存在路徑vi,v1,vj / 路徑中所含頂點序號不大于1若vi,v2, v2,vj存在， 則存在一條路徑vi, , v2, vj / 路徑中所含頂點序號不大于2 依次類推，則 vi 至 vj 的最短路徑應是上述這些路徑中，路徑長度最小者。68設二維數(shù)組設二維數(shù)組A來存儲任一對頂點的最短路徑長度，來存儲任一對頂點的最短路徑長度，開始時，開始時，Aij的值

46、取的值取netij的值的值。 將A記為A(0) 。要進行要進行n次試探次試探。(1)對每一條路徑，先考慮讓路徑經(jīng)過頂點v1，比較路徑和+ 的長度，取其短者為當前求得的最短路徑長度，記為A(1)。稱為中間點序號不大于中間點序號不大于1的最短路徑(2)在A(1)的基礎上讓路徑經(jīng)過頂點v2，可求得A(2) 稱為中間點序號不大于中間點序號不大于2的最短路徑。 (n)在A(n-1)的基礎上讓路徑經(jīng)過頂點vn，可求得A(n) 69序列序列A(k)ij（k=1，2，n)的求法：的求法：假設已知A(k-1)ij，分兩種情況： 頂點vi到頂點vj的最短路徑不通過中間點中間點vk， 則: A(k)ij= A(k-

47、1)ij (2) 頂點vi到頂點vj的最短路徑經(jīng)過中間點中間點vk ， 則: 該路徑由 + 組成，此時應修改A(k)ij為 A(k-1)ik + A(k-1)kj A(0)ij = netij A(k)ij=minA(k-1)ij，A(k-1)ik+A(k-1)kj其中：A(i)ij= A(i-1)ij；A(j)ij=A(j-1)ij； A(k)ii = A(0)ii（k=1，2，n)70A(0) = 1 4 9 2 3 5 8 6 A(3)= 1 10 3 12 9 2 3 4 6 9 10 6 A(2)= 1 10 3 9 2 3 4 6 6 A(4)= 1 9 3 11 8 2 3 4

48、6 9 10 6 A(1)= 1 4 9 2 3 4 7 6 31954862例： v3 v4 v1 v271void floyd(AdjMatrix net，PathMatrix &path ，DistancMatrix &a)/i和和j之間的最短路徑為之間的最短路徑為pij，最短路徑長為，最短路徑長為aij；若；若/pijk為為TRUE，則，則k是從是從i到到j當前求得最短路徑上的頂點當前求得最短路徑上的頂點for(i=0；in；i+) for(j=0；jn；j+) aij= netij； for(k=0；kn；k+)pijk=FALSE； if (aijMAXINT) p

49、athiji=TRUE；pathjkk=TRUE； 72for (k=0；kn；k+) for (i=0；in；i+) for (j=0；jn；j+) if (aik+akjaij) aij=aik+akj； for (t=0；tn；t+) / pathi,j=pathi,k+pathk,jpjkt=pjit | pjkt； / floyd 73有向無環(huán)圖有向無環(huán)圖(directed acycline graph)：以有向圖表示一個工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。a1a10a4a7a8a2a5a3a11a6a974一一. .拓撲排序問題的提出拓撲排序問題的提出 在現(xiàn)實世界中

50、,一項大的工程通常有若干個子工程構成，這些子工程和主工程的關系可以用有向圖來描述。子工程稱為活動(Activity)，活動之間經(jīng)常存在先后的次序關系。a1a10a4a7a8a2a5a3a11a6a975 在一個有向圖中如果用頂點表示活動頂點表示活動，用弧表示活動間優(yōu)先關系弧表示活動間優(yōu)先關系，該圖稱為用頂點表示活動的網(wǎng) (Activity On Vertex Network) ， 簡稱AOV_網(wǎng)。網(wǎng)。i是j的前驅(qū)前驅(qū)，j是i的后繼后繼； i是k的直接前直接前驅(qū)驅(qū)，k是i的直接后繼直接后繼。 i k j 二二. AOV_網(wǎng)網(wǎng)76三三. 拓撲序列的定義拓撲序列的定義 設圖G是一個具有n個頂點的有向

51、圖，包含圖G的所有n個頂點的一個序列：Vi1,Vi2,Vin，當滿足下面條件時該序列稱為G的一個拓撲序列拓撲序列：當在圖G中，從頂點Vi到頂點Vj有一條路徑時，在序列中Vi必須排在Vj的前面。構造拓撲序列的過程稱為構造拓撲序列的過程稱為拓撲排序拓撲排序。77例如：在如下的AOV_網(wǎng)中：序列：v1v3v2v4v5v6v7 是一個拓撲序列；序列：v2v1v3v5v4v7v6 也是一個拓撲序列；v3v1v2v4v5v6v7 程序設計程序設計 匯編匯編語言語言 信息技術信息技術 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構 編譯原理編譯原理 離散數(shù)學離散數(shù)學 操作系統(tǒng)操作系統(tǒng)78例如：對于下列有向圖BDAC可求得可求得拓撲有序序

52、列拓撲有序序列： A B C D 或或 A C B D對于下列有向圖：對于下列有向圖：BDAC不能求得它的拓撲不能求得它的拓撲有序序列。有序序列。存在一個回路存在一個回路 四四. .拓撲序列的特點拓撲序列的特點1) 一個有向圖的拓撲序列一般不唯一。一個有向圖的拓撲序列一般不唯一。2) 有向無環(huán)圖一定存在拓撲序列。有向無環(huán)圖一定存在拓撲序列。79五五. 拓撲排序的算法描述拓撲排序的算法描述如果頂點沒有全部輸出，且當前圖中不存在無前驅(qū)的頂點，則說明有向圖中存在環(huán)(1) 在有向圖中選一個沒有前驅(qū)的頂點且輸出；(2) 從圖中刪除該頂點以及以該頂點為弧尾的所有??； 重復上述兩步，直至全部頂點均已輸出。8

53、0V1V2V3V4V5V6V2V3V4V5V6V2V3V4V5例(a)輸出 V1(b) 輸出V6(c)輸出V4V2V3V5(d) 輸出V3V2V5 (e) 輸出V2或V5拓撲序列：拓撲序列：V1 V6 V4 V3 V2 V5V1 V6 V4 V3 V5 V2 V6 81鄰接表存儲結(jié)構中實現(xiàn)拓撲排序的算法鄰接表存儲結(jié)構中實現(xiàn)拓撲排序的算法可用可用加了入度域加了入度域(id)的頭結(jié)點的的頭結(jié)點的鄰接表鄰接表來存儲有向圖。來存儲有向圖?；〉淖x入順序如下弧的讀入順序如下(0，1) 、(0，2)、(0，3)、(2，1)、(2，4)、(3，2)、(3，4)、(5，3)、(5，4)用一個順序棧存放入度為用一

54、個順序棧存放入度為0的頂點序號。的頂點序號。 頂點頂點 入度入度 指針指針 0 V0 0 3 2 1 1 V1 2 2 V2 2 4 1 3 V3 2 4 2 4 V4 3 5 V5 0 4 3 V0V1V4V3V4V5821、邏輯算法：、邏輯算法： InitStack(s)； 將所有入度為零的頂點的棧 ； m = 0； / m記已輸出頂點的個數(shù)記已輸出頂點的個數(shù) while (!Empty(s) v= Pop(s)； printf(v)； m=m+1； w = FirstAdjvex(g，v)； while (w存在) 入度(w)=入度(w)-1； if (入度(w)= 0) push(s，

55、w)； w = NextAdjvex(g，v，w) if (mn) return ERROR；/ 該圖有回路該圖有回路 else return OK； 832、鄰接表結(jié)構下的算法：、鄰接表結(jié)構下的算法：typedef struct arcnode int adjvex； / 鄰接點位置鄰接點位置 struct arcnode *nextarc； /下一個弧結(jié)點指針下一個弧結(jié)點指針 ArcNode，*ArcPointer；typedef struct DataType vexdata ； / 頂點類型頂點類型 int id； / 入度入度 ArcPointer firstarc； / 頭指針頭指

56、針 VexNode；typedef struct VexNode adjlistVnum； / 鄰接表鄰接表 int vexnum，arcnum； /有向圖的當前頂點數(shù)和弧數(shù)有向圖的當前頂點數(shù)和弧數(shù) AdjGraph84status top_sort(AdjGraph g) InitStack(s)； m = 0； / 初始化順序棧初始化順序棧s for(i=0；ig.vexnum；i+)if(g.adjlisti.id=0) Push(s，i)； while (! Empty(s) v=Pop(s)； printf(g.adjlistv.vexdata)； m=m+1； p= g.adjli

57、stv.firstarc； while(pNULL) w = padjvex ； g.adjlistw.id-； if(g.adjlistw.id =0) Push(s，w)； p = pnextarc； if (mn) return ERROR；else return OK； / top_sort85 頂點頂點 入度入度 指針指針 0 V0 0 3 2 1 1 V1 2 2 V2 2 4 1 3 V3 2 4 2 4 V4 3 5 V5 0 4 3 先先輸出輸出 v5棧棧s 5 0按topsort算法得到的拓撲序列為：V5、V0、V3、V2、V1、V4。1201110003 2 41V0V1

58、V4V3V4V586 AOE_網(wǎng)(activity on edge)：在對工程進度進行管理時，往往用頂點表示往往用頂點表示事件事件，弧表示，弧表示活動活動，弧上的權表示活動持續(xù)的時間，這種網(wǎng)稱為AOE網(wǎng)。12a1=6a4=1a2=4a3=5a5=1a6=2a9=4a11=4a7=9a10=2a8=7源點源點匯點匯點968753487(1) 完成整項工程至少要花多少時間？完成整項工程至少要花多少時間？整個工程完成的時間為整個工程完成的時間為：從有向圖的：從有向圖的源點源點到到匯點匯點的最長路徑。的最長路徑。abcdefghk64521187244源點源點匯點匯點6174(2) 哪些活動是影響工程

59、進度的關鍵？哪些活動是影響工程進度的關鍵？關鍵路徑關鍵路徑：路徑長度最長最長的路徑。關鍵活動關鍵活動：關鍵路徑上的所有活動。88事件事件Vi的最早發(fā)生時間的最早發(fā)生時間：從源點源點到Vi的最長路徑長度最長路徑長度。ViV1 . . .l(i) - e(i): 完成活動完成活動ai的的余量余量。jkai 定義定義 當當e(i)=l(i)時，活動時，活動ai為為關鍵活動。關鍵活動。定義定義 e(i) 活動活動ai的的最早最早(early)開始時間。開始時間。 l(i) 活動活動ai的的最遲最遲(late)開始時間。開始時間。 也是也是以以Vi為尾的弧為尾的弧所表示的所表示的活動活動的的最早開始時間

60、最早開始時間 其中：ai 89可知Ve(j)是以Vj為弧尾的活動ai的最早開始時間 即: Ve(j)=e(i) weight() ：活動ai的持續(xù)時間。 “事件事件j(頂點頂點)” 的的 最早最早發(fā)生時間發(fā)生時間 Ve(j)Ve(j) = 從源點到頂點從源點到頂點j的的最長最長路徑長度路徑長度;“事件事件k(頂點頂點)” 的的 最遲最遲發(fā)生時間發(fā)生時間 Vl(k) Vl(k) = 從頂點從頂點k到匯點的到匯點的最短最短路徑長度路徑長度;jkweight第第i i項活動項活動aiVe(j)Vl(k)e(i)，l(i) 定義定義 90假設第 i 條弧為 “活動活動ai(弧弧)”的 最早開始時間 e(i) e(i) = Ve(j)；“活動活動ai(弧弧)”的 最遲開始時間 l(i) l(i) = Vl(k) weight() ；jkai 事件發(fā)生時間的計算公式