數(shù)據(jù)結(jié)構(gòu)高春曉71圖

1、ABCDEABCDE 7.1 抽象數(shù)據(jù)類型圖的定義抽象數(shù)據(jù)類型圖的定義 7.2 圖的存儲表示圖的存儲表示 7.3 圖的遍歷圖的遍歷 7.4 最小生成樹最小生成樹 7.5 重（雙）連通圖和關(guān)節(jié)點(diǎn)重（雙）連通圖和關(guān)節(jié)點(diǎn) 7.6 兩點(diǎn)之間的最短路徑問題兩點(diǎn)之間的最短路徑問題 7.7 拓?fù)渑判蛲負(fù)渑判?7.8 關(guān)鍵路徑關(guān)鍵路徑 7.1.1 圖的定義圖的定義 圖圖(Graph)是由一個是由一個頂點(diǎn)頂點(diǎn)(Vertex)集集 V 和一個和一個弧弧(Arc)集集 R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V , R ) 其中其中 R| v,wV 且且 P(v,w) 表示從表示從 v 到到 w 的一

2、條弧，并稱的一條弧，并稱 w 為弧頭，為弧頭，v 為弧尾。為弧尾。 謂詞謂詞 P(v,w) 定義了弧定義了弧 的意義或信息的意義或信息 有向圖有向圖(Digraph)：由于：由于“弧弧”是有方向的，因此稱是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。 例如：例如：G1 = (V1, VR1) V1=A, B, C, D, E VR1=, , , , , , , ABCDE弧頭弧頭Initial Node弧尾弧尾Terminal Node 若若 VR 必有必有 VR, 則稱則稱 (v,w) 為頂點(diǎn)為頂點(diǎn)v 和頂點(diǎn)和頂點(diǎn) w 之間存在一條之間存在一條“邊邊(ed

3、ge)”。 由頂點(diǎn)集和邊集構(gòu)成的圖稱作由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向圖無向圖(Undiagrah)。例如：例如：G1 = (V1, VR1)V1=A, B, C, D, EVR1=, , , , , , ABCDE 1)網(wǎng)網(wǎng)(Network) 弧或邊帶權(quán)弧或邊帶權(quán)(Weight)的圖分別稱的圖分別稱有向網(wǎng)有向網(wǎng)和和無向網(wǎng)無向網(wǎng)ABCDE134142390661 2)子圖子圖 G=(V ,VR ) ，G =(V ,VR ),且且 VV, VRVR,則稱則稱 G 為為 G 的的子圖子圖(Subgraph)AABACD 假設(shè)圖中有假設(shè)圖中有 n 個頂點(diǎn)，個頂點(diǎn)，e 條邊，則條邊，則 3) 含有含有e

4、=n(n-1)/2 條邊的條邊的無向圖無向圖稱作稱作完全圖完全圖(Completed graph) 4) 含有含有e=n(n-1) 條弧的條弧的有向圖有向圖稱作稱作 有向完全圖有向完全圖 5) 若邊或弧的個數(shù)若邊或弧的個數(shù) enlogn，則稱作，則稱作稀疏圖稀疏圖(Sparse graph)，否則稱作否則稱作稠密圖稠密圖(Dense graph).BADEC 6）假若頂點(diǎn)）假若頂點(diǎn)v 和頂點(diǎn)和頂點(diǎn)w 之間存在一條邊，則稱頂點(diǎn)之間存在一條邊，則稱頂點(diǎn)v 和和w 互為互為鄰接點(diǎn)鄰接點(diǎn)。 邊邊(v,w) 和頂點(diǎn)和頂點(diǎn)v 和和w 相相關(guān)聯(lián)關(guān)聯(lián) 7 7）和頂點(diǎn)）和頂點(diǎn)v 關(guān)聯(lián)的邊的數(shù)目定義為頂點(diǎn)的關(guān)聯(lián)的

5、邊的數(shù)目定義為頂點(diǎn)的度度 出度、入度出度、入度BADECBADEC 8) 從頂點(diǎn)從頂點(diǎn)u 到頂點(diǎn)到頂點(diǎn)w 之間存在一條之間存在一條路徑路徑(Path)，當(dāng)，當(dāng) u=vi,0,vi,1, , vi,m=w中中， VR 1jm 路徑上邊的數(shù)目稱作路徑上邊的數(shù)目稱作路徑長度路徑長度 簡單路徑簡單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑 簡單回路簡單回路(Cycle):序列中第一個頂點(diǎn)和最后一個頂點(diǎn)序列中第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑相同的路徑BADEC 9)若圖若圖G中任意兩個頂點(diǎn)之間都有路徑相通，則稱此中任意兩個頂點(diǎn)之間都有路徑相通，則稱此圖為圖為連通圖連通圖(Connect

6、ed graph)； 若無向圖為非連通圖，則圖中各個極大連通子圖稱若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的作此圖的連通分量連通分量(Connected component);BADECBADEC 對有向圖，若任意兩個頂點(diǎn)之間都存在一條有向路對有向圖，若任意兩個頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為徑，則稱此有向圖為強(qiáng)連通圖強(qiáng)連通圖 否則，其各個強(qiáng)連通子圖稱作它的否則，其各個強(qiáng)連通子圖稱作它的強(qiáng)連通分量強(qiáng)連通分量ABCDEBADEC 結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀 對頂點(diǎn)的訪問操作對頂點(diǎn)的訪問操作 對鄰接點(diǎn)的操作對鄰接點(diǎn)的操作 插入或刪除頂點(diǎn)插入或刪除頂點(diǎn) 插入和刪除弧插入和刪

7、除弧 遍歷遍歷 CreatGraph(&G, V, VR): 按定義按定義(V, VR) 構(gòu)造圖構(gòu)造圖 DestroyGraph(&G): 銷毀圖銷毀圖 LocateVex(G, u); 若若G中存在頂點(diǎn)中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中，則返回該頂點(diǎn)在圖中“位置位置” ； 否則返回其它信息否則返回其它信息 GetVex(G, v); 返回返回 v 的值的值 PutVex(&G, v, value); 對對 v 賦值賦值value FirstAdjVex(G, v); 返回返回 v 的的“第一個鄰接點(diǎn)第一個鄰接點(diǎn)” 。 若該頂點(diǎn)在若該頂點(diǎn)在 G 中沒有鄰接點(diǎn)，則返回中沒有

8、鄰接點(diǎn)，則返回“空空” NextAdjVex(G, v, w); 返回返回 v 的（相對于的（相對于 w 的）的） “下一個鄰接點(diǎn)下一個鄰接點(diǎn)”。 若若 w 是是 v 的最后一個鄰接點(diǎn)，則返回的最后一個鄰接點(diǎn)，則返回“空空”。 InsertVex(&G, v); 在圖在圖G中增添新頂點(diǎn)中增添新頂點(diǎn)v DeleteVex(&G, v); 刪除刪除G中頂點(diǎn)中頂點(diǎn)v及其相關(guān)的弧及其相關(guān)的弧 DeleteVex(&G, v); 刪除刪除G中頂點(diǎn)中頂點(diǎn)v及其相關(guān)的弧及其相關(guān)的弧 DeleteArc(&G, v, w); 在在G中刪除弧中刪除弧 若若G是無向的，則還刪除對稱

9、弧是無向的，則還刪除對稱弧 DFSTraverse(G, v, Visit(); 從頂點(diǎn)從頂點(diǎn)v起起深度優(yōu)先深度優(yōu)先遍歷圖遍歷圖G 并對每個頂點(diǎn)調(diào)用函數(shù)并對每個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次一次且僅一次 BFSTraverse(G, v, Visit(); 從頂點(diǎn)從頂點(diǎn)v起起廣度優(yōu)先廣度優(yōu)先遍歷圖遍歷圖G， 并對每個頂點(diǎn)調(diào)用函數(shù)并對每個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次一次且僅一次 7.2.1 圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示 7.2.2 圖的鄰接表存儲表示圖的鄰接表存儲表示 7.2.3 有向圖的十字鏈表存儲表示有向圖的十字鏈表存儲表示 7.2.4 無向圖的鄰接多重表存

10、儲表示無向圖的鄰接多重表存儲表示 定義定義:矩陣的元素為矩陣的元素為BACDFEVRjiVRjiAij),( 1),(0頂點(diǎn)頂點(diǎn)i 的度？的度？第第 i 行行 (列列) 1 的個數(shù)。的個數(shù)。有向圖的鄰接矩陣為非對稱矩陣有向圖的鄰接矩陣為非對稱矩陣ABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0typedef struct ArcCell / 弧的定義弧的定義 VRType adj; / VRType是頂點(diǎn)關(guān)系類型。是頂點(diǎn)關(guān)系類型。 / 對無權(quán)圖，用對無權(quán)圖，用1或或0表示相鄰否；表示相鄰否； / 對帶權(quán)圖，則為權(quán)值類型。對帶權(quán)圖，則為權(quán)值類型

11、。 InfoType *info; / 該弧相關(guān)信息的指針該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct / 圖的定義圖的定義 VertexType / 頂點(diǎn)信息頂點(diǎn)信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息弧的信息 int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù)頂點(diǎn)數(shù)，弧數(shù) GraphKind kind; / 圖的種類標(biāo)志圖的種類標(biāo)志 MGraph;BACDFE0A1B2C3D4E5F14045352501123頂點(diǎn)頂點(diǎn)i 的度？的度？頂

12、點(diǎn)頂點(diǎn) i 邊表長度邊表長度無向圖的鄰接表無向圖的鄰接表共有多少邊節(jié)點(diǎn)？共有多少邊節(jié)點(diǎn)？2e。ABECD0A1B2C3D4E14201有向圖的鄰接表有向圖的鄰接表32出邊表出邊表頂點(diǎn)頂點(diǎn) i 的出度的出度?頂點(diǎn)頂點(diǎn) i 的出邊表長度的出邊表長度共有多少邊節(jié)點(diǎn)？共有多少邊節(jié)點(diǎn)？e。ABECD有向圖的逆鄰接表有向圖的逆鄰接表30240入邊表入邊表0A1B2C3D4E3頂點(diǎn)頂點(diǎn) i 的入度的入度?頂點(diǎn)頂點(diǎn) i 的入邊表長度的入邊表長度共有多少邊節(jié)點(diǎn)？共有多少邊節(jié)點(diǎn)？e。adjvex nextarc info弧的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)typedef struct ArcNode int adjvex;

13、/ 該弧所指向的頂點(diǎn)的位置該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc; / 指向下一條弧的指針指向下一條弧的指針 InfoType *info; / 該弧相關(guān)信息的指針該弧相關(guān)信息的指針 ArcNode;頂點(diǎn)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)的結(jié)點(diǎn)結(jié)構(gòu) data firstarctypedef struct VNode VertexType data; / 頂點(diǎn)信息頂點(diǎn)信息 ArcNode *firstarc; / 指向第一條依附該頂點(diǎn)的弧指向第一條依附該頂點(diǎn)的弧 VNode, AdjListMAX_VERTEX_NUM;圖的圖的結(jié)構(gòu)定義結(jié)構(gòu)定義typedef struct AdjLi

14、st vertices;/頂點(diǎn)列表頂點(diǎn)列表 int vexnum, arcnum; /頂點(diǎn)數(shù)，邊數(shù)頂點(diǎn)數(shù)，邊數(shù) int kind; / 圖的種類標(biāo)志圖的種類標(biāo)志 ALGraph;vertices vexnumarcnumkindTypedef enum DG, DN, UDG, UDN Graphkind;ALGraph G;vertices vexnumarcnumkinddatafirstarc0A1B2C3D4E5FGadjvex-1infonextarc4 infonull0 info5 info4 infonullBACDFEV1V2V3V4v1v2v3v42001023132302

15、30123如何求頂點(diǎn)如何求頂點(diǎn) i 的入度的入度?如何求如何求頂點(diǎn)頂點(diǎn) i 的出度的出度?tailvex headvex hlinktlinkinfodatafirstin firstout弧的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置弧尾頂點(diǎn)位置 弧頭頂點(diǎn)位置弧頭頂點(diǎn)位置 弧的相關(guān)信息弧的相關(guān)信息指向下一個有相有相同弧尾同弧尾的結(jié)點(diǎn)指向下一個有相有相同弧頭同弧頭的結(jié)點(diǎn)typedef struct ArcBox / 弧弧的結(jié)構(gòu)表示的結(jié)構(gòu)表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;頂點(diǎn)的結(jié)點(diǎn)結(jié)

16、構(gòu)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù)頂點(diǎn)信息數(shù)據(jù) 指向該頂點(diǎn)的第一條入弧第一條入弧指向該頂點(diǎn)的第一條出弧第一條出弧typedef struct VexNode / 頂點(diǎn)的結(jié)構(gòu)表示頂點(diǎn)的結(jié)構(gòu)表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)(表頭向量表頭向量) int vexnum, arcnum; /有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph;有向圖的結(jié)構(gòu)表示有向圖的結(jié)構(gòu)表示(十字鏈表十字鏈表)V1V2V4V5V

17、30V11V22V33V44V5010321234124mark ivex ilink jvex jlink info頂點(diǎn)頂點(diǎn) i 的度的度?多少邊節(jié)點(diǎn)多少邊節(jié)點(diǎn)?typedef struct Ebox VisitIf mark; / 訪問標(biāo)記訪問標(biāo)記 int ivex, jvex; /該邊依附的兩個頂點(diǎn)的位置該邊依附的兩個頂點(diǎn)的位置 struct EBox *ilink, *jlink; InfoType *info; / 該邊信息指針該邊信息指針 EBox;邊的結(jié)構(gòu)表示邊的結(jié)構(gòu)表示mark ivex ilink jvex jlink infotypedef struct / 鄰接多重表鄰接

18、多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;頂點(diǎn)的結(jié)構(gòu)表示頂點(diǎn)的結(jié)構(gòu)表示typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一條依附的邊指向第一條依附的邊 VexBox;無向圖的結(jié)構(gòu)表示無向圖的結(jié)構(gòu)表示 圖的遍歷：從圖中某個頂點(diǎn)出發(fā)游歷圖，訪遍圖中圖的遍歷：從圖中某個頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個頂點(diǎn)僅被訪問一次的其余頂點(diǎn)，并且使圖中的每個頂點(diǎn)僅被訪問一次的過程過程 由于圖中可能有環(huán)，所以設(shè)置數(shù)組由于圖中可能有環(huán)，所以

19、設(shè)置數(shù)組visited0,n 7.3.1 深度優(yōu)先搜索深度優(yōu)先搜索 7.3.2 廣度優(yōu)先搜索廣度優(yōu)先搜索 7.3.3 遍歷應(yīng)用舉例遍歷應(yīng)用舉例 連通圖的遍歷連通圖的遍歷 深度優(yōu)先遍歷連通圖的過程類似于樹的先根遍歷深度優(yōu)先遍歷連通圖的過程類似于樹的先根遍歷 從圖中某個頂點(diǎn)從圖中某個頂點(diǎn)V 出發(fā)，訪問此頂點(diǎn)，然后出發(fā)，訪問此頂點(diǎn)，然后依次從依次從V的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和直至圖中所有和V有路徑相通的頂點(diǎn)都被訪問到有路徑相通的頂點(diǎn)都被訪問到V1V2V3V4V5V6V7V8訪問頂點(diǎn)訪問頂點(diǎn) V ：for (W1、W2、W3

20、 ) 若若該鄰接點(diǎn)該鄰接點(diǎn)Wi未被訪問未被訪問， 則則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。Vw1SG1SG2SG3w2w3w2void DFS(Graph G, int v, void (* visit)(VertexType) / 從頂點(diǎn)從頂點(diǎn)v出發(fā)，出發(fā)，深度優(yōu)先搜索遍歷連通圖深度優(yōu)先搜索遍歷連通圖 G / DFSvisitedv = TRUE; visit(v);for(w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G,v,w) / 對對v的尚未訪問的鄰接頂點(diǎn)的尚未訪問的鄰接頂點(diǎn)w，遞歸調(diào)用遞歸調(diào)用DFS if (!visite

21、dw) DFS(G, w, visit); 非連通圖的深度優(yōu)先搜索遍歷非連通圖的深度優(yōu)先搜索遍歷 1) 將圖中每個頂點(diǎn)的訪問標(biāo)志設(shè)為將圖中每個頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE 2) 搜索圖中每個頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)搜索圖中每個頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷 否則繼續(xù)檢查下一頂點(diǎn)否則繼續(xù)檢查下一頂點(diǎn)void DFSTraverse(Graph G, void (*visit)(VertexType) / 對圖對圖 G 作深度優(yōu)先遍歷。作深度優(yōu)先遍歷。 / DFSTraversefor (v=0; vG.vexnum; +v) /

22、初始化標(biāo)志數(shù)組初始化標(biāo)志數(shù)組 visitedv = FALSE; / 對尚未訪問的頂點(diǎn)調(diào)用對尚未訪問的頂點(diǎn)調(diào)用DFSfor (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v, visit);v0v1v2v6v3v4v7v5v80263 574 18訪問次序訪問次序: : 類似樹的廣度優(yōu)先遍歷類似樹的廣度優(yōu)先遍歷 圖中某頂點(diǎn)圖中某頂點(diǎn)v出發(fā)：出發(fā)： 1）訪問頂點(diǎn)）訪問頂點(diǎn)v ； 2）訪問）訪問v所有未被訪問的鄰接點(diǎn)所有未被訪問的鄰接點(diǎn)w1,w2,wk； 3）依次從這些鄰接點(diǎn)出發(fā)，訪問其所有未被訪問）依次從這些鄰接點(diǎn)出發(fā)，訪問其所有未被訪問的鄰接點(diǎn)。的鄰接點(diǎn)

23、。 依此類推，直到圖中所有訪問過的頂點(diǎn)依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問的鄰接點(diǎn)都被訪問 借用隊(duì)列暫存節(jié)點(diǎn)借用隊(duì)列暫存節(jié)點(diǎn)V1V2V3V4V5V6V7V8void BFS(Graph G, VexIndex v, void (*visit)(VertexType) ) /從第從第v個頂點(diǎn)出發(fā)，廣度優(yōu)先遍歷個頂點(diǎn)出發(fā)，廣度優(yōu)先遍歷G,使用輔助隊(duì)列使用輔助隊(duì)列Q。 InitQueue(Q); /建空隊(duì)列建空隊(duì)列Q EnQueue(Q,v) /訪問訪問v,v入隊(duì)入隊(duì)/BFSwhile(!QueueEmpty(Q) DeQueue(Q,u); /隊(duì)頭元素出隊(duì)隊(duì)頭元素出隊(duì),并賦值給并賦值

24、給u visit(u) ;visitedu=TRUE; /訪問訪問u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if(!visitedw) EnQueue(Q,w); /whileQV1V1V2V2V3V3V4V4V8V8V5V5V6V6V7V7V2V2 V3V3 V4V4V1V1V8V8 V5V5 V6V6 V7V7 V1V1 V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2入隊(duì)列入隊(duì)列出出隊(duì)隊(duì)列列void BFSTraverse(Graph G, void (*visit)(VertexType) / 對圖對圖 G 作深度

25、優(yōu)先遍歷。作深度優(yōu)先遍歷。/ BFSTraversefor (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標(biāo)志數(shù)組初始化訪問標(biāo)志數(shù)組初始化/ 對尚未訪問的頂點(diǎn)調(diào)用對尚未訪問的頂點(diǎn)調(diào)用DFSfor (v=0; vG.vexnum; +v) if (!visitedv) BFS(G, v, visit); 求一條從頂點(diǎn)求一條從頂點(diǎn) i 到頂點(diǎn)到頂點(diǎn) s 的簡單路徑的簡單路徑Status DFSearch(Graph G, VertexType v, VertexType s, SqList &PATH) /從從v開始深度優(yōu)先搜索，找到開始深度優(yōu)先搜索，找到s為止為止 v1 = LocateVex(G, v);/找到找到v if ( v1 = -1) return FALSE; for (i=0; iG.vexnum; +i) visitedi = FALSE; / 訪問標(biāo)志數(shù)組初始化訪問標(biāo)志數(shù)組初始化 InitList_Sq(PATH); return _DFSearch(G, v1