上堂課要點(diǎn)回顧,樹的應(yīng)用 等價(jià)問題 等價(jià)關(guān)系、等價(jià)類的定義 并查集ADT 并查集實(shí)現(xiàn) 數(shù)組表示法 鏈表表示法及改進(jìn) 森林表示法及改進(jìn),第 十三 次 課,閱讀： 朱戰(zhàn)立，第209-223頁 習(xí)題： 作業(yè)12,數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容,Chapter 9 圖,9.1 圖的定義及ADT 9.2-3 存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn) 9.4 圖的遍歷 深度優(yōu)先搜索 廣度優(yōu)先搜索 應(yīng)用：9.7 拓?fù)渑判?9.5 最小生成樹 prim算法 kruskul算法,9.6 最短路徑 dijkstra算法 floyd算法 9.8 關(guān)鍵路徑,圖的應(yīng)用領(lǐng)域,電路網(wǎng)絡(luò)分析 交通運(yùn)輸管理 線路的鋪設(shè) 印刷電路板與集成電路的布線 工作的分配 工程進(jìn)度的安排 課程表的制訂 關(guān)系數(shù)據(jù)庫的設(shè)計(jì),9.1 圖的定義及抽象數(shù)據(jù)類型,9.1.1 圖(graph)的基本概念 定義 圖G由兩個(gè)集合V(G)和E(G)所組成，記作 G=(V, E)。 其中，V(G)是圖中頂點(diǎn)vertex(即圖的數(shù)據(jù)元素) 的有限集合， E(G)是圖中邊edge(即兩個(gè)頂點(diǎn)之間的關(guān) 系)的有限集合。,分類 (1) 有向圖(directed graph)：每條邊是頂點(diǎn)的有序偶對(duì) 有向圖中的邊也稱為弧。用尖括號(hào)表示頂點(diǎn) 的有序?qū)Γ?，vi稱為弧尾，vj稱為弧頭，并 稱它們互為鄰接點(diǎn)(adjacent)。 例：,V(G1)=V1,V2,V3, E(G1)=, ,(2) 無向圖(undirected graph)：每條邊是頂點(diǎn)的無序偶對(duì)。用圓括號(hào)表示頂點(diǎn)的無序?qū)?，如（Vi,Vj），其中Vi和Vj為此邊的起點(diǎn)和終點(diǎn)，并稱它們互為鄰接點(diǎn)(adjacent)。 例：,V(G2)=V1, V2, V3, V4 E(G2)=(V1, V2), (V1, V3), (V1, V4), (V2, V3), (V2, V4), (V3, V4),樹圖,無向完全圖，有向完全圖 設(shè)n為圖的頂點(diǎn)數(shù)，e為邊或弧的數(shù)目，假設(shè)不考 慮頂點(diǎn)到其自身的邊或弧。,具有n個(gè)頂點(diǎn)、n(n-1)條邊的有向圖，稱為有向完全圖(directed complete graph) 。,具有n個(gè)頂點(diǎn)、 條邊的無向圖，稱為無向完全圖(undirected complete graph)。,當(dāng)一個(gè)圖接近完全圖時(shí)，則稱它為稠密圖(dense graph)，相反地，當(dāng)一個(gè)圖中含有較少的邊或弧時(shí)，則稱它為稀疏圖(sparse graph)。,網(wǎng) 若圖的邊或弧上附帶有數(shù)據(jù)信息,這些附帶的數(shù)據(jù)信息稱為稱為權(quán)。 這種帶權(quán)的圖(weighted graph)稱作網(wǎng)。,子圖 假設(shè)有兩個(gè)圖G和G，且滿足條件： V(G)V(G)，E(G) E(G)，則稱G是G的子圖。 例： G1的一些子圖：,G1的一些子圖,G2的一些子圖：,G2的子圖,度、入度和出度 (1) 度(無向圖中) 頂點(diǎn)vi的度(total degree) ：是和vi相關(guān)聯(lián)的邊的 數(shù)目，記作TD(vi)。 (2) 入度、出度、度(有向圖中) 頂點(diǎn)vi的入度(in degree)：是以頂點(diǎn)vi為頭(終端 點(diǎn))的弧的數(shù)目，記作ID(vi)。 頂點(diǎn)vi的出度(out degree)：是以頂點(diǎn)vi為尾(初始 點(diǎn))的弧的數(shù)目，記作OD(vi)。 頂點(diǎn)vi的度(total degree)：入度和出度之和。 即TD(vi)=ID(vi)+OD(vi),路徑、回路 (1) 路徑(path) 在無向圖G中，從頂點(diǎn)vp到頂點(diǎn)vq的一條路徑是 頂點(diǎn)的序列(vp,vi1,vi2, vin,vq)，且 (vp,vi1), (vi1,vi2), , (vin,vq)都是E(G)中的邊。 路徑上邊的數(shù)目稱為該路徑的長(zhǎng)度(length) 。 對(duì)于有向圖，其路徑也是有向的，其頂點(diǎn)序列 為，且, , , 都是E(G)中的弧。 路徑上弧的數(shù)目稱為該路徑的長(zhǎng)度。,(2) 回路( cycle, 環(huán)) 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為 回路或環(huán)。 簡(jiǎn)單路徑(simple path)：序列中各頂點(diǎn)不重復(fù)出現(xiàn)的路徑。 簡(jiǎn)單回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的簡(jiǎn)單 路徑稱為簡(jiǎn)單回路(simple cycle)。 例：圖G2中， (v1, v2, v4, v3)是一條簡(jiǎn)單路徑； (v1, v2, v4, v3 , v1)是一條簡(jiǎn)單回路； (v1, v2, v4, v3 , v2 , v1)是一條回路。,連通圖、強(qiáng)連通圖和生成樹 (1) 在無向圖G中，若V(G)中的每一對(duì)不同的頂點(diǎn)vi和vj都是連通的，則稱G為連通圖(connected graph)。 在無向圖G中，最大的連通子圖稱為G的連通分量(connect compoent)。 例：,的連通分量：,的連通分量：,(2) 在有向圖G中，若對(duì)于V(G)中每一對(duì)不同頂點(diǎn)vi和 vj 之間，都存在從vi到vj以及從vj到vi的路徑，則稱 G為強(qiáng)連通圖。 有向圖中最大的強(qiáng)連通子圖稱為它的強(qiáng)連通分量。 例：,的強(qiáng)連通分量：,(1),(2),(3) 生成樹 一個(gè)連通圖的極小連通子圖稱作該圖的生成樹，它含有圖中全部頂點(diǎn)n，但只有足以構(gòu)成一棵樹的n-1條邊。 例：圖G2的一棵生成樹為：,9.1.2 圖的抽象數(shù)據(jù)類型 ADT Graph 數(shù)據(jù)：由一個(gè)結(jié)點(diǎn)集合Vi和一個(gè)邊集合ej組成，網(wǎng)則還 有一個(gè)權(quán)集合Wi 。 操作：設(shè)G為 Graph 型 GraphInitiate(G) /初始化圖G； IsVertex(G,vertex) /判斷vertex是否是圖G的頂點(diǎn)； InsertVertex(G, vertex) /在圖G中插入頂點(diǎn)vertex； IsEdge(G,v1,v2) /判斷邊是否是圖G的邊； InsertEdge(G,v1,v2,weight) /*在圖G中插入邊，邊 的權(quán)值為weight ；*/ DeleteEdge(G,v1,v2) /在圖G中刪除邊； DeleteVertex(G, v) /*在圖G中刪除第v個(gè)頂點(diǎn)以及與 該頂點(diǎn)相關(guān)的所有邊；*/ Degree(G,v) /計(jì)算圖G中第v個(gè)頂點(diǎn)的度； GetFirstVex(G,v) /在圖G尋找第v個(gè)頂點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)； GetNextVex(G,v1,v2) /*在圖G中尋找頂點(diǎn)v1的鄰接頂點(diǎn)v2 的下一個(gè)鄰接頂點(diǎn)；*/ Traverse(G,Visit) /遍歷圖G。,9.2 圖的存儲(chǔ)結(jié)構(gòu),9.2.1 鄰接矩陣(adjecency matrix) 9.2.2 鄰接表(adjecency list),9.2 圖的存儲(chǔ)結(jié)構(gòu),9.2.1 鄰接矩陣(adjecency matrix) 定義 表達(dá)頂點(diǎn)間的相鄰關(guān)系的矩陣。設(shè)G=(V，E)是有n(n0)個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是按如下定義的n階方陣A， 鄰接矩陣的空間代價(jià)是O(n2),例：,特征 (1) 無向圖 對(duì)稱矩陣 存儲(chǔ)量：n(n+1)/2 頂點(diǎn)的度數(shù)：TD(Vi)=,(2) 有向圖 不一定是對(duì)稱矩陣 存儲(chǔ)量：n2 頂點(diǎn)的度數(shù)：ID(Vi)=,OD(Vi)=,(3) 適合稠密圖（e n2 ）,(4) 容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。,網(wǎng)的鄰接矩陣 定義：,aij =,wij，若(vi,vj)或E(G),， 否則且ij,例：,0， 否則且i=j,描述： #define MaxVertices typedef struct SeqList Vertices; /*頂點(diǎn)*/ int edgeMaxVerticesMaxVertices; /*邊*/ int numOfEdges; /*邊數(shù)*/ AdjMGraph;,9.3.1 鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的實(shí)現(xiàn)（AdjMGraph.h）,GraphInitiate(G) InsertVertex(G,vertex) InsertEdge(G,v1,v2,weight) DeleteEdge(G,v1,v2) DeleteVertex(G,v) GetFirstVex(G,v) GetNextVex(G,v1,v2),基本操作的實(shí)現(xiàn)：P214-218,void GraphInitiate(AdjMGraph *G) /初始化帶權(quán)有向圖G int i, j; for(i = 0; i edgeij = 0; else G-edgeij = MaxWeight; /無窮大 G-numOfEdges = 0; /*邊的條數(shù)置為0*/ ListInitiate(/*頂點(diǎn)順序表初始化*/ /時(shí)間復(fù)雜度：O(1),int IsVertex(AdjMGraph *G,DataType vertex) /*判斷頂點(diǎn)vertex是否是有向圖G的頂點(diǎn)，是則返回頂點(diǎn)在頂點(diǎn)順序表中的序號(hào)，否則返回-1。*/ int i; for (i=0;iVertices.size;i+) if(G-Vertices.listi=vertex) break; if (i=G-Vertices.size) return -1; else return i; /時(shí)間復(fù)雜度O(n),void InsertVertex(AdjMGraph *G, DataType vertex) /*在帶權(quán)有向圖G中插入頂點(diǎn)vertex。如果圖中已經(jīng)有頂點(diǎn)vertex，則圖不變。*/ if(IsVertex(G,vertex)Vertices, G-Vertices.size,vertex)=0) printf(“插入頂點(diǎn)時(shí)“); exit(1); /時(shí)間復(fù)雜度：O(n),void InsertEdge(AdjMGraph *G, int v1, int v2, int weight) /* 在帶權(quán)有向圖G中插入一條第v1個(gè)頂點(diǎn)指向第v2個(gè)頂點(diǎn)，權(quán)值為weight的有向邊。如果v1和v2有一個(gè)不是圖中的頂點(diǎn)，則圖不變；如果v1和v2相等，則圖不變。如果圖已經(jīng)包含該邊，則邊的權(quán)值更改為新的權(quán)值。*/ DataType x; if(v1!=v2) if(ListGet(G-Vertices,v1, /時(shí)間復(fù)雜度:O(1),int IsEdge(AdjMGraph *G,int v1,int v2) /*判斷第v1個(gè)頂點(diǎn)到第v2個(gè)頂點(diǎn)的邊是否是有向圖G的邊，是則返回1，否則返回0。 */ DataType x; if(ListGet(G-Vertices,v1, /時(shí)間復(fù)雜度O(1),void DeleteEdge(AdjMGraph *G,int v1,int v2) /* 在帶權(quán)有向圖G中刪除一條第v1個(gè)頂點(diǎn)指向第v2個(gè)頂點(diǎn)的有向邊。如果v1和v2有一個(gè)不是圖中的頂點(diǎn)，則圖不變；如果v1和v2相等，則圖不變。如果不是圖的邊，則圖不變。 */ if (IsEdge(G,v1,v2)=0) printf(“刪除邊時(shí)出錯(cuò)！“); exit(1); else G-edgev1v2=MaxWeight; G-numOfEdges-; /時(shí)間復(fù)雜度:O(1),int GetFirstVex(AdjMGraph G, int v) /*在帶權(quán)有向圖G中取第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)，如果這樣的鄰接頂點(diǎn)存在，則返回該頂點(diǎn)在頂點(diǎn)順序表的序號(hào)，否則返回-1。*/ int col;DataType x; if(ListGet(G.Vertices,v, /時(shí)間復(fù)雜度：O(n),int GetNextVex(AdjMGraph G, int v1, int v2) /*在帶權(quán)有向圖G中取第v1個(gè)頂點(diǎn)的繼鄰接結(jié)點(diǎn)第v2個(gè)頂點(diǎn)之后的下一個(gè)鄰接結(jié)點(diǎn)。*/ int col;DataType x; if(ListGet(G.Vertices,v1, /時(shí)間復(fù)雜度:O(n),void GraphCreat(AdjMGraph *G,DataType v,int n,RowColWeight W,int e) /*創(chuàng)建有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖G。*/ int i,k; GraphInitiate(G); for(i=0;in;i+) InsertVertex(G,vi); for(k=0;ke;k+) InsertEdge(G,Wk.row,Wk.col,Wk.weight); /時(shí)間復(fù)雜度:O(n2+e),typedef struct int row; /行下標(biāo) int col; /列下標(biāo) int weight; /權(quán)值 RowColWeight;/邊信息,9.2.2 鄰接表(adjecency list) 定義：在鄰接表中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單 鏈表。 無向圖：第i個(gè)鏈表中的結(jié)點(diǎn)表示了依附于頂點(diǎn)Vi 的邊。 有向圖：第i個(gè)鏈表中的結(jié)點(diǎn)就表示了從Vi 發(fā)出的 所有的弧(以Vi為尾的弧)。 邊結(jié)點(diǎn)：,weight,next,dest,鄰接點(diǎn)域,鏈域,權(quán)值域,頭結(jié)點(diǎn)：,例：,例：,特征 (1) 若無向圖G有n個(gè)頂點(diǎn)，e條邊，則鄰接表需n個(gè)表頭結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)；若有向圖G有n個(gè)頂點(diǎn)，e條邊，則鄰接表需n個(gè)表頭結(jié)點(diǎn)和e個(gè)邊結(jié)點(diǎn)?？臻g利用率高。. (2) 無向圖：第i個(gè)鏈表中的表結(jié)點(diǎn)數(shù)為TD(vi)； 有向圖：第i個(gè)鏈表中的表結(jié)點(diǎn)數(shù)為OD(vi)，不能求ID(vi) 。為便于求ID(vi) 可另外建立有向圖的逆鄰接表。,(4) 鄰接表多用于稀疏圖的存儲(chǔ)（en2),(3) 容易尋找頂點(diǎn)的鄰接點(diǎn)，但判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表。,描述： #de