抽象數(shù)據(jù)類型圖的定義

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

2、AdjVex(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( / 刪除G中頂點(diǎn)v及其相關(guān)的弧,插入和刪除弧 InsertArc( / 從頂點(diǎn)v起廣度優(yōu)先遍歷圖 / G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù) / Visit一次且僅一次,7.2 圖的存儲(chǔ)表示圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示#define INFINITY INT_MAX / 最大值#define MAX_VERTEX_NUM 20 / 最大頂點(diǎn)

3、個(gè)數(shù)typedef enum DG, DN, AG, AN GraphKind;/有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct ArcCell VRType adj; / VRType是頂點(diǎn)關(guān)系類型。/ 對(duì)無權(quán)圖，用1或0表示相鄰否；/ 對(duì)帶權(quán)圖，則為權(quán)值類型。InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; / 頂點(diǎn)向量AdjMatrix arcs; / 鄰接矩陣int vexnum, a

4、rcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)GraphKind kind; / 圖的種類標(biāo)志 MGraph,圖的鄰接表存儲(chǔ)表示 #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; / 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc; / 指向下一條弧的指針 InfoType *info; / 該弧相關(guān)信息的指針 ArcNode; typedef struct VNode VertexType data; / 頂點(diǎn)信息 ArcNode *firstarc; / 指向第一條依附該頂點(diǎn)的弧 VNode, A

5、djListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int kind; / 圖的種類標(biāo)志 ALGraph,有向圖的十字鏈表存儲(chǔ)表示 #define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex, headvex; / 該弧的尾和頭頂點(diǎn)的位置 struct ArcBox *hlink, *tlink; / 分別指向下一個(gè)弧頭相同和弧尾相同的弧的指針域 InfoType *info; / 該弧相關(guān)信息的指針 ArcBo

6、x; typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; / 分別指向該頂點(diǎn)第一條入弧和出弧 VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; / 表頭向量 int vexnum, arcnum; / 有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph,無向圖的鄰接多重表存儲(chǔ)表示 #define MAX_VERTEX_NUM 20 typedef emnu unvisited, visited VisitIf; typedef struct Ebox VisitIf

7、 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 vexnum, edgenum; / 無向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) AMLGraph,7.3 圖的

8、遍歷 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。 一、深度優(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)都被訪問到為止,下列算法使用的全局變量 -Boolean visitedMAX; / 訪問標(biāo)志數(shù)組Status (* VisitFunc)(int v); / 函數(shù)變量void DFSTraverse(Graph G, Status (*Visit

9、)(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)用DFS,void DFS(Graph G, int v) / 從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。visitedv = TRUE; VisitFunc(v); / 訪問第v個(gè)頂點(diǎn)for ( w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G, v,

10、 w) )if (!visitedw) DFS(G, w); / 對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFS,二、廣度優(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)都被訪問到為止,void BFSTraverse(Graph G, Status (*Visit)(int v) / 按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited。 for

11、 (v=0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v尚未訪問 EnQueue(Q, v); / v入隊(duì)列 while (!QueueEmpty(Q) DeQueue(Q, u); / 隊(duì)頭元素出隊(duì)并置為u visitedu = TRUE; Visit(u); / 訪問u for ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) ) if ( ! visitedw) EnQue

12、ue(Q, w); / u的尚未訪問的鄰接頂點(diǎn)w入隊(duì)列Q,7.4 最小生成樹 問題：假設(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)值之和”為最小,算法一：（普里姆算法） 可取圖中任意一個(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è)集合：U（包含已落在生成樹上的結(jié)點(diǎn)）和V-U（尚未落在生成樹上的頂點(diǎn)），

13、則在所有連通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; / 初始，Uu for (i=0; iG.vexnum; +i) /在其余頂點(diǎn)中選

14、擇 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)值之和最小，顯然，其中每一條邊的權(quán)值應(yīng)該盡可能地小?？唆斔箍査惴ǖ淖龇ň褪牵合葮?gòu)造一個(gè)

15、只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止,算法: 構(gòu)造非連通圖 ST=( V, ); k = i = 0; while (kn-1) +i; 從邊集 E 中選取第i條權(quán)值最小的邊(u,v); 若(u,v)加入ST后不使ST中產(chǎn)生回路， 則 輸出邊(u,v); 且 k+; 一般來講， 由于普里姆算法的時(shí)間復(fù)雜度為O(n2)，則適于稠密圖；而克魯斯卡爾算法需對(duì)e條邊按權(quán)值進(jìn)行排序，其時(shí)間復(fù)雜度為O(eloge)，則適于稀疏圖,7.5 重（雙）連通圖和關(guān)節(jié)點(diǎn) 問題：若從一個(gè)連通圖中刪去任何一個(gè)頂點(diǎn)及其相關(guān)聯(lián)的

16、邊，它仍為一個(gè)連通圖的話，則該連通圖被稱為重（雙）連通圖。圖的雙連通性對(duì)于表示通訊或運(yùn)輸?shù)膱D來說，有著重要的意義。 若連通圖中的某個(gè)頂點(diǎn)和其相關(guān)聯(lián)的邊被刪去之后，該連通圖被分割成兩個(gè)或兩個(gè)以上的連通分量，則稱此頂點(diǎn)為關(guān)節(jié)點(diǎn)。 顯然，沒有關(guān)節(jié)點(diǎn)的連通圖為雙連通圖,關(guān)節(jié)點(diǎn)的特征： 假設(shè)從某個(gè)頂點(diǎn)V0出發(fā)對(duì)連通圖進(jìn)行深度優(yōu)先搜索遍歷，則可得到一棵深度優(yōu)先生成樹，樹上包含圖的所有頂點(diǎn)。 若生成樹的根結(jié)點(diǎn)，有兩個(gè)或兩個(gè)以上的分支，則此頂點(diǎn)(生成樹的根)必為關(guān)節(jié)點(diǎn); 對(duì)生成樹上的任意一個(gè)“頂點(diǎn)”，若其某棵子樹的根或子樹中的其它“頂點(diǎn)”沒有和其祖先相通的回邊，則該“頂點(diǎn)”必為關(guān)節(jié)點(diǎn),如何判別？ 1) 設(shè)V0

17、為深度優(yōu)先遍歷的出發(fā)點(diǎn) p = G.vertices0.firstarc; v = p-adjvex; DFSArticul(G, v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先搜索 if (count G.vexnum) / 生成樹的根有至少兩棵子樹 printf (0, G.vertices0.data); / 根是關(guān)節(jié)點(diǎn),2) 對(duì)生成樹上的頂點(diǎn)定義一個(gè)函數(shù): low(v) = Minvisitedv, loww, visitedk 對(duì)頂點(diǎn)v，若(在生成樹上)存在一個(gè)子樹根w, loww visitedv 則頂點(diǎn)v為關(guān)節(jié)點(diǎn) visitedv0 = min = +count; / count計(jì)頂點(diǎn)訪問次

18、序 for (p=G.verticesv0.firstarc; p; p=p-nextarc) w = p-adjvex; / w為v0的鄰接頂點(diǎn) if (visitedw = 0) / w未曾被訪問 DFSArticul(G, w); / 返回前求得loww if (loww =visitedv0) printf(v0, G.verticesv0.data); / 輸出關(guān)節(jié)點(diǎn) else if (visitedw min) min = visitedw; / w是回邊上的頂點(diǎn) lowv0 = min,7.6 兩點(diǎn)之間的最短路徑問題 求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑 迪杰斯特拉推出了一個(gè)按路徑長(zhǎng)

19、度遞增的次序求從源點(diǎn)到其余各點(diǎn)最短路徑的算法。 假設(shè)圖中所示為從源點(diǎn)到其余各點(diǎn)之間的最短路徑，則在這些路徑中，必然存在一條長(zhǎng)度最短者 在這條路徑上，必定只含一條(權(quán)值最小)弧，由此，只要在所有從源點(diǎn)出發(fā)的弧中查找權(quán)值最小者,長(zhǎng)度次短的路徑可能有兩種情況: 它可能是從源點(diǎn)直接到該點(diǎn)的路徑; 也可能是，從源點(diǎn)到a, 再從a到該點(diǎn) 其余依次類推。 假設(shè) Distk 表示 當(dāng)前所求得的從源點(diǎn)到k的最 短路徑 顯然， Distk = 或者 = +,二、每一對(duì)頂點(diǎn)之間的最短路徑 從vi到vj的最短路徑是以下各種可能路徑中的長(zhǎng)度最小者: 若存在，則存在路徑vi,vj / 路徑中不含其它頂點(diǎn) 若,存在，則存在

20、路徑vi,v1,vj / 路徑中所含頂點(diǎn)序號(hào)不大于1 若vi,v2, v2,vj存在， 則存在一條路徑vi, , v2, vj / 路徑中所含頂點(diǎn)序號(hào)不大于2 依次類推，則vi至vj的最短路徑應(yīng)是上述這些路徑中，路徑長(zhǎng)度最小者,7.7 拓?fù)渑判?問題: 假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。 如何檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判颉?何謂“拓?fù)渑判颉保?對(duì)有向圖進(jìn)行如下操作: 按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系,如何進(jìn)行拓?fù)渑判颍?一、從有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)，并輸出之; 二、從有向圖中刪去此頂點(diǎn)以及所有以它為尾的弧; 重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。 沒有前驅(qū) - 入度為零 刪除頂點(diǎn)及以它為尾的弧- 弧頭頂點(diǎn)的入度減1,算法: 取入度為零的頂點(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(“圖中有回路,7.8 關(guān)鍵路徑 問題: 假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間，問:哪些子工程項(xiàng)是“關(guān)鍵工程”