數(shù)據(jù)結(jié)構(gòu)課件：1-圖的ADT和物理實(shí)現(xiàn)

1、1第第1111章章 圖圖數(shù)據(jù)結(jié)構(gòu)與算法分析23456圖的應(yīng)用 為計(jì)算機(jī)與通信網(wǎng)絡(luò)的互連建模為計(jì)算機(jī)與通信網(wǎng)絡(luò)的互連建模 把一張地圖表示為一組位置以及位置之間的距離，把一張地圖表示為一組位置以及位置之間的距離，以求得位置之間得最短路徑以求得位置之間得最短路徑 為網(wǎng)絡(luò)的流量能力建模為網(wǎng)絡(luò)的流量能力建模 尋找從開始狀態(tài)到目標(biāo)狀態(tài)得路徑，如人工智能問(wèn)尋找從開始狀態(tài)到目標(biāo)狀態(tài)得路徑，如人工智能問(wèn)題的求解題的求解 為計(jì)算機(jī)算法建模，顯示程序狀態(tài)的變化為計(jì)算機(jī)算法建模，顯示程序狀態(tài)的變化 為復(fù)雜活動(dòng)各子任務(wù)的完成尋找較優(yōu)順序，如大型為復(fù)雜活動(dòng)各子任務(wù)的完成尋找較優(yōu)順序，如大型建筑的建造建筑的建造 為家族、商

2、業(yè)或軍事組織和自然科學(xué)分類中的各種為家族、商業(yè)或軍事組織和自然科學(xué)分類中的各種關(guān)系建模關(guān)系建模7網(wǎng)型結(jié)構(gòu)小節(jié) 客觀世界客觀世界中廣泛存在網(wǎng)狀結(jié)構(gòu)中廣泛存在網(wǎng)狀結(jié)構(gòu) 圖結(jié)構(gòu)也在圖結(jié)構(gòu)也在計(jì)算科學(xué)領(lǐng)域計(jì)算科學(xué)領(lǐng)域中被廣泛的中被廣泛的（創(chuàng)造和）應(yīng)用（創(chuàng)造和）應(yīng)用以上各例的數(shù)據(jù)(信息)組織形式，均稱為網(wǎng)狀結(jié)構(gòu)。8圖的定義和基本術(shù)語(yǔ)9圖Graphs圖可以用 G = (V, E) 來(lái)表示來(lái)表示,每個(gè)圖都包括一每個(gè)圖都包括一個(gè)頂點(diǎn)集個(gè)頂點(diǎn)集(vertices) V, 和一個(gè)邊集合和一個(gè)邊集合(edges) E, 其中其中E中的每條邊都是 V 中某一對(duì)頂點(diǎn)之間的連接.頂點(diǎn)總數(shù)記為頂點(diǎn)總數(shù)記為 |V|, 邊的總

3、數(shù)記為邊的總數(shù)記為 |E|.10圖Graphs 如果圖中的邊限定為從一個(gè)頂點(diǎn)指向另一個(gè)頂點(diǎn), 則此圖稱為有向圖(directed graph或digraph)。如果圖中的邊沒(méi)有方向, 則稱之為無(wú)向圖(undirected graph)。如果圖中各頂點(diǎn)均帶有標(biāo)號(hào), 則稱之為標(biāo)號(hào)圖(labeled graph)。 一條邊所連接的兩個(gè)頂點(diǎn)是相鄰的(adjacent), 稱為鄰接點(diǎn)(neighbors)。連接一對(duì)鄰接點(diǎn)u、v的邊被稱為與頂點(diǎn)u、v相關(guān)聯(lián)(incident)的邊, 記作(u,v)。每條邊都可能附有值或權(quán)(weight)。邊上標(biāo)有權(quán)的圖稱為帶權(quán)圖(weighted graph)11頂點(diǎn)的度

4、 在無(wú)向圖中，與頂點(diǎn)vi(viV(G)相關(guān)聯(lián)的邊的條數(shù)稱為vi的度，記為TD(vi) 在有向圖中，頂點(diǎn)的度為頂點(diǎn)的入度、出度之和 入度等于以vi為頭的弧的數(shù)目 出度等于以vi為尾的弧的數(shù)目1( )2nii ieTD v=n為圖G的頂點(diǎn)數(shù)12路徑Paths 和回路 Cycles路徑路徑: 如果頂點(diǎn)序列如果頂點(diǎn)序列 v1, v2, , vn 從從 vi 到到 vi+1 (1 = i n) 的邊均存在，則稱頂點(diǎn)序列的邊均存在，則稱頂點(diǎn)序列v1, v2, , vn 構(gòu)構(gòu)成一條長(zhǎng)度為成一條長(zhǎng)度為 n-1 的路徑的路徑(path).如果路徑上的各個(gè)頂點(diǎn)都不同，則稱這個(gè)路徑為如果路徑上的各個(gè)頂點(diǎn)都不同，則稱

5、這個(gè)路徑為簡(jiǎn)簡(jiǎn)單路徑單路徑(simple path).一條路徑將某個(gè)頂點(diǎn)一條路徑將某個(gè)頂點(diǎn)vi 連接到它本身，且其長(zhǎng)度大連接到它本身，且其長(zhǎng)度大于或等于于或等于3，則稱此路徑為，則稱此路徑為回路回路(cycle).如果構(gòu)成回路的路徑是簡(jiǎn)單路徑如果構(gòu)成回路的路徑是簡(jiǎn)單路徑,除了首尾兩個(gè)頂點(diǎn)除了首尾兩個(gè)頂點(diǎn)相同以外其他頂點(diǎn)均不同相同以外其他頂點(diǎn)均不同,則稱此回路為則稱此回路為簡(jiǎn)單回路簡(jiǎn)單回路(simple cycle).13圖 (2)14子圖 子圖(subgraph)S是指由圖G中選出其頂點(diǎn)集的一個(gè)子集VS以及與VS中頂點(diǎn)相關(guān)聯(lián)的一些邊所構(gòu)成的圖15連通分量Connected Components

6、如果一個(gè)無(wú)向圖中任意一個(gè)頂點(diǎn)到其他任意如果一個(gè)無(wú)向圖中任意一個(gè)頂點(diǎn)到其他任意頂點(diǎn)都至少存在一條路徑頂點(diǎn)都至少存在一條路徑, 則稱此無(wú)向圖為則稱此無(wú)向圖為連通的連通的(connected).無(wú)向圖的無(wú)向圖的極大極大連通子圖稱為連通子圖稱為連通分量連通分量(connected component).16無(wú)環(huán)圖 和 有向無(wú)環(huán)圖 不帶回路的圖稱為無(wú)環(huán)圖(acyclic graph) 不帶回路的有向圖稱為有向無(wú)環(huán)圖(directed acyclic graph或DAG) 一棵自由樹(free tree)就是一個(gè)不帶有簡(jiǎn)單回路的無(wú)向圖, 它是連通的, 且有|V|-1條邊17對(duì)比對(duì)比網(wǎng)型結(jié)構(gòu)網(wǎng)型結(jié)構(gòu)和和樹型

7、結(jié)構(gòu)樹型結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn)18網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無(wú)前驅(qū)無(wú)前驅(qū)) )多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無(wú)后繼無(wú)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) ) 所有的結(jié)點(diǎn)的所有的結(jié)點(diǎn)的特征一致特征一致 ( (頂點(diǎn)頂點(diǎn)) )結(jié)點(diǎn)可以和結(jié)點(diǎn)可以和多個(gè)的其它結(jié)點(diǎn)多個(gè)的其它結(jié)點(diǎn) 關(guān)聯(lián)關(guān)聯(lián) ( (邊邊) )19圖的ADT20 圖圖是由一個(gè)是由一個(gè)頂點(diǎn)集頂點(diǎn)集 V 和一個(gè)和一個(gè)弧集弧集 R構(gòu)成構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V , R )其中，VR| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱 v

8、 為弧頭弧頭，w 為弧尾弧尾。 謂詞 P(v,w) 定義了弧 的意義或信息。圖的ADT定義21Graph ADTclass Graph / Graph abstract classpublic: virtual int n() =0; / # of vertices virtual int e() =0; / # of edges / Return index of first, next neighbor virtual int first(int) =0; virtual int next(int, int) =0; / Store new edge virtual void setEdg

9、e(int, int, int) =0; / Delete edge defined by two vertices virtual void delEdge(int, int) =0; / Weight of edge connecting two vertices virtual int weight(int, int) =0; virtual int getMark(int) =0; virtual void setMark(int, int) =0;22結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問(wèn)操作對(duì)頂點(diǎn)的訪問(wèn)操作遍歷遍歷插入和

10、刪除弧插入和刪除弧圖的ADT定義（2）23CreatGraph(&G, V, VR): / 按定義(V, VR) 構(gòu)造圖DestroyGraph(&G): / 銷毀圖結(jié)構(gòu)的建立和銷毀24對(duì)頂點(diǎn)的訪問(wèn)操作LocateVex(G, u); / 若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在 / 圖中“位置位置” ；否則返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 對(duì) v 賦值value。25對(duì)鄰接點(diǎn)的操作FirstAdjVex(G, v); / 返回 v 的“第一個(gè)鄰接點(diǎn)第一個(gè)鄰接點(diǎn)” 。若該頂點(diǎn)/在 G 中沒(méi)有鄰接點(diǎn)，則返

11、回“空”。NextAdjVex(G, v, w); / 返回 v 的（相對(duì)于 w 的） “下一個(gè)鄰接下一個(gè)鄰接/ 點(diǎn)點(diǎn)”。若 w 是 v 的最后一個(gè)鄰接點(diǎn)，則/ 返回“空”。26插入或刪除頂點(diǎn)InsertVex(&G, v); /在圖G中增添新頂點(diǎn)v。DeleteVex(&G, v); / 刪除G中頂點(diǎn)v及其相關(guān)的弧。27插入和刪除弧InsertArc(&G, v, w); / 在G中增添弧，若G是無(wú)向的， /則還增添對(duì)稱弧。DeleteArc(&G, v, w); /在G中刪除弧，若G是無(wú)向的， /則還刪除對(duì)稱弧。28遍 歷DFSTraverse(G, v,

12、Visit(); /從頂點(diǎn)v起深度優(yōu)先深度優(yōu)先遍歷圖G，并對(duì)每/個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G, v, Visit(); /從頂點(diǎn)v起廣度優(yōu)先廣度優(yōu)先遍歷圖G，并對(duì)每/個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。29圖的實(shí)現(xiàn)（物理數(shù)據(jù)結(jié)構(gòu)）30圖 的表示法 鄰接矩陣(adjacency matrix)表示法 圖的鄰接矩陣是一個(gè)|V|V|矩陣。 如果從vi到vj存在一條邊, 則對(duì)第i行的第j個(gè)元素做標(biāo)記, 否則不做標(biāo)記 鄰接矩陣的空間代價(jià)為(|V|2) 鄰接表(adjacency list)表示法 鄰接表是一個(gè)以鏈表為元素的數(shù)組。該數(shù)組包含|V|個(gè)元素, 其中第i個(gè)元

13、素存儲(chǔ)的是指向頂點(diǎn)vi的鏈表的指針, 這個(gè)鏈表是由頂點(diǎn)vi的鄰接點(diǎn)構(gòu)成 鄰接表的空間代價(jià)為(|V|+|E|)31有向圖的表示法32無(wú)向圖的表示法33表示法的空間代價(jià)Adjacency Matrix鄰接矩陣鄰接矩陣:Adjacency List鄰接鏈表鄰接鏈表:哪種表示法存儲(chǔ)效率更高取決于圖中邊的數(shù)哪種表示法存儲(chǔ)效率更高取決于圖中邊的數(shù)目目34十字鏈表 十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu). . 可以看成將有向圖的鄰接表和逆鄰接表結(jié)合可以看成將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表起來(lái)得到的一種鏈表. . 在十字鏈表中，對(duì)應(yīng)于有向圖中每一條弧有在十字鏈

14、表中，對(duì)應(yīng)于有向圖中每一條弧有一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)于每個(gè)頂點(diǎn)也有一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)于每個(gè)頂點(diǎn)也有一個(gè)結(jié)點(diǎn). .V1V2V3V4V1V2V3V4012320303132230102datafirstinfirstouttailvexheadvexhlinktlinkinfo35鄰接多重表 鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在鄰接表中每一條邊（在鄰接表中每一條邊（vi，vj）有兩個(gè)結(jié)點(diǎn)，分別在第有兩個(gè)結(jié)點(diǎn)，分別在第i個(gè)和第個(gè)和第j個(gè)鏈表中，這給某些圖的操作帶來(lái)不便個(gè)鏈表中，這給某些圖的操作帶來(lái)不便 在鄰接多重表中，每一條邊用一個(gè)結(jié)點(diǎn)表示，每一個(gè)在鄰接多重表

15、中，每一條邊用一個(gè)結(jié)點(diǎn)表示，每一個(gè)頂點(diǎn)也用一個(gè)結(jié)點(diǎn)表示頂點(diǎn)也用一個(gè)結(jié)點(diǎn)表示36相鄰矩陣實(shí)現(xiàn)（1）class Graphm : public Graph /Implement adjacency matrixprivate: int numVertex, numEdge;/Store number of vertices edges int *matrix; / Pointer to adjacency matrix int *mark; / Pointer to mark arraypublic: Graphm(int numVert) / Make graph w/ numVert vert

16、ices int i, j; numVertex = numVert; numEdge = 0; mark = new intnumVert; / Initialize mark array for (i=0; inumVertex; i+) marki = UNVISITED; matrix = (int*) new int*numVertex; / Make matrix for (i=0; inumVertex; i+) matrixi = new intnumVertex; for (i=0; i numVertex; i+)/Edges start w/0 weight for (i

17、nt j=0; jnumVertex; j+) matrixij = 0; 37相鄰矩陣實(shí)現(xiàn)（2）int first(int v)/ Return vs first neighbor int i; for (i=0; inumVertex; i+) if (matrixvi != 0) return i; return i; / Return n if noneint next(int v1, int v2)/ Get v1s neighbor after v2 int i; for(i=v2+1; i0, Illegal weight value); if (matrixv1v2 = 0)

18、numEdge+; matrixv1v2 = wgt;void delEdge(int v1, int v2) / Delete edge (v1, v2) if (matrixv1v2 != 0) numEdge-; matrixv1v2 = 0;int weight(int v1, int v2) return matrixv1v2; int getMark(int v) return markv; void setMark(int v, int val) markv = val; 39鄰接表實(shí)現(xiàn)（1）class Edge public: int vertex, weight; Edge(

19、) vertex = -1; weight = -1; Edge(int v, int w) vertex = v; weight = w; ;class Graphl : public Graph / Implement adjacency listprivate: int numVertex, numEdge; / Number of vertices, edges List* vertex; / List headers int *mark; / Pointer to mark arraypublic: Graphl(int numVert)/ Make graph with numVe

20、rt vertices int i, j; numVertex = numVert; numEdge = 0; mark = new intnumVert; / Initialize mark array for (i=0; inumVertex; i+) marki = UNVISITED; / Create and initialize adjacency lists vertex = (List*) new List*numVertex; for (i=0; inumVertex; i+) vertexi = new LList();40鄰接表實(shí)現(xiàn)（2）int first(int v)

21、/ Return first neighbor of v Edge it; vertexv-setStart(); if (vertexv-getValue(it) return it.vertex; else return numVertex; / Return n if noneint next(int v1, int v2) / Gete v1s neighbor after v2 Edge it; vertexv1-getValue(it); if (it.vertex = v2) vertexv1-next(); else / Start from beginning of list

22、 vertexv1-setStart(); while (vertexv1-getValue(it) & (it.vertex next(); if (vertexv1-getValue(it) return it.vertex; else return numVertex; / Return n if none41鄰接表實(shí)現(xiàn)（3） / Set edge (v1, v2) to wgtvoid setEdge(int v1, int v2, int wgt) Assert(wgt0, Illegal weight value); Edge it(v2, wgt); Edge curr;

23、 vertexv1-getValue(curr); if (curr.vertex != v2) / If not already there, search for (vertexv1-setStart(); vertexv1-getValue(curr); vertexv1-next() if (curr.vertex = v2) break; if (curr.vertex = v2) / Clear out the current one vertexv1-remove(curr); else numEdge+; vertexv1-insert(it);42鄰接表實(shí)現(xiàn)（4）void delEdge(int v1, int v2) / Delete edge (