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

1、1第第1111章章 圖圖數(shù)據(jù)結(jié)構(gòu)與算法分析2345圖的應用為計算機與通信網(wǎng)絡的互連建模把一張地圖表示為一組位置以及位置之間的距離，以求得位置之間得最短路徑為網(wǎng)絡的流量能力建模尋找從開始狀態(tài)到目標狀態(tài)得路徑，如人工智能問題的求解為計算機算法建模，顯示程序狀態(tài)的變化為復雜活動各子任務的完成尋找較優(yōu)順序，如大型建筑的建造為家族、商業(yè)或軍事組織和自然科學分類中的各種關系建模6網(wǎng)型結(jié)構(gòu)小節(jié) 客觀世界中廣泛存在網(wǎng)狀結(jié)構(gòu) 圖結(jié)構(gòu)也在計算科學領域中被廣泛的（創(chuàng)造和）應用7以上各例的數(shù)據(jù)(信息)組織形式，均稱為網(wǎng)狀結(jié)構(gòu)。圖的定義和基本術語8圖Graphs圖可以用 G = (V, E) 來表示,每個圖都包括一個頂

2、點集(vertices) V, 和一個邊集合(edges) E, 其中E中的每條邊都是 V 中某一對頂點之間的連接.頂點總數(shù)記為 |V|, 邊的總數(shù)記為 |E|.9圖Graphs如果圖中的邊限定為從一個頂點指向另一個頂點, 則此圖稱為一條邊所連接的兩個頂點是有向圖(directed graph或digraph)。如果圖中的邊沒有方向, 則稱之為無向圖(undirected graph)。如果圖中各頂點均帶有標號, 則稱之為標號圖(labeled graph)。相鄰的(adjacent), 稱為鄰接點(neighbors)。連接一對鄰接點u、v的邊被稱為與頂點u、v相關聯(lián)(incident)的邊

3、, 記作(u,v)。每條邊都可能附有值或權(weight)。邊上標有權的圖稱為帶權圖(weighted graph)10頂點的度在無向圖中，與頂點vi(viV(G)相關聯(lián)的邊的條數(shù)稱為vi的度，記為TD(vi)在有向圖中，頂點的度為頂點的入度、出度之和入度等于以vi為頭的弧的數(shù)目出度等于以vi為尾的弧的數(shù)目111( )2nii ieTD v=n為圖G的頂點數(shù)路徑Paths 和回路 Cycles路徑: 如果頂點序列 v1, v2, , vn 從 vi 到 vi+1 (1 = i n) 的邊均存在，則稱頂點序列v1, v2, , vn 構(gòu)成一條長度為 n-1 的路徑(path).如果路徑上的各個頂

4、點都不同，則稱這個路徑為簡單路徑(simple path).一條路徑將某個頂點vi 連接到它本身，且其長度大于或等于3，則稱此路徑為回路(cycle).如果構(gòu)成回路的路徑是簡單路徑,除了首尾兩個頂點相同以外其他頂點均不同,則稱此回路為簡單回路(simple cycle).12圖 (2)13子圖子圖(subgraph)S是指由圖G中選出其頂點集的一個子集VS以及與VS中頂點相關聯(lián)的一些邊所構(gòu)成的圖14連通分量Connected Components如果一個無向圖中任意一個頂點到其他任意頂點都至少存在一條路徑, 則稱此無向圖為連通的(connected).無向圖的極大連通子圖稱為連通分量(conn

5、ected component).15無環(huán)圖 和 有向無環(huán)圖 不帶回路的圖稱為無環(huán)圖(acyclic graph) 不帶回路的有向圖稱為有向無環(huán)圖(directed acyclic graph或DAG)一棵自由樹(free tree)就是一個不帶有簡單回路的無向圖, 它是連通的, 且有|V|-1條邊1617對比對比網(wǎng)型結(jié)構(gòu)網(wǎng)型結(jié)構(gòu)和和樹型結(jié)構(gòu)樹型結(jié)構(gòu)的結(jié)構(gòu)特點的結(jié)構(gòu)特點18網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu) 根結(jié)點根結(jié)點 ( (無前驅(qū)無前驅(qū)) )多個葉子結(jié)點多個葉子結(jié)點 ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 多個后繼多個后繼) ) 所有的結(jié)點的所有的結(jié)點的特

6、征一致特征一致 ( (頂點頂點) )結(jié)點可以和結(jié)點可以和多個的其它結(jié)點多個的其它結(jié)點 關聯(lián)關聯(lián) ( (邊邊) )圖的ADT1920 圖圖是由一個是由一個頂點集頂點集 V V 和一個和一個弧集弧集 R 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 為弧頭弧頭，w 為弧尾弧尾。 謂詞 P(v,w) 定義了弧 的意義或信息。圖的ADT定義Graph ADTclass Graph / Graph abstract classpublic: virtual int n() =0; / # of ver

7、tices 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 setEdge(int, int, int) =0; / Delete edge defined by two vertices virtual void delEdge(int, int) =0; / Weight of edge connecting two ve

8、rtices virtual int weight(int, int) =0; virtual int getMark(int) =0; virtual void setMark(int, int) =0;2122結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀插入或刪除頂點插入或刪除頂點對鄰接點的操作對鄰接點的操作對頂點的訪問操作對頂點的訪問操作遍歷遍歷插入和刪除弧插入和刪除弧圖的ADT定義（2）23CreatGraph(&G, V, VR):CreatGraph(&G, V, VR): / 按定義(V, VR) 構(gòu)造圖DestroyGraph(&G):DestroyGraph(&a

9、mp;G): / 銷毀圖結(jié)構(gòu)的建立和銷毀24對頂點的訪問操作LocateVex(G, u);LocateVex(G, u); / 若G中存在頂點u，則返回該頂點在 / 圖中“位置位置” ；否則返回其它信息。GetVex(G, v);GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value);PutVex(&G, v, value); / 對 v 賦值value。25對鄰接點的操作FirstAdjVex(G, v);FirstAdjVex(G, v); / 返回 v 的“第一個鄰接點第一個鄰接點” 。若該頂點/在 G 中沒有鄰接點，則返回“空”。Ne

10、xtAdjVex(G, v, w);NextAdjVex(G, v, w); / 返回 v 的（相對于 w 的） “下一個下一個鄰接鄰接/ 點點”。若 w 是 v 的最后一個鄰接點，則/ 返回“空”。26插入或刪除頂點InsertVex(&G, v);InsertVex(&G, v); /在圖G中增添新頂點v。DeleteVex(&G, v);DeleteVex(&G, v); / 刪除G中頂點v及其相關的弧。27插入和刪除弧InsertArc(&G, v, w); InsertArc(&G, v, w); / 在G中增添弧，若G是無向的， /則

11、還增添對稱弧。DeleteArc(&G, v, w);DeleteArc(&G, v, w); /在G中刪除弧，若G是無向的， /則還刪除對稱弧。28遍 歷DFSTraverse(G, v, Visit(); DFSTraverse(G, v, Visit(); /從頂點v起深度優(yōu)先深度優(yōu)先遍歷圖G，并對每/個頂點調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G, v, Visit();BFSTraverse(G, v, Visit(); /從頂點v起廣度優(yōu)先廣度優(yōu)先遍歷圖G，并對每/個頂點調(diào)用函數(shù)Visit一次且僅一次。圖的實現(xiàn)（物理數(shù)據(jù)結(jié)構(gòu)）29圖 的表示法 鄰接

12、矩陣(adjacency matrix)表示法 圖的鄰接矩陣是一個|V|V|矩陣。 如果從vi到vj存在一條邊, 則對第i行的第j個元素做標記, 否則不做標記 鄰接矩陣的空間代價為(|V|2) 鄰接表(adjacency list)表示法 鄰接表是一個以鏈表為元素的數(shù)組。該數(shù)組包含|V|個元素, 其中第i個元素存儲的是指向頂點vi的鏈表的指針, 這個鏈表是由頂點vi的鄰接點構(gòu)成 鄰接表的空間代價為(|V|+|E|)30有向圖的表示法31無向圖的表示法32表示法的空間代價Adjacency Matrix鄰接矩陣:Adjacency List鄰接鏈表:哪種表示法存儲效率更高取決于圖中邊的數(shù)目33十

13、字鏈表 十字鏈表是有向圖的另一種鏈式存儲結(jié)構(gòu). 可以看成將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表. 在十字鏈表中，對應于有向圖中每一條弧有一個結(jié)點，對應于每個頂點也有一個結(jié)點.34V1V2V3V4V1V2V3V4012320303132230102datafirstinfirstouttailvexheadvexhlinktlinkinfo鄰接多重表 鄰接多重表是無向圖的另一種鏈式存儲結(jié)構(gòu) 在鄰接表中每一條邊（vi，vj）有兩個結(jié)點，分別在第i個和第j個鏈表中，這給某些圖的操作帶來不便 在鄰接多重表中，每一條邊用一個結(jié)點表示，每一個頂點也用一個結(jié)點表示35相鄰矩陣實現(xiàn)（1）class

14、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 vertices int i, j; numVertex = numVert; numEdge = 0; mark

15、= 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 (int j=0; jnumVertex; j+) matrixij = 0; 36相鄰矩陣實現(xiàn)（2）int f

16、irst(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) numEdge+; matrixv1v2 = wgt;void delEdge(int v1, int v2

17、) / 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; 38鄰接表實現(xiàn)（1）class Edge public: int vertex, weight; Edge() vertex = -1; weight = -1; Edge(int v, int w) vertex

18、= 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 numVert vertices int i, j; numVertex = numVert; numEdge = 0

19、; 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();39鄰接表實現(xiàn)（2）int first(int v) / Return first neighbor of v Edge it; vertexv-setStart

20、(); 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 vertexv1-setStart(); while (vertexv1-getValue(it) &am

21、p; (it.vertex next(); if (vertexv1-getValue(it) return it.vertex; else return numVertex; / Return n if none40鄰接表實現(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; vertexv1-getValue(curr); if (curr.vertex != v2) / If

22、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);41鄰接表實現(xiàn)（4）void delEdge(int v1, int v2) / Delete edge (v1, v2) Edge curr; vertexv1-getValue(