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

1、ADT Graph 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：RVRVR| v,wV且P(v,w)，表示從v到w的弧，謂詞P(v,w)定義了弧的意義或信息 第七章第七章 圖圖7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)有向圖、 無(wú)向圖、 網(wǎng)、 子圖 弧頭、 弧尾、 邊完全圖、 稀疏圖、 稠密圖 鄰接點(diǎn)、 度、 入度、 出度路徑、 路徑長(zhǎng)度、 回路簡(jiǎn)單路徑、 簡(jiǎn)單回路連通圖、 連通分量、強(qiáng)連通圖、 強(qiáng)連通分量生成樹、 生成森林、 最小生成樹名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)結(jié)構(gòu)的建立和銷毀:CreateGraph(&G,V,VR); / 按V和VR的定義構(gòu)造圖G。D

2、estroyGraph(&G); / 銷毀圖G。對(duì)頂點(diǎn)的訪問(wèn)操作:LocateVex(G, u); / 若G中存在頂點(diǎn)u，則返回該頂點(diǎn)/ 在圖中位置位置；否則返回其它信息。GetVex(G, v); / 返回v的值。PutVex(&G, v, value); / 對(duì)v賦值value。圖的基本操作圖的基本操作FirstAdjVex(G, v); / 返回v的第一個(gè)鄰接點(diǎn)。若該頂點(diǎn)/在G中沒(méi)有鄰接點(diǎn)，則返回“空”。NextAdjVex(G, v, w); /返回v的（相對(duì)于w的）下一個(gè)/ 鄰接點(diǎn)。若w是v的最后一個(gè)鄰/ 接點(diǎn)，則返回“空”。插入或刪除頂點(diǎn)InsertVex(&

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

4、圖/ G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)/ Visit一次且僅一次。圖的鄰接矩陣7.2 圖的存儲(chǔ)表示圖的存儲(chǔ)表示圖的鄰接矩陣 1 邊或弧 aIj= 0 無(wú)網(wǎng)的鄰接矩陣定義 wi,j 邊或弧 aIj= 0， 無(wú)一般用二維數(shù)組表示類型描述：類型描述：#define M_V_NUM 20typedef struct ArcCell VertexType adj; InfoType *info ArcCell, AdjListM_V_NUMM_V_NUM;typedef struct vertextype vexm_v_num AdjList arc; int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)

5、和弧數(shù) int kind; / 圖的種類標(biāo)志 mgraph;有關(guān)運(yùn)算見有關(guān)運(yùn)算見P1622 鄰接表adjvexnextarcinfodatafirstarc表結(jié)點(diǎn) 頭結(jié)點(diǎn)#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode; /表結(jié)點(diǎn)typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM; /頭結(jié)點(diǎn)typedef st

6、ruct AdjList vertices;int vexnum, arcnum; int kind; ALGraph; 類似的有逆鄰接表類似的有逆鄰接表3。十字鏈表。十字鏈表 tailvexheadvexhlinktlinkinfo 頂點(diǎn)結(jié)點(diǎn)datafirstinfirstout弧結(jié)點(diǎn)有向圖的鄰接表和逆鄰接表的結(jié)合 #define MAX_VERTEX_NUM 20typedef struct ArcBox int tailvex, headvex; / 該弧的尾和頭頂點(diǎn)的位置struct ArcBox *hlink, *tlink; InfoType *info; / 該弧相關(guān)信息的指針

7、ArcBox;typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 表頭向量int vexnum, arcnum; / 有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph;例：如圖7.11所示。P165類型描述類型描述4。鄰接多重表。鄰接多重表 邊結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)markivexilinkjvexjlinkinfo data firstedge #define MAX_VERTEX_NUM 20typedef emnu

8、unvisited, visited VisitIf;typedef struct Ebox VisitIf mark; / 訪問(wèn)標(biāo)記int ivex, jvex; / 該邊依附的兩個(gè)頂點(diǎn)的位置struct EBox *ilink, *jlink; / 分別指向依附這兩個(gè)頂點(diǎn)的下一條邊InfoType *info; / 該邊信息指針 EBox;typedef struct VexBox VertexType data;EBox *firstedge; / 指向第一條依附該頂點(diǎn)的邊 VexBox;typedef struct VexBox adjmulistMAX_VERTEX_NUM;int

9、vexnum, edgenum; / 無(wú)向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) AMLGraph; 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。一、深度優(yōu)先搜索一、深度優(yōu)先搜索從圖中某個(gè)頂點(diǎn)V0 出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到，若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。7.3 圖的遍歷圖的遍歷/- 下列算法使用的全局變量 -Boolean visitedMAX; / 訪問(wèn)標(biāo)志數(shù)組Status (* Visit

10、Func)(int v); / 函數(shù)變量voidGraph G, Status (*Visit)(int v) / 對(duì)圖G作深度優(yōu)先遍歷。VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問(wèn)標(biāo)志數(shù)組初始化for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFSvoid DFS(Graph G, int v) / 從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。visitedv = TRUE; VisitFunc(v); / 訪問(wèn)第v個(gè)頂點(diǎn)for (

11、 w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G, v, w) )if (!visitedw) DFS(G, w); / 對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS計(jì)算時(shí)間O（n+e）深度優(yōu)先遍歷深度優(yōu)先遍歷從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問(wèn)此頂點(diǎn)之后依次訪問(wèn)V0的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn),則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。二、廣度優(yōu)先搜索二、廣度優(yōu)先搜索void BFSTraverse

12、(Graph G, Status (*Visit)(int v) / 按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問(wèn)標(biāo)志數(shù)組visited。for (v=0; vG.vexnum; +v) visitedv = FALSE;InitQueue(Q); / 置空的輔助隊(duì)列Qfor ( v=0; vG.vexnum; +v )if ( !visitedv) / v尚未訪問(wèn)EnQueue(Q, v); / v入隊(duì)列while (!QueueEmpty(Q) DeQueue(Q, u); / 隊(duì)頭元素出隊(duì)并置為uvisitedu = TRUE; Visit(u); / 訪問(wèn)ufor ( w=First

13、AdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) )if ( ! visitedw) EnQueue(Q, w); / u的尚未訪問(wèn)的鄰接頂點(diǎn)w入隊(duì)列Q7.4 圖的連通性問(wèn)題圖的連通性問(wèn)題1.無(wú)向圖的連通分量和生成樹無(wú)向圖的連通分量和生成樹連通圖從一個(gè)結(jié)點(diǎn)出發(fā)，可訪問(wèn)圖中所有頂點(diǎn)，對(duì)于非連通圖，則需從多個(gè)頂點(diǎn)出發(fā)，才能訪問(wèn)所有頂點(diǎn)。每一個(gè)出發(fā)點(diǎn)，遍歷時(shí)，所訪問(wèn)的點(diǎn)為其分量的頂點(diǎn)。求連通過(guò)分量求連通過(guò)分量，則只需將對(duì)應(yīng)的邊全部加入到分量頂點(diǎn)中即可。算法7。7 深度優(yōu)先生成森林。P171*2.有向圖的強(qiáng)連通分量有向圖的強(qiáng)連通分量深度優(yōu)先搜索是求有向圖的強(qiáng)連通分量的

14、一個(gè)新的有效方法。十字鏈表存貯由某頂點(diǎn)出發(fā)，作逆向深度深度優(yōu)先搜索的頂點(diǎn)集是有向圖G中的個(gè)強(qiáng)連通的頂點(diǎn)集。問(wèn)題：假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？該問(wèn)題等價(jià)于：構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條（不構(gòu)成回路），使“權(quán)值之和”為最小。3 最小生成樹最小生成樹算法一：（普里姆算法）算法一：（普里姆算法）可取圖中任意一個(gè)頂點(diǎn)v作為生成樹的根，之后若要往生成樹上添加頂點(diǎn)w，則在頂點(diǎn)v和頂點(diǎn)w之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最小。一般情況下，假設(shè)n個(gè)頂點(diǎn)分成兩個(gè)集合：

15、U（包含已落在生成樹上的結(jié)點(diǎn)）和V-U（尚未落在生成樹上的頂點(diǎn)），則在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。記錄從頂點(diǎn)集U到VU的代價(jià)最小的邊的輔助數(shù)組：struct VertexType adjvex;VRType lowcost; closedgeMAX_VERTEX_NUM;k = LocateVex ( G, u ); / 頂點(diǎn)u為構(gòu)造生成樹的起始點(diǎn)for ( j=0; jG.vexnum; +j ) / 輔助數(shù)組初始化if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uufor (i

16、=0; iG.vexnum; +i) /在其余頂點(diǎn)中選擇k = minimum(closedge); / 求出T的下一個(gè)結(jié)點(diǎn)(k)printf(closedgek.adjvex, G.vexsk); / 輸出生成樹的邊closedgek.lowcost = 0; / 第k頂點(diǎn)并入U(xiǎn)集for (j=0; jG.vexnum; +j)if (G.arcskj.adj closedgej.lowcost)closedgej = G.vexsk, G.arcskj.adj ;/ 新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊算法二：（克魯斯卡爾算法）算法二：（克魯斯卡爾算法）為使生成樹上邊的權(quán)值之和最小，顯然，其中每一

17、條邊的權(quán)值應(yīng)該盡可能地小。克魯斯卡爾算法的做法就是：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。算法算法:構(gòu)造非連通圖 ST=( V, );k = i = 0;while (kadjvex;DFSArticul(G, v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先搜索if (count nextarc) w = p-adjvex; / w為v0的鄰接頂點(diǎn)if (visitedw = 0) / w未曾被訪問(wèn)DFSArticul(G, w); / 返回前求得lowwif (loww =visitedv0) pr

18、intf(v0, G.verticesv0.data); / 輸出關(guān)節(jié)點(diǎn)elseif (visitedw min) min = visitedw; / w是回邊上的頂點(diǎn)lowv0 = min; 7.5 有向無(wú)環(huán)圖及其應(yīng)用有向無(wú)環(huán)圖及其應(yīng)用一個(gè)無(wú)環(huán)的有向圖，稱有向無(wú)環(huán)圖稱有向無(wú)環(huán)圖。DAG圖圖7.21 P179有向無(wú)環(huán)圖的應(yīng)用：（1） 描述表達(dá)式描述表達(dá)式圖7.23 P179（2）描述工程或系統(tǒng)的進(jìn)行）描述工程或系統(tǒng)的進(jìn)行 工程可以分為若干個(gè)子過(guò)程（稱為活動(dòng)），子過(guò)程中受條件約束，則可檢查是否可順利進(jìn)行。有向無(wú)環(huán)圖的檢查有向無(wú)環(huán)圖的檢查 對(duì)無(wú)向圖，若深度優(yōu)先搜索中遇到回邊則其必定存在環(huán)路 對(duì)有向

19、圖，在深度優(yōu)先搜索DFS（V）結(jié)束之前中遇到回邊U到V則的回邊，圖有也必定有環(huán)路。 問(wèn)題問(wèn)題: 假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。如何檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判颉?何謂何謂“拓?fù)渑判蛲負(fù)渑判颉保?按照有向圖給出的約束次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。這樣若能得到一個(gè)全序，則稱為拓?fù)渑判颉?概念：偏序， 全序，拓樸有序。7.5.1 拓?fù)渑判蛲負(fù)渑判駻OV網(wǎng)：網(wǎng)：頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)間的優(yōu)先關(guān)系的有向圖。 如何進(jìn)行拓?fù)渑判?？如何進(jìn)行拓?fù)渑判颍?. 從有向圖

20、中選取一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并輸出之;2. 從有向圖中刪去此頂點(diǎn)以及所有以它為尾的弧;重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止。沒(méi)有前驅(qū)沒(méi)有前驅(qū) - 入度為零入度為零刪除頂點(diǎn)及以它為尾的弧刪除頂點(diǎn)及以它為尾的弧- 弧頭頂點(diǎn)的入度減弧頭頂點(diǎn)的入度減1例：如圖例：如圖7.28 P182 問(wèn)題問(wèn)題: 假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間，問(wèn):哪些子工程項(xiàng)是“關(guān)鍵工程”？即:將影響整個(gè)工程完成期限的子工程項(xiàng)。整個(gè)工程完成的時(shí)間為:從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑。稱關(guān)鍵路徑關(guān)鍵路徑。AOE網(wǎng)網(wǎng)：項(xiàng)點(diǎn)表示事件，邊表示活動(dòng)的網(wǎng)。它是一個(gè)帶樹的有向無(wú)環(huán)圖。“關(guān)鍵活

21、動(dòng)”指的是: 關(guān)鍵路徑上的活動(dòng)，該弧上的權(quán)值增加權(quán)值增加 將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。最長(zhǎng)路徑的長(zhǎng)度增加。7.5.2 關(guān)鍵路徑關(guān)鍵路徑“事件(頂點(diǎn))” 的 最早發(fā)生時(shí)間最早發(fā)生時(shí)間 ve(j)ve(j) = 從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度;“事件(頂點(diǎn))” 的 最遲發(fā)生時(shí)間最遲發(fā)生時(shí)間 vl(k) vl(k) = 從頂點(diǎn)k到匯點(diǎn)的最短路徑長(zhǎng)度;假設(shè)第i條弧為則 第i項(xiàng)活動(dòng) “活動(dòng)(弧)”的 最早開始時(shí)間 ee(i) ee(i) = ve(j);“活動(dòng)(弧)”的 最遲開始時(shí)間 el(i) el(i) = vl(k) dut(); 如何求關(guān)鍵活動(dòng)？如何求關(guān)鍵活動(dòng)？事件發(fā)生時(shí)間的計(jì)算公式:ve(

22、源點(diǎn)) = 0;ve(k) = Maxve(j) + dut()vl(匯點(diǎn)) = ve(匯點(diǎn));vl(j) = Minvl(k) dut()求ve的順序應(yīng)該是按拓?fù)溆行虻拇涡?求vl的順序應(yīng)該是按拓?fù)淠嫘虻拇涡? 算法的實(shí)現(xiàn)要點(diǎn)算法的實(shí)現(xiàn)要點(diǎn):（1）建立VOE-網(wǎng)的存貯結(jié)構(gòu)（2）從V0出發(fā)，ve0=0,按拓樸有序求最旱發(fā)生時(shí)間（3）從Vn出發(fā)，vln=ven,按拓樸逆序求最遲發(fā)生時(shí)間（4）求活動(dòng)的最早和最遲發(fā)生時(shí)間，若有e(s)=l(s),則為關(guān)鍵活動(dòng)。算法算法7.13,7.14 P184-185例：如圖例：如圖7.30所示。所示。P185 7.6.1 從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑例：圖例：圖7.34所示。所示。P187 迪杰斯特拉推出了一個(gè)按路徑長(zhǎng)度遞增的次序按路徑長(zhǎng)度遞增的次序求從源點(diǎn)到其余各點(diǎn)最短路徑的算法。 假設(shè)圖中所示為從源點(diǎn)到其余各點(diǎn)之間的最短路徑，則在這些路徑中，必然存在一條長(zhǎng)度最短者 在這條路徑上