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

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

2、AdjVex(G, v); / 返回v的第一個鄰接點。若該頂點 /在G中沒有鄰接點，則返回“空”。 NextAdjVex(G, v, w); /返回v的（相對于w的）下一個 / 鄰接點。若w是v的最后一個鄰 / 接點，則返回“空”。 插入或刪除頂點 InsertVex( / 刪除G中頂點v及其相關的弧,插入和刪除弧 InsertArc( / 從頂點v起廣度優(yōu)先遍歷圖 / G，并對每個頂點調用函數(shù) / Visit一次且僅一次,7.2 圖的存儲表示圖的數(shù)組(鄰接矩陣)存儲表示#define INFINITY INT_MAX / 最大值#define MAX_VERTEX_NUM 20 / 最大頂點

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

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

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

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

7、 mark; / 訪問標記 int ivex, jvex; / 該邊依附的兩個頂點的位置 struct EBox *ilink, *jlink; / 分別指向依附這兩個頂點的下一條邊 InfoType *info; / 該邊信息指針 EBox; typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一條依附該頂點的邊 VexBox; typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; / 無向圖的當前頂點數(shù)和邊數(shù) AMLGraph,7.3 圖的

8、遍歷 從圖中某個頂點出發(fā)游歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。 一、深度優(yōu)先搜索 從圖中某個頂點V0 出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到，若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止,下列算法使用的全局變量 -Boolean visitedMAX; / 訪問標志數(shù)組Status (* VisitFunc)(int v); / 函數(shù)變量void DFSTraverse(Graph G, Status (*Visit

9、)(int v) / 對圖G作深度優(yōu)先遍歷。VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標志數(shù)組初始化for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 對尚未訪問的頂點調用DFS,void DFS(Graph G, int v) / 從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G。visitedv = TRUE; VisitFunc(v); / 訪問第v個頂點for ( w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G, v,

10、 w) )if (!visitedw) DFS(G, w); / 對v的尚未訪問的鄰接頂點w遞歸調用DFS,二、廣度優(yōu)先搜索 從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止,void BFSTraverse(Graph G, Status (*Visit)(int v) / 按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數(shù)組visited。 for

11、 (v=0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q); / 置空的輔助隊列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v尚未訪問 EnQueue(Q, v); / v入隊列 while (!QueueEmpty(Q) DeQueue(Q, u); / 隊頭元素出隊并置為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的尚未訪問的鄰接頂點w入隊列Q,7.4 最小生成樹 問題：假設要在n個城市之間建立通訊聯(lián)絡網，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經費的前提下建立這個 通訊網？ 該問題等價于：構造網的一棵最小生成樹，即：在e條帶權的邊中選取n-1條（不構成回路），使“權值之和”為最小,算法一：（普里姆算法） 可取圖中任意一個頂點v作為生成樹的根，之后若要往生成樹上添加頂點w，則在頂點v和頂點w之間必定存在一條邊，并且該邊的權值在所有連通頂點v和w之間的邊中取值最小。 一般情況下，假設n個頂點分成兩個集合：U（包含已落在生成樹上的結點）和V-U（尚未落在生成樹上的頂點），

13、則在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。 記錄從頂點集U到VU的代價最小的邊的輔助數(shù)組,struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; k = LocateVex ( G, u ); / 頂點u為構造生成樹的起始點 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) /在其余頂點中選

14、擇 k = minimum(closedge); / 求出T的下一個結點(k) printf(closedgek.adjvex, G.vexsk); / 輸出生成樹的邊 closedgek.lowcost = 0; / 第k頂點并入U集 for (j=0; jG.vexnum; +j) if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ; / 新頂點并入U后重新選擇最小邊,算法二：（克魯斯卡爾算法） 為使生成樹上邊的權值之和最小，顯然，其中每一條邊的權值應該盡可能地小?？唆斔箍査惴ǖ淖龇ň褪牵合葮嬙煲粋€

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

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

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

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

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

20、路徑vi,v1,vj / 路徑中所含頂點序號不大于1 若vi,v2, v2,vj存在， 則存在一條路徑vi, , v2, vj / 路徑中所含頂點序號不大于2 依次類推，則vi至vj的最短路徑應是上述這些路徑中，路徑長度最小者,7.7 拓撲排序 問題: 假設以有向圖表示一個工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。 如何檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。 何謂“拓撲排序”？ 對有向圖進行如下操作: 按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則可以人為加上任意的次序關系,如何進行拓撲排序？ 一、從有向圖中選取一個沒有前驅的頂點，并輸出之; 二、從有向圖中刪去此頂點以及所有以它為尾的弧; 重復上述兩步，直至圖空，或者圖不空但找不到無前驅的頂點為止。 沒有前驅 - 入度為零 刪除頂點及以它為尾的弧- 弧頭頂點的入度減1,算法: 取入度為零的頂點v; while (v0) printf(v); +m; w:=FirstAdj(v); while (w0) inDegreew-; w:=nextAdj(v,w); 取下一個入度為零的頂點v; if mn printf(“圖中有回路,7.8 關鍵路徑 問題: 假設以有向網表示一個施工流圖，弧上的權值表示完成該項子工程所需時間，問:哪些子工程項是“關鍵工程”