第7章 圖和廣義表

1、12v 7.1 圖的定義圖的定義和術(shù)語和術(shù)語v 7.2 圖的存儲(chǔ)圖的存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)v 7.3 圖的遍歷圖的遍歷v 7.4 連通網(wǎng)的連通網(wǎng)的最小生成樹最小生成樹v 7.5 單源單源最短路徑最短路徑v 7.6 拓?fù)渑判蛲負(fù)渑判騰 7.7 關(guān)鍵路徑關(guān)鍵路徑v 7.8 廣義表廣義表34 圖圖Graph是由一個(gè)是由一個(gè)頂點(diǎn)集頂點(diǎn)集 V 和一個(gè)和一個(gè)弧集弧集 E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，記作構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，記作Graph = (V , E )。 其中，圖的頂點(diǎn)為數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，弧的集合E是定義在頂點(diǎn)集合V上的一個(gè)關(guān)系。有序?qū)?表示從 v 到 w 的一條弧，并稱 v 為弧頭弧頭，w 為弧尾弧尾。 謂詞 P(v,w

2、) 定義了弧 的意義或信息。圖圖的定義的定義:圖圖的類型定義的類型定義5 由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖有向圖。例如例如: :G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , A B C D E6若VR 必有VR, 則稱 (v,w) 為頂點(diǎn)v 和頂點(diǎn) w 之間存在一條邊邊。由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向圖無向圖。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=, , , , , , ABCDEF7名詞和術(shù)語名詞和術(shù)語網(wǎng)、子圖 完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑

3、、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹、生成森林8AEABBC設(shè)圖G=(V,VR) 和圖 G=(V,VR),且 VV, VRVR,則稱 G 為 G 的子圖子圖。ABECF1597211132 弧或邊帶權(quán)的圖分別稱作有向網(wǎng)有向網(wǎng)或無向網(wǎng)無向網(wǎng)。9 假設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則 含有 e=n(n-1)/2 條邊的無向圖稱作 完全圖完全圖； 含有 e=n(n-1) 條弧的有向圖稱作 有向完全圖有向完全圖； 若邊或弧的個(gè)數(shù) enlogn，則稱作稀疏圖稀疏圖，否則稱作稠密圖稠密圖。10 假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊，則稱頂點(diǎn)v 和w 互為鄰接點(diǎn)鄰接點(diǎn)，例如例如: :ID(

4、B) = 3ID(A) = 2 邊(v,w) 和頂點(diǎn)v 和w 相關(guān)聯(lián)關(guān)聯(lián)。 和頂點(diǎn)v 關(guān)聯(lián)的邊的數(shù)目邊的數(shù)目定義為邊的度度。ACDFEB11頂點(diǎn)的出度出度: : 以頂點(diǎn)v為弧尾的弧的數(shù)目；ABECF對(duì)有向圖來說對(duì)有向圖來說，頂點(diǎn)的入度入度: : 以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度度( (TD)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1TD(B) = 312設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑路徑。路徑上邊

5、的數(shù)目稱作路徑長(zhǎng)度路徑長(zhǎng)度。ABECF如如: :長(zhǎng)度為3的路徑A,B,C,F簡(jiǎn)單路徑簡(jiǎn)單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路簡(jiǎn)單回路:序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。13若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖連通圖；若無向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量連通分量。BACDFEBACDFE14對(duì)有向圖，對(duì)有向圖， 若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖強(qiáng)連通圖。ABECFABECF否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通強(qiáng)連通分量分量。15 假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n-1 條邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極

6、小連通子圖，稱該極小連通子圖為此連通圖的生成樹生成樹。 對(duì)非連通圖，則稱由各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林生成森林。BACDFE16結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問操作對(duì)頂點(diǎn)的訪問操作遍歷遍歷插入和刪除弧插入和刪除弧圖圖的基本操作：的基本操作：17CreatGraph(&G, V, VR): / 按定義(V, VR) 構(gòu)造圖DestroyGraph(&G): / 銷毀圖結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀18對(duì)頂點(diǎn)的訪問操作對(duì)頂點(diǎn)的訪問操作LocateVex(G, u); / 若G中存在頂點(diǎn)u，則返

7、回該頂點(diǎn)在 / 圖中“位置位置” ；否則返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 對(duì) v 賦值value。19對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作FirstAdjVex(G, v); / 返回 v 的“第一個(gè)鄰接點(diǎn)第一個(gè)鄰接點(diǎn)” 。若該頂點(diǎn)/在 G 中沒有鄰接點(diǎn)，則返回“空”。NextAdjVex(G, v, w); / 返回 v 的（相對(duì)于 w 的） “下一個(gè)鄰接下一個(gè)鄰接/ 點(diǎn)點(diǎn)”。若 w 是 v 的最后一個(gè)鄰接點(diǎn)，則/ 返回“空”。20插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)InsertVex(&G, v); /在圖G中增添

8、新頂點(diǎn)v。DeleteVex(&G, v); / 刪除G中頂點(diǎn)v及其相關(guān)的弧。21插入和刪除弧插入和刪除弧InsertArc(&G, v, w); / 在G中增添弧，若G是無向的， /則還增添對(duì)稱弧。DeleteArc(&G, v, w); /在G中刪除弧，若G是無向的， /則還刪除對(duì)稱弧。22遍遍 歷歷DFSTraverse(G, v, Visit(); /從頂點(diǎn)v起深度優(yōu)先深度優(yōu)先遍歷圖G，并對(duì)每/個(gè)頂點(diǎn)訪問一次且僅一次。BFSTraverse(G, v, Visit(); /從頂點(diǎn)v起廣度優(yōu)先廣度優(yōu)先遍歷圖G，并對(duì)每/個(gè)頂點(diǎn)訪問一次且僅一次。23一、圖的數(shù)組一、圖

9、的數(shù)組(鄰接矩陣鄰接矩陣)存儲(chǔ)表示存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示24Aij=0 (i,j)VR1 (i,j)VR一、圖的數(shù)組一、圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲(chǔ)表示存儲(chǔ)表示定義定義:矩陣的元素為矩陣的元素為BACDFE01234501001010001100010100100111000001110001234501234525 有向圖的鄰接矩有向圖的鄰接矩陣為非對(duì)稱矩陣陣為非對(duì)稱矩陣ABECF26typedef struct ArcCell / 弧的定義弧的定義 VRType adj; / VRType是頂點(diǎn)關(guān)系類型。 / 對(duì)無權(quán)圖，用1或0表示相鄰否； / 對(duì)

10、帶權(quán)圖，則為權(quán)值類型。 InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;27typedef struct VertexType / 頂點(diǎn)信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù) GraphKind kind; / 圖的種類標(biāo)志 MGraph;圖圖的結(jié)構(gòu)定義的結(jié)構(gòu)定義(鄰接矩陣鄰接矩陣)28二、圖的鄰接表二、圖的鄰接表 存儲(chǔ)表示存儲(chǔ)表示 0 A 1 4 1 B 0 4 5 2 C 3 5

11、 3 D 2 5 4 E 0 1 5 F 1 2 3BACDFE102345表結(jié)點(diǎn)之間無順序要求，由建圖時(shí)輸入的信息次序決定29有向圖的鄰接表有向圖的鄰接表1 4230 120 1 2 3 4 A B C D E可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。ABECF0123430有向圖的逆鄰接表有向圖的逆鄰接表A B C D E 303420 01234在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。ABECF0123431typedef struct ArcNode int adjvex; / 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc; / 指向下一

12、條弧的指針 InfoType *info; / 該弧相關(guān)信息的指針 ArcNode;adjvex nextarc info弧的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)32typedef struct VNode VertexType data; / 頂點(diǎn)信息 ArcNode *firstarc; / 指向第一條依附該頂點(diǎn)的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)33typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 圖的種類標(biāo)志 ALGraph;圖圖的結(jié)構(gòu)定義

13、的結(jié)構(gòu)定義(鄰接表鄰接表)34 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。一、深度優(yōu)先搜索一、深度優(yōu)先搜索二、廣度優(yōu)先搜索二、廣度優(yōu)先搜索三、遍歷應(yīng)用舉例三、遍歷應(yīng)用舉例35 從圖中某個(gè)頂點(diǎn)V0 出發(fā)，訪問此頂點(diǎn)，然后依次從依次從V0的各個(gè)未被訪問的的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。一、深度優(yōu)先搜索遍歷圖一、深度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷連通圖的深度優(yōu)先搜索遍歷36Vw1SG1SG2SG3 W1、W2 和 W3 均為 V 的鄰接點(diǎn)，SG1、SG2 和 SG

14、3 分別為含頂點(diǎn)W1、W2 和 W3的子圖。訪問頂點(diǎn) V ;for ( W1、W2、W3 ) 若該鄰接點(diǎn)W未被訪問， 則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。w2w3w2w371. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;解決的辦法是:為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問標(biāo)志訪問標(biāo)志” visitedw;2. 如何判別當(dāng)前的鄰接點(diǎn)W是否被訪問？w 如何知道鄰接點(diǎn)是否被訪問過？！38void DFS(Graph G, int v) / 從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for (w=FirstAdjVex(G, v); w!=0; w

15、=NextAdjVex(G,v,w) ) if (!visitedw) DFS(G, w); / 對(duì)v的尚未訪問的鄰接頂點(diǎn)w / 遞歸調(diào)用DFS / DFS39 首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷非連通圖的深度優(yōu)先搜索遍歷40void DFSTraverse(Graph G ) / 對(duì)圖 G 作深度優(yōu)先遍歷 for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標(biāo)志數(shù)組初始化 for (v=0; vw1, V-w2,

16、 V-w8 的路徑長(zhǎng)度為1；V-w7, V-w3, V-w5 的路徑長(zhǎng)度為2；V-w6, V-w4 的路徑長(zhǎng)度為3。w1Vw2w7w6w3w8w5w443 從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。44 void BFSTraverse(Graph G, int v) for (v=0; v

17、G.vexnum; +v) visitedv = FALSE; /初始化訪問標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; vnext = Q.rear-next = NULLvoid EnQueue( LinkQueue& Q, QelemType e ) p = new QNode; p-data = e; p-next = NULL; p-prior = Q.front; Q.rear-next = p; Q.rear = p;void DeQueue( LinkQueue& Q, QelemType& e ) Q.front = Q

18、.front-next; e = Q.front-data;573. 求迷宮的最短路徑求迷宮的最短路徑 以二維數(shù)組maze表示迷宮, 若mazeij的值可為1或0, 分別表示走通或受阻, 入口和出口設(shè)定是0。如果路徑存在, 一定可以找到一條最短的路徑（只需最少的步數(shù)步數(shù)走通）。58迷宮的最短路徑迷宮的最短路徑01234501234567101010000110010110011110011010010100101110110000maze59 如果把迷宮路徑作為一個(gè)有向圖看待, 求最短路徑可以從入口頂點(diǎn)開始做廣度優(yōu)先搜索, 試探的路徑向“四面八方”擴(kuò)散, 最先達(dá)到出口的路徑即為最短路徑。0 0

19、1 12 23 34 45 56 67 7搜索方向：搜索方向：6001234501234567101010000110010110011110011010010100101110110000廣度優(yōu)先搜索最短路徑（廣度優(yōu)先搜索最短路徑（最少步數(shù)的路徑）6101234501234567101010000110010110011110011010010100101110110000通過反向的線索追朔最短路徑的信息通過反向的線索追朔最短路徑的信息62 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)通

20、訊網(wǎng)？問題：?jiǎn)栴}：63 構(gòu)造網(wǎng)的一棵最小生成樹, 即:在 e 條帶權(quán)的邊中選取 n-1 條邊(不構(gòu)成回路), 使“權(quán)值之和權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）算法二：（克魯斯卡爾算法）該問題等價(jià)于：該問題等價(jià)于：算法一：（普里姆算法）算法一：（普里姆算法）64 取圖中任意一個(gè)頂點(diǎn) v 作為生成樹的根，之后往生成樹上添加新的頂點(diǎn) w。在添加的頂點(diǎn)在添加的頂點(diǎn) w 和已經(jīng)在生成樹上的頂點(diǎn)和已經(jīng)在生成樹上的頂點(diǎn)v 之間必定存在一之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)條邊，并且該邊的權(quán)值在所有連通頂點(diǎn) v 和和 w 之間的邊中取值最小之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直

21、至生成樹上含有 n-1 個(gè)頂點(diǎn)為止。普里姆算法的基本思想普里姆算法的基本思想:65abcdegf例如例如: :195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和= 14+8+3+5+16+21 = 6766 在生成樹的構(gòu)造過程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集 U 和尚未落在生成樹上的頂點(diǎn)集 V-U ，則應(yīng)在所在所有連通有連通U中頂點(diǎn)和中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值中頂點(diǎn)的邊中選取權(quán)值最小的邊最小的邊。 一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:UV-U67abcdegf195141827168213ae12dcb7closedge012

22、3456AdjvexLowcostaaa19141814例如例如: :e12ee8168d3dd7213c5 568 具體做法具體做法: 先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開始，若它的添加不使 SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止。 考慮問題的出發(fā)點(diǎn)考慮問題的出發(fā)點(diǎn): 為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。克魯斯卡爾算法的基本思想：克魯斯卡爾算法的基本思想：69abcdegf195141827168213ae12dcbgf7148531621例如例如: :712181970克魯斯卡爾克魯斯卡

23、爾算法描述算法描述:構(gòu)造非連通圖 ST=( V, ); k = i = 0; / k 計(jì)選中的邊數(shù) while (kn-1) +i; 檢查邊集 E 中第第 i 條權(quán)值最小的邊條權(quán)值最小的邊(u,v); 若(u,v)加入ST后不使ST中產(chǎn)生回路， 則 輸出邊(u,v); 且 k+;71普里姆算法普里姆算法 克魯斯卡爾算法克魯斯卡爾算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稠密圖稀疏圖稀疏圖適應(yīng)范圍適應(yīng)范圍比較兩種算法比較兩種算法72v 求從某個(gè)源點(diǎn)到其余各點(diǎn)的求從某個(gè)源點(diǎn)到其余各點(diǎn)的 最短路徑最短路徑73 求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想: 依最短路徑的長(zhǎng)度遞增的次序求

24、得各條路徑源點(diǎn)源點(diǎn)v1 其中，從源點(diǎn)到從源點(diǎn)到頂點(diǎn)頂點(diǎn)v的最短路徑的最短路徑是所有最短路徑中長(zhǎng)度最短者。v274 在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。 下一條路徑長(zhǎng)度次短的最短路徑最短路徑的特點(diǎn)：路徑長(zhǎng)度最短的最短路徑最短路徑的特點(diǎn)： 它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。75其余最短路徑的特點(diǎn)：再下一條路徑長(zhǎng)度次短的最短路徑最短路徑的特點(diǎn): 它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。 它或

25、者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。76求最短路徑的迪杰斯特拉算法：求最短路徑的迪杰斯特拉算法：一般情況下，Distk = 或者 = + 。 設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Distk 表示當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。771）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的Distk值。假設(shè)求得最短路徑的頂點(diǎn)為u，若若 Distu+G.arcsukDistk則將 Distk 改為 Distu+G.arcsuk。INFINITYkvarcsGkDist0.V0和k之間存在弧V0和k之間

26、不存在弧其中的最小值即為最短路徑的長(zhǎng)度其中的最小值即為最短路徑的長(zhǎng)度。78vkuDistDistkG.arcsukDistuku2312102212+10 23791 2 3 4 5 6dist01510infinfinf10infinf0101540150151030inf35303580 問題問題: 假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。 檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判蛲負(fù)渑判颉?1何謂何謂“拓?fù)渑判蛲負(fù)渑判颉?？?duì)有向圖進(jìn)行如下操作： 按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可

27、以人為加上任意的次序關(guān)系。82例如：對(duì)于下列有向圖BDAC 可求得拓?fù)溆行蛐蛄校?A B C D 或 A C B D 由此所得頂點(diǎn)的線性序列稱之為拓?fù)溆行蛐蛄?3BDAC反之，對(duì)于下列有向圖不能求得它的拓?fù)溆行蛐蛄小Ｒ驗(yàn)閳D中存在一個(gè)回路 B, C, D 84如何進(jìn)行拓?fù)渑判?？如何進(jìn)行拓?fù)渑判颍恳?、從有向圖中選取一個(gè)沒有前驅(qū)沒有前驅(qū) 的頂點(diǎn)，并輸出之； 重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。二、從有向圖中刪去此頂點(diǎn)以及所刪去此頂點(diǎn)以及所 有以它為尾的弧有以它為尾的??；85abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念 沒有前驅(qū)的頂點(diǎn)沒有前驅(qū)的頂點(diǎn) 入

28、度為零的頂點(diǎn)入度為零的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧刪除頂點(diǎn)及以它為尾的弧 弧頭頂點(diǎn)的入度減弧頭頂點(diǎn)的入度減186算法描述：算法描述：取入度為零的頂點(diǎn)v;while (v0) printf(v); +m; w = FirstAdj(v); while (w0) inDegreew-; w = nextAdj(v,w); 取下一個(gè)入度為零的頂點(diǎn)v;if (mn) printf(“圖中有回路”);87問題問題: 假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間。 問：哪些子工程項(xiàng)是“關(guān)鍵工程”？即：哪些子工程項(xiàng)將影響整個(gè)工程的完成期限的。88abcdefghk64521187244例

29、如例如: : “關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加權(quán)值增加 將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。最長(zhǎng)路徑的長(zhǎng)度增加。 整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)源點(diǎn)到匯點(diǎn)匯點(diǎn)的最長(zhǎng)路徑。源點(diǎn)匯點(diǎn)617489 如何如何求關(guān)鍵活動(dòng)？求關(guān)鍵活動(dòng)？“事件事件(頂點(diǎn)頂點(diǎn))” 的 最早發(fā)生時(shí)間 ve(j)ve(j) = 從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度；“事件事件(頂點(diǎn)頂點(diǎn))” 的 最遲發(fā)生時(shí)間 vl(k) vl(k) = 從頂點(diǎn)k到匯點(diǎn)的最短路徑長(zhǎng)度。90 假設(shè)第 i 條弧為 則對(duì)第 i 項(xiàng)活動(dòng)而言 “活動(dòng)活動(dòng)(弧弧)”的 最早開始時(shí)間 ee(i) ee(i) = ve(j)； “活動(dòng)活動(dòng)(弧弧)”的 最遲

30、開始時(shí)間 el(i) el(i) = vl(k) dut()；91 事件發(fā)生時(shí)間的計(jì)算公式：事件發(fā)生時(shí)間的計(jì)算公式： ve(源點(diǎn)) = 0； ve(k) = Maxve(j) + dut() vl(匯點(diǎn)) = ve(匯點(diǎn))； vl(j) = Minvl(k) dut()92abcdefghk64521187244a b c d efg h kvevl0000000006457115 715 14 1818181818181818181816 1486610807拓?fù)溆行蛐蛄型負(fù)溆行蛐蛄? a - d - f - c - b - e - h - g - k93a b c d efg h kvev

31、l06457715 14 181814161078660ab ac ad be ce df eg eh fh gk hk權(quán)權(quán)6 4 5 1 1 2 8 7 4 2 4el000645777 15 14141602366887 1094一、廣義表的類型定義一、廣義表的類型定義二、廣義表的存儲(chǔ)結(jié)構(gòu)二、廣義表的存儲(chǔ)結(jié)構(gòu)三、廣義表的遍歷三、廣義表的遍歷95一、一、廣義表廣義表的類型定義的類型定義 廣義表廣義表的定義：的定義： 廣義表是n（n0）個(gè)元素1, 2, , n的有限集，通常記作 LS = ( 1, 2, , n )。 廣義表是遞歸遞歸定義的線性結(jié)構(gòu)線性結(jié)構(gòu), 其中: i 或?yàn)樵釉?或?yàn)閺V義

32、表廣義表（子表） 。 96北京亞洲足球邀請(qǐng)賽北京亞洲足球邀請(qǐng)賽（日本, 韓國(guó),中國(guó), 朝鮮）（日本, 韓國(guó), （申花, 實(shí)德, 現(xiàn)代）,（）（）在現(xiàn)實(shí)中，不乏廣義表的例子：97 一般廣義表的例子一般廣義表的例子: A = ( ) A為空表 F = (d, (e) 小寫字母代表元素 D = (a,(b,c), F) C = (A, D, F) 大寫字母代表子表 B = (a, B) = (a, (a, (a, , ) ) )98廣義表廣義表是一個(gè)多層次多層次的線性結(jié)構(gòu)線性結(jié)構(gòu)例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bce99廣義表廣義表

33、LS = ( 1, 2, , n )的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn):1) 廣義表中的數(shù)據(jù)元素有相對(duì)次序次序；2) 廣義表的長(zhǎng)度長(zhǎng)度定義為最外層包含元素個(gè)數(shù)；3) 廣義表的深度深度定義為所含括弧的重?cái)?shù)； 注意：“原子”的深度為 0 “空表”的深度為 1 4) 廣義表可以共享共享；5) 廣義表可以是一個(gè)遞歸遞歸的表。 遞歸表的深度是無窮值，長(zhǎng)度是有限值。1006) 任何一個(gè)非空廣義表非空廣義表 LS = ( 1, 2, , n) 均可分解為 表頭表頭 Head(LS) = 1 和 表尾表尾 Tail(LS) = ( 2, , n) 兩部分。例如: D = ( E, F ) = (a, (b, c)，F(xiàn) )H

34、ead( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )101結(jié)構(gòu)的創(chuàng)建和銷毀結(jié)構(gòu)的創(chuàng)建和銷毀 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);

35、狀態(tài)函數(shù)狀態(tài)函數(shù) GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);插入和刪除操作插入和刪除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e);遍歷遍歷 Traverse_GL(L, Visit();廣義表廣義表的操作：的操作：102二、二、廣義表廣義表的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)通常采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點(diǎn)表結(jié)點(diǎn):原子結(jié)點(diǎn)：原子結(jié)點(diǎn)：tag=1 hp tptag=0 data1031) 表頭、表尾分析法：構(gòu)造存儲(chǔ)結(jié)構(gòu)的兩種分析方法構(gòu)造存儲(chǔ)

36、結(jié)構(gòu)的兩種分析方法: :若表頭為原子，則為為空表空表 ls=NIL非空表非空表 lstag=1 指向表頭的指針指向表尾的指針tag=0 data否則，依次類推。104例如:L=(a, (x, y), (x) )a (x, y), (x) ) (x, y) ( (x) )x (y) (x) ( )y ( ) (x) ( )x ( )105L = ( a, ( x, y ), ( ( x ) ) )a ( x, y ) ( ) 1 LL = ( )0 a 1 1 1 1 1 0 x ( )x 1062) 子表分析法：若子表為原子，則為空表空表 ls=NIL非空表非空表 1 指向子表1 的指針tag

37、=0 data否則，依次類推。 1 指向子表2 的指針 1 指向子表n 的指針ls 107例如例如:LS=( a, (x,y), (x) )ls a (x, y) (x) 108三、廣義表的遍歷三、廣義表的遍歷1. 廣義表操作的遞歸函數(shù)廣義表操作的遞歸函數(shù)2. 廣義表的應(yīng)用舉例廣義表的應(yīng)用舉例1091. 廣義表操作的遞歸函數(shù)廣義表操作的遞歸函數(shù)遞歸函數(shù)遞歸函數(shù) 一個(gè)含直接或間接調(diào)用本函數(shù)語句含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件：1) 在每一次調(diào)用自己時(shí)，必須是(在某 種意義上)更接近于解更接近于解; 2) 必須有一個(gè)終止終止處理或計(jì)算的準(zhǔn)則準(zhǔn)則。110 在利

38、用分治法求解時(shí)，所得子問題的類型常常和原問題相同，因而很自然地導(dǎo)致遞歸求解。分治法：分治法：對(duì)于一個(gè)輸入規(guī)模為 n 的函數(shù)或問題，用某種方法把輸入分割成 k(1ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepthif (!L) return 1; if (L-tag = ATOM) return 0; 116 1 1 1 L for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep;pppp-ptr.hppppppp-ptr.hppp-ptr.hp例如例如: :117例二例二 復(fù)制廣義表復(fù)制廣義表新的廣義表由新的表頭和表尾構(gòu)成。新的廣義表由新的表頭和表尾構(gòu)成。 可以直接求解的兩種簡(jiǎn)單情況為： 空表復(fù)制求得的新表自然也是空表空表