1、ABCDEABCDE 7.1 抽象數據類型圖的定義抽象數據類型圖的定義 7.2 圖的存儲表示圖的存儲表示 7.3 圖的遍歷圖的遍歷 7.4 最小生成樹最小生成樹 7.5 重（雙）連通圖和關節點重（雙）連通圖和關節點 7.6 兩點之間的最短路徑問題兩點之間的最短路徑問題 7.7 拓撲排序拓撲排序 7.8 關鍵路徑關鍵路徑 7.1.1 圖的定義圖的定義 圖圖(Graph)是由一個是由一個頂點頂點(Vertex)集集 V 和一個和一個弧弧(Arc)集集 R構成的數據結構。構成的數據結構。 Graph = (V , R ) 其中其中 R| v,wV 且且 P(v,w) 表示從表示從 v 到到 w 的一

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

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

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

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

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

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

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

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

10、儲表示無向圖的鄰接多重表存儲表示 定義定義:矩陣的元素為矩陣的元素為BACDFEVRjiVRjiAij),( 1),(0頂點頂點i 的度？的度？第第 i 行行 (列列) 1 的個數。的個數。有向圖的鄰接矩陣為非對稱矩陣有向圖的鄰接矩陣為非對稱矩陣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是頂點關系類型。是頂點關系類型。 / 對無權圖，用對無權圖，用1或或0表示相鄰否；表示相鄰否； / 對帶權圖，則為權值類型。對帶權圖，則為權值類型

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

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

13、/ 該弧所指向的頂點的位置該弧所指向的頂點的位置 struct ArcNode *nextarc; / 指向下一條弧的指針指向下一條弧的指針 InfoType *info; / 該弧相關信息的指針該弧相關信息的指針 ArcNode;頂點頂點的結點結構的結點結構 data firstarctypedef struct VNode VertexType data; / 頂點信息頂點信息 ArcNode *firstarc; / 指向第一條依附該頂點的弧指向第一條依附該頂點的弧 VNode, AdjListMAX_VERTEX_NUM;圖的圖的結構定義結構定義typedef struct AdjLi

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

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

16、構頂點的結點結構頂點信息數據頂點信息數據 指向該頂點的第一條入弧第一條入弧指向該頂點的第一條出弧第一條出弧typedef struct VexNode / 頂點的結構表示頂點的結構表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 頂點結點頂點結點(表頭向量表頭向量) int vexnum, arcnum; /有向圖的當前頂點數和弧數有向圖的當前頂點數和弧數 OLGraph;有向圖的結構表示有向圖的結構表示(十字鏈表十字鏈表)V1V2V4V5V

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

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

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

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

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

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

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

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入隊列入隊列出出隊隊列列void BFSTraverse(Graph G, void (*visit)(VertexType) / 對圖對圖 G 作深度

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