數(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ù)語圖的定義和術(shù)語有向圖、 無向圖、 網(wǎng)、 子圖 弧頭、 弧尾、 邊完全圖、 稀疏圖、 稠密圖 鄰接點(diǎn)、 度、 入度、 出度路徑、 路徑長(zhǎng)度、 回路簡(jiǎn)單路徑、 簡(jiǎn)單回路連通圖、 連通分量、強(qiáng)連通圖、 強(qiáng)連通分量生成樹、 生成森林、 最小生成樹名詞和術(shù)語名詞和術(shù)語結(jié)構(gòu)的建立和銷毀:CreateGraph(&G,V,VR); / 按V和VR的定義構(gòu)造圖G。D

2、estroyGraph(&G); / 銷毀圖G。對(duì)頂點(diǎ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中沒有鄰接點(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是無/ 向的，則還增添對(duì)稱弧。DeleteArc(&G, v, w); /在G中刪除弧，若G是無/ 向的，則還刪除對(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ǎng)的鄰接矩陣定義 wi,j 邊或弧 aIj= 0， 無一般用二維數(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; / 訪問標(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; / 無向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) AMLGraph; 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。一、深度優(yōu)先搜索一、深度優(yōu)先搜索從圖中某個(gè)頂點(diǎn)V0 出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到，若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。7.3 圖的遍歷圖的遍歷/- 下列算法使用的全局變量 -Boolean visitedMAX; / 訪問標(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; / 訪問標(biāo)志數(shù)組初始化for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 對(duì)尚未訪問的頂點(diǎn)調(diào)用DFSvoid DFS(Graph G, int v) / 從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。visitedv = TRUE; VisitFunc(v); / 訪問第v個(gè)頂點(diǎn)for (

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

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

13、AdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) )if ( ! visitedw) EnQueue(Q, w); / u的尚未訪問的鄰接頂點(diǎn)w入隊(duì)列Q7.4 圖的連通性問題圖的連通性問題1.無向圖的連通分量和生成樹無向圖的連通分量和生成樹連通圖從一個(gè)結(jié)點(diǎn)出發(fā)，可訪問圖中所有頂點(diǎn)，對(duì)于非連通圖，則需從多個(gè)頂點(diǎn)出發(fā)，才能訪問所有頂點(diǎn)。每一個(gè)出發(fā)點(diǎn)，遍歷時(shí)，所訪問的點(diǎn)為其分量的頂點(diǎn)。求連通過分量求連通過分量，則只需將對(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)集。問題：假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？該問題等價(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未曾被訪問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 有向無環(huán)圖及其應(yīng)用有向無環(huán)圖及其應(yīng)用一個(gè)無環(huán)的有向圖，稱有向無環(huán)圖稱有向無環(huán)圖。DAG圖圖7.21 P179有向無環(huán)圖的應(yīng)用：（1） 描述表達(dá)式描述表達(dá)式圖7.23 P179（2）描述工程或系統(tǒng)的進(jìn)行）描述工程或系統(tǒng)的進(jìn)行 工程可以分為若干個(gè)子過程（稱為活動(dòng)），子過程中受條件約束，則可檢查是否可順利進(jìn)行。有向無環(huán)圖的檢查有向無環(huán)圖的檢查 對(duì)無向圖，若深度優(yōu)先搜索中遇到回邊則其必定存在環(huán)路 對(duì)有向

19、圖，在深度優(yōu)先搜索DFS（V）結(jié)束之前中遇到回邊U到V則的回邊，圖有也必定有環(huán)路。 問題問題: 假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。如何檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判颉?何謂何謂“拓?fù)渑判蛲負(fù)渑判颉保?按照有向圖給出的約束次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒有限定次序關(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è)沒有前驅(qū)的頂點(diǎn)，并輸出之;2. 從有向圖中刪去此頂點(diǎn)以及所有以它為尾的弧;重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。沒有前驅(qū)沒有前驅(qū) - 入度為零入度為零刪除頂點(diǎn)及以它為尾的弧刪除頂點(diǎn)及以它為尾的弧- 弧頭頂點(diǎn)的入度減弧頭頂點(diǎn)的入度減1例：如圖例：如圖7.28 P182 問題問題: 假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間，問:哪些子工程項(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è)帶樹的有向無環(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)度最短者 在這條路徑上