數(shù)據(jù)結(jié)構(gòu)課件第六章

1、第六章 圖圖的基本概念圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷最小生成樹最短路徑 活動(dòng)網(wǎng)絡(luò) 圖的定義 圖是由頂點(diǎn)的有限集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph(V, E ) 其中： V = x | x 某個(gè)數(shù)據(jù)對象是頂點(diǎn)的有窮非空集合； E = (x,y) | x,y V 是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。6.1 圖的基本概念V(G1)=0, 1, 2, 3; E(G1)=(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) V(G2)=0, 1, 2, 3, 4, 5, 6; E(G2)=(0, 1), (0, 2), (1

2、, 3), (1, 4), (2, 5), (2, 6) V(G3)=0, 1, 2; E(G3)=, 01230123456012G1G2G3 有向圖與無向圖 在有向圖中，頂點(diǎn)對是有序的。在無向圖中，頂點(diǎn)對(x, y)是無序的。完全圖 若有n個(gè)頂點(diǎn)的無向圖有n(n-1)/2 條邊, 則此圖為完全無向圖。有n個(gè)頂點(diǎn)的有向圖有n(n-1) 條邊，則此圖為完全有向圖。鄰接頂點(diǎn) 如果(u, v)是E(G)中的一條邊，則稱u與v 互為鄰接頂點(diǎn)，邊(u, v)使得頂點(diǎn)u, v之間相關(guān)聯(lián) 。權(quán) 某些圖的邊具有與它相關(guān)的數(shù)，稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。子圖 設(shè)有兩個(gè)圖 G(V, E) 和G(V, E)。若

3、VV 且EE，則稱圖G是圖G的子圖。頂點(diǎn)的度 一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中, 頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。對于有向圖，頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù)，記作 ID(v)；頂點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù)， 記作OD(v)。路徑 在圖G(V,E)中，若從頂點(diǎn)vi出發(fā)，沿一些邊經(jīng)過一些頂點(diǎn)vp1，vp2，vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi、vp1、vp2、.、vpm、vj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、.、(vpm,vj)應(yīng)是屬于E的邊。路徑長度 非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶

4、權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑 若路徑上各頂點(diǎn)v1, v2, ., vm均不互相重復(fù), 則稱這樣的路徑為簡單路徑?；芈?若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合, 則稱這樣的路徑為回路或環(huán)。連通圖與連通分量 在無向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的, 則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強(qiáng)連通圖與強(qiáng)連通分量 在有向圖中, 若對于每一對頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的路徑, 則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。生成樹 一個(gè)連通圖的生成樹是它的極小

5、連通子圖，在n個(gè)頂點(diǎn)的情形下，有n-1條邊。不予討論的圖例回答下列問題：（1）對于一個(gè)具有n個(gè)頂點(diǎn)的連通無向圖，最多有多少條邊，最少有多少條邊？（2）對于一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，最多有多少條邊，最少有多少條邊？（1）最多有n(n-1)/2條邊，最少有n-1條邊。（2）最多有n(n-1)條邊，最少有n條邊。例 若具有n個(gè)頂點(diǎn)的無向圖G的頂點(diǎn)度數(shù)的和大于或等于2n，則G中必然存在回路，試證明之。假定G有n個(gè)頂點(diǎn)，度之和為N，N2n。因?yàn)閳D中每條邊涉及兩個(gè)頂點(diǎn)，也即每條邊含有兩個(gè)度，因此，圖中至少有n條邊。因?yàn)閷?yīng)一個(gè)n個(gè)頂點(diǎn)的樹圖只有n1條邊，如果多于n1條邊則樹圖將不存在，也即圖中必然存

6、在回路，而由前述所知，該圖至少有n條邊，故該圖必有回路存在。圖的抽象數(shù)據(jù)類型template class Graph public: Graph ( ); void InsertVertex ( const T & vertex ); /插入頂點(diǎn) void InsertEdge( int v1, int v2, int weight); /插入邊 void RemoveVertex ( int v ); /刪除頂點(diǎn) void RemoveEdge ( int v1, int v2 ); /刪除邊 bool IsEmpty( ); /判邊集是否為空 T GetWeight ( int v1, i

7、nt v2 ); 返回邊上的權(quán)值 int GetFirstNeighbor ( int v ); 返回v的第一個(gè)鄰接頂點(diǎn)的位 置 int GetNextNeighbor ( int v1, int v2 ); 下一個(gè)鄰接頂點(diǎn)的位置;6.2 圖的存儲(chǔ)表示在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖G =(V,E )是一個(gè)有n個(gè)頂點(diǎn)的圖，則圖的鄰接矩陣是一個(gè)二維數(shù)組 An, n，定義為：無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的。鄰接矩陣 (Adjacency Matrix)在有向圖中, 統(tǒng)計(jì)第i行1的個(gè)數(shù)可得頂點(diǎn)i的出度，統(tǒng)計(jì)第

8、j列1的個(gè)數(shù)可得頂點(diǎn)j的入度。在無向圖中，統(tǒng)計(jì)第i行(列)1的個(gè)數(shù)可得頂點(diǎn)i的度。網(wǎng)絡(luò)的鄰接矩陣template class Graph public: Graph ( int sz=DefaultVertices); graph(); bool GraphEmpty( ) const if (numEdges = 0) return ture; else return false; bool GraphFull ( ) const if (numVertices = maxVertices | numEdges = maxVertices*(maxVertices-1)/2) return

9、ture; else return false; 圖的模板基類 int NumberOfVertices( ) return numVertices; int NumberOfEdges ( ) return numEdges; virtual bool InsertVertex ( const Type vertex ); virtual bool InsertEdge( int v1, int v2, E cost); virtual bool RemoveVertex ( int v ); virtual bool RemoveEdge ( int v1, int v2 ); T Get

10、Weight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); Protected int maxVertices; int numEdges; int numVertices; int getVertexPos(T vertex);template class Graphmtx : public gragh friend istream&operator (istream&in, grapgmtx & G)friend ostream&operator (os

11、tream&out, grapgmtx & G)public: Graphmtx ( int sz=DefaultVertices); /構(gòu)造函數(shù) Graphmtx( delete VerticesList; delete Edge; ) T GetValue ( int i ) /取頂點(diǎn) return i = 0 & i numVertices ? VerticesListi : NULL; E GetWeight (int v1, int v2 ) /取邊上的權(quán) return v1!=-1&v2!=-1 ? Edgev1v2 : 0;用鄰接矩陣表示的圖的類的定義 int GetFirstN

12、eighbor ( int v ); /取鄰接頂點(diǎn) int GetNextNeighbor ( int v, int w ); /取鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) bool InsertVertex ( const T vertex ); /插入頂點(diǎn) bool InsertEdge ( int v1, int v2, E cost ); /插入邊 bool RemoveVertex ( int v ); /刪除頂點(diǎn) bool RemoveEdge ( int v1, int v2 ); /刪除邊private: T * VerticesList; E * Edge; int GetVertexPos

13、 ( T vertex ) /給出頂點(diǎn)在圖中的位置 for ( i=1; i numVertices ) if (VerticesListi = vertex) return i; return 0; template Graphmtx:Graph( int sz)/構(gòu)造函數(shù) maxVertices = sz; numVertices = 0; numEdges = 0; int i, j; VerticesList = new TmaxVertices; Edge = (int * *) new int * maxVertices; for (i=0; imaxVertices; i+) E

14、dgei = new intmaxVertices; for (i = 0; i sz; i+ ) for ( j = 0; j sz; j+ ) Edgeij = ( i=j ) ? 0 : maxWeight;鄰接矩陣實(shí)現(xiàn)的部分圖操作（構(gòu)造）template int Graphmtx:getFirstNeighbor(int v)/給出頂點(diǎn)位置v的第一個(gè)鄰接頂點(diǎn)的位置，如果找 不到，則函數(shù)返回-1。 if ( v != -1 ) for ( int col=0; col0 & EdgevcolmaxWeight ) return col; return -1; 鄰接矩陣實(shí)現(xiàn)的部分圖操作（找

15、第一個(gè)鄰接頂點(diǎn)）template int Graphmtx:getNextNeighbor(int v, int w)/給出頂點(diǎn)v的某鄰接頂點(diǎn)w的下一個(gè)與v的鄰接頂點(diǎn) if (v != -1 & w != -1) for ( int col=w+1; col0 & EdgevcolmaxWeight) return col; return -1; 鄰接矩陣實(shí)現(xiàn)的部分圖操作（找下一個(gè)鄰接頂點(diǎn)）template int Graphmtx:insertVertex(const T& vertex)/插入頂點(diǎn)vertex if (numVertices=maxVertices) return fals

16、e;/頂點(diǎn)表滿，不插入 VerticesListnumVertices+=vertex;return ture; 鄰接矩陣實(shí)現(xiàn)的部分圖操作（插入一個(gè)頂點(diǎn)）template int Graphmtx:removeVertex(int v)/刪去頂點(diǎn)v和所有與它關(guān)聯(lián)的邊 if (v=numVertices) return false; /v不再圖中，不刪除 if (numVertices=1) return false; /只剩一個(gè)頂點(diǎn)，不刪除 int i, j; VerticesListv = VerticesListnumVertices-1; /頂點(diǎn)表中刪除該結(jié)點(diǎn) for (i=0; i0&

17、EdgeivmaxWeight) numEdges-; 鄰接矩陣實(shí)現(xiàn)的部分圖操作（刪除一個(gè)頂點(diǎn)） for (i=0; inumVertices; i+)/用最后一列填補(bǔ)第v列 Edgeiv = EdgeinumVertices-1; numVertices-; /頂點(diǎn)數(shù)減1 for (j=0; jnumVertices; j+) /用最后一行填補(bǔ)第v行 Edgevj=EdgenumVerticesj; return true; template int Graphmtx:insertEdge(int v1, int v2, E cost)/插入邊（v1, v2）權(quán)值為cost if (v1-1

18、&v1-1& v2numVertices&Edgev1v2=maxWeight) /插入條件 Edgev1v2=Edgev2v1=cost; numEdges+;return ture; else return false; 鄰接矩陣實(shí)現(xiàn)的部分圖操作（插入一條邊）template int Graphmtx:removeEdge(int v1,int v2)/在圖中刪除邊（v1,v2） if (v1-1&v1-1& v20& Edgev1v2maxWeight) Edgev1v2=Edgev2v1=maxWeight; numEdges-; return true; else return fa

19、lse;鄰接矩陣實(shí)現(xiàn)的部分圖操作（刪除一條邊）template istream& operator istream&in,Graphmtx&G /通過從輸入流對象in輸入n個(gè)頂點(diǎn)信息和e條無向邊 的信息建立用鄰接矩陣表示的圖G。 /鄰接矩陣初始化的工作已經(jīng)在構(gòu)造函數(shù)中完成。 int i, j, k, n, m; T e1, e2; E weight; innm; /輸入頂點(diǎn)數(shù)n和邊數(shù)m for (i=0; ie1;G.insertVertex(e1); i=0;通過輸入建立圖的鄰接矩陣表示 while (ie1e2weight; /輸入端點(diǎn)信息 j=G.getVertexPos(e1); k=

20、G.getVertexPos(e2); /查頂點(diǎn)號(hào) if (j=-1|k=-1) cout邊兩端點(diǎn)信息有誤，重新輸入！endl; else G.inserEdge(j, k, weight); i+; return in;template ostream& operator (ostream& out,Graphmtx&G) /輸出圖的所有頂點(diǎn)和邊的信息 int i, j, k, n, m; T e1, e2; E w; n =G.NumberOfVertices(); m=G.NumberOfEdges(); outn,mendl; /輸出頂點(diǎn)數(shù)與邊數(shù) 輸出鄰接矩陣表示的圖的頂點(diǎn)和邊信息 f

21、or (i=0; in; i+) for (j=i+1; j0&wmaxWeight) /有效 e1=G.getValue(i); e2=G.getValue(j); /輸出 out(e1,e2,w)endl; return out;鄰接表 (Adjacency List)無向圖的鄰接表把同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，鏈表的每一個(gè)結(jié)點(diǎn)代表一條邊，叫做邊結(jié)點(diǎn)，結(jié)點(diǎn)中保存有與該邊相關(guān)聯(lián)的另一頂點(diǎn)的頂點(diǎn)下標(biāo)dest和指向同一鏈表中下一個(gè)邊結(jié)點(diǎn)的指針link。有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第i個(gè)邊鏈表鏈接的邊都是頂點(diǎn)i發(fā)出的邊。也叫做出邊表。在有向圖的逆鄰接表中，第i個(gè)邊鏈表鏈

22、接的邊都是進(jìn)入頂點(diǎn)i的邊。也叫做入邊表。帶權(quán)圖的邊結(jié)點(diǎn)中保存該邊上的權(quán)值cost。頂點(diǎn)i的邊鏈表的表頭指針adj在頂點(diǎn)表的下標(biāo)為i的頂點(diǎn)記錄中，該記錄還保存了該頂點(diǎn)的其它信息。在鄰接表的邊鏈表中，各個(gè)邊結(jié)點(diǎn)的鏈入順序任意，視邊結(jié)點(diǎn)輸入次序而定。設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則用鄰接表表示無向圖時(shí)，需要n個(gè)頂點(diǎn)結(jié)點(diǎn)，2e個(gè)邊結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需n個(gè)頂點(diǎn)結(jié)點(diǎn)，e 個(gè)邊結(jié)點(diǎn)。template struct Edge /邊結(jié)點(diǎn)的定義 in dest; /邊的另一頂點(diǎn)位置 E cost; /邊上的權(quán)值 Edge *link; /下一條邊鏈指針 Edge() /構(gòu)造函數(shù) Edge

23、(int num, E weight):dest(num), cost(weight), link(NULL) /構(gòu)造函數(shù) bool perator!=(Edge&R)const /判邊不等否 return(dest!=R.dest) ? true : false; ; 鄰接表表示的圖的類定義template struct Vertex /頂點(diǎn)的定義 T data; /頂點(diǎn)的名字 Edge *adj; /邊鏈表的頭指針;template class Graphlnk:public Graph /圖的類定義friend istream& operatoristream&in,Graphlin&

24、G);friend ostream& operatorostream&out,Graphlin& G); /輸入和輸出public: Graphlnk (int sz=DefaultVertices); /構(gòu)造函數(shù) Graphlnk(); /析構(gòu)函數(shù) T getValue(int i) /取位置為i的頂點(diǎn)中的值 return(i=0&iNumVertices) ? NodeTablei.data : 0; E getWeight(int v1,int v2); /返回邊(v1,v2)上的權(quán)值 bool insertVertex(const T& vertex); /插入一個(gè)頂點(diǎn)vertex b

25、ool removeVertex(int v); /在圖中刪除一個(gè)頂點(diǎn)v bool insertEdge(int v); /在圖中插入一條邊(v1,v2) bool removeEdge(int v1,int v2); /在圖中刪除一條邊(v1,v2) int getFirstNeighbor(int v); /取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn) int getNextNeighbor(int v,int w); /取v的鄰接頂點(diǎn)w的下一鄰接頂點(diǎn)private: Vertex *NodeTable; /頂點(diǎn)表（各邊鏈表的頭結(jié)點(diǎn)） int getVertexPos(const T vertex) /給出頂

26、點(diǎn)vertex在圖中的位置 for (int i=0; inumVertices; i+) if (NodeTablei.data=Vertex) return i; return -1; ; 網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表template Graphlnk:Graphlnk(int sz)/構(gòu)造函數(shù)：建立一個(gè)空的鄰接表 maxVertices=sz; numVertices=0; numEdges=0; NodeTable=new VertexmaxVertices; /創(chuàng)建頂點(diǎn)表數(shù)組 if (NodeTable=NULL) cerr存儲(chǔ)分配錯(cuò)！endl;exit(1); for (int i=0;

27、 imaxVertices; i+) NodeTablei.adj=NULL; 鄰接表的構(gòu)造函數(shù)和析構(gòu)函數(shù)template Graphlnk:Graphlnk()/析構(gòu)函數(shù):刪除一個(gè)鄰接表 for (int i=0; inumVertices; i+) /刪除各邊鏈表的結(jié)點(diǎn) Edge *p=NodeTablei.adj; /找到其對應(yīng)邊鏈表的首結(jié)點(diǎn) while (p!=NULL) /不斷刪除第一個(gè)結(jié)點(diǎn) NodeTablei.adj=p-link; delete p; p=NodeTablei.adj; delete NodeTable; /刪除頂點(diǎn)表數(shù)組;template int Graphl

28、nk:getFirstNeighbor(int v)/給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置，如果 找不到，則函數(shù)返回-1. if (v!=-1) /頂點(diǎn)v存在 Edge *p=NodeTablev.adj; /對應(yīng)邊鏈表第一個(gè)邊結(jié)點(diǎn) if (p!=NULL) return P-data; /存在，返回第一個(gè)鄰接頂點(diǎn) return -1; /第一個(gè)鄰接頂點(diǎn)不存在;鄰接表部分成員函數(shù)的實(shí)現(xiàn)（找第一個(gè)鄰接頂點(diǎn)）template int Graphlnk:getNextNeighbor(int v, int w)/給出頂點(diǎn)v的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)的位置，若沒有 下一個(gè)鄰接頂點(diǎn)，則函數(shù)返回-1.

29、 if (v!=-1) /頂點(diǎn)v存在 Edge *p=NodeTablev.adj; /對應(yīng)邊鏈表第一個(gè)邊結(jié)點(diǎn) while (p!=NULL & p-dest!=w) /尋找鄰接頂點(diǎn)w p=p-link; if (p!=NULL&p-link!=NULL) return p-link-dest; /返回下一個(gè)鄰接頂點(diǎn) return -1; /下一個(gè)鄰接頂點(diǎn)不存在; 鄰接表部分成員函數(shù)的實(shí)現(xiàn)（找下一個(gè)鄰接頂點(diǎn)）template E Graphlnk:getWeight(int v1, int v2)/函數(shù)返回邊(v1,v2)上的權(quán)值，若該邊不在圖中，則函數(shù)返回 權(quán)值0. if (v1!=-1&v

30、2!=-1) Edge *p=NodeTablev1.adj; /v1的第一條關(guān)聯(lián)的邊 while (p!=NULL&p-dest!=v2) /尋找鄰接頂點(diǎn)v2 p=p-link; if (p!=NULL) return p-cost; /找到此邊，返回權(quán)值 return 0; /邊(v1,v2)不存在; 鄰接表部分成員函數(shù)的實(shí)現(xiàn)（得到邊上的權(quán)值）template bool Graphlnk:insetVertex(const T& vertex)/在圖的頂點(diǎn)表中插入一個(gè)新頂點(diǎn)vertex。若插入成 功，函數(shù)返回TRUE，否則返回FALSE。 if (numVertices=maxVertic

31、es) return false; /頂點(diǎn)表滿，不能插入 NodeTablenumVertices.data=vertex; /插入在表的最后 numVertices+; return true; 鄰接表部分成員函數(shù)的實(shí)現(xiàn)（插入和刪除頂點(diǎn)）template bool Graphlnk:removeVertex(int v)/在圖中刪除一個(gè)指定頂點(diǎn)v，v是頂點(diǎn)號(hào)。若刪除成功，函 數(shù)返回TRUE，否則返回FALSE。 if (numVertices=1 | v=numVertices) return false; /表空或頂點(diǎn)號(hào)超出范圍 Edge *p, *s, *t; int i, k; whi

32、le (NodeTablev.adj!=NULL) /刪除第v個(gè)頂點(diǎn)的邊鏈表 p=NodeTablev.adj; k=p-dest; /取鄰接頂點(diǎn)k s=NodeTablek.adj; t=NULL; /找對稱存放的邊結(jié)點(diǎn) while (s!=NULL&s-dest!=v) t=s; s=s-link; if (s!=NULL) /刪除對稱存放的邊結(jié)點(diǎn) if (t=NULL) NodeTablek.adj=s-link; else t-link=s-link; delete s; NodeTablev.adj=p-link; /清除頂點(diǎn)v的邊鏈表結(jié)點(diǎn) delete p; numEdges-;

33、/與頂點(diǎn)v相關(guān)聯(lián)的邊數(shù)減1 numVertices-; /圖的頂點(diǎn)個(gè)數(shù)減1 NodeTablev.data=NodeTablenumVertices.data; /填補(bǔ) p=NodeTablev.adj=NodeTablenumVertices.adj; while (p!=NULL) s=NodeTablep-dest.adj; while (s!=NULL) if (s-dest=numVertices) s-dest=v; break; else s=s-link; return true; template bool Graphlnk:insertEdge(int v1, int v2

34、, E weight)/在帶權(quán)圖中插入一條邊(v1,v2)，若此邊存在或參數(shù)不合理， 函數(shù)返回FALSE，否則返回TRUE。對于非帶權(quán)圖，最后一 個(gè)參數(shù)weight不要。算法中相應(yīng)語句也不要。 if (v1=0&v1=0&v2numVertices) Edge *q,*p=NodeTablev1.adj; /v1對應(yīng)的邊鏈表頭指針 while(p!=NULL&p-dest!=v2) /尋找鄰接頂點(diǎn)v2 p=p-link; if (p!=NULL) return false; /找到此邊，不插入 p=new Edge; q=new Edge; /否則創(chuàng)建新結(jié)點(diǎn) p-dest=v2; p-cost

35、=weight; p-link=NodeTablev1.adj; /鏈入v1邊鏈表 NodeTablev1.adj=p;鄰接表部分成員函數(shù)的實(shí)現(xiàn)（插入一條邊） q-dest=v1;q-cost=weight; q-link=NodeTablev2.adj; /鏈入v2邊鏈表 NodeTablev2.adj=q; numEdges+; return true; return 0;template bool Graphlnk:removetEdge(int v1,int v2)/在圖中刪除一條邊(v1,v2) if (v1!=-1&v2!=-1) Edge *p=NodeTablev1.adj,*

36、q=NULL,*s=p; while(p!=NULL&p-dest!=v2) /v1對應(yīng)邊鏈表中找被刪邊 q=p; p=p-link; if (p!=NULL) /找到被刪邊結(jié)點(diǎn) if (p=s) NodeTablev1.adj=p-link; /該結(jié)點(diǎn)是邊鏈表首結(jié)點(diǎn) else q-link=p-link; /不是，重新鏈接 delete p; else return false; /沒有找到被刪邊結(jié)點(diǎn)鄰接表部分成員函數(shù)的實(shí)現(xiàn)（刪除一條邊） p=NodeTablev2.adj; q=NULL, s=p; /v2對應(yīng)邊鏈表中刪除 while (p-dest!=v1) q=p; p=p-link;

37、 /尋找被刪邊結(jié)點(diǎn) if (p=s) NodeTablev2.adj=p-link; /該結(jié)點(diǎn)是邊鏈表首結(jié)點(diǎn) else q-link=p-link; /不是，重新鏈接 delete p; return true; /沒有找到結(jié)點(diǎn) return false; 鄰接多重表 (Adjacency Multilist)在鄰接多重表中，每一條邊只有一個(gè)邊結(jié)點(diǎn)，為有關(guān)邊的處理提供了方便。無向圖的情形邊結(jié)點(diǎn)的結(jié)構(gòu) mark vertex1 vertex2 path1 path2其中，mark 是記錄是否處理過的標(biāo)記；vertex1和vertex2是依附于該邊的兩頂點(diǎn)位置。path1域是鏈接指針，指向下一條依

38、附于頂點(diǎn)vertex1的邊；path2也是鏈接指針，指向下一條依附于頂點(diǎn)vertex2的邊。需要時(shí)還可設(shè)置一個(gè)存放與該邊相關(guān)的權(quán)值的域 cost。頂點(diǎn)的結(jié)構(gòu)存儲(chǔ)頂點(diǎn)信息的結(jié)點(diǎn)表以順序表方式組織，每一個(gè)頂點(diǎn)結(jié)點(diǎn)有兩個(gè)數(shù)據(jù)成員：其中，data 存放與該頂點(diǎn)相關(guān)的信息，F(xiàn)irstout 是指示第一條依附于該頂點(diǎn)的邊的指針。在鄰接多重表中, 所有依附于同一個(gè)頂點(diǎn)的邊都鏈接在同一個(gè)單鏈表中。從頂點(diǎn) i 出發(fā), 可以循鏈找到所有依附于該頂點(diǎn)的邊，也可以找到它的所有鄰接頂點(diǎn)。鄰接多重表的結(jié)構(gòu) data Firstout有向圖的情形在用鄰接表表示有向圖時(shí)，有時(shí)需要同時(shí)使用鄰接表和逆鄰接表。用有向圖的鄰接多重表

39、(十字鏈表)可把這兩個(gè)表結(jié)合起來表示。 鄰接多重表的結(jié)構(gòu)邊結(jié)點(diǎn)的結(jié)構(gòu)其中，mark是處理標(biāo)記；vertex1和vertex2指明該有向邊始頂點(diǎn)和終頂點(diǎn)的位置。path1是指向始頂點(diǎn)與該邊相同的下一條邊的指針；path2是指向終頂點(diǎn)與該邊相同的下一條邊的指針。需要時(shí)還可有權(quán)值域cost。 mark vertex1 vertex2 path1 path2頂點(diǎn)的結(jié)構(gòu)每個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)，它相當(dāng)于出邊表和入邊表的表頭結(jié)點(diǎn)：其中，數(shù)據(jù)成員data存放與該頂點(diǎn)相關(guān)的信息，指針Firstin指示以該頂點(diǎn)為始頂點(diǎn)的入邊表的第一條邊，F(xiàn)irstout指示以該頂點(diǎn)為終頂點(diǎn)的出邊表的第一條邊。 data Firsti

40、n Firstout鄰接多重表的結(jié)構(gòu)對于一個(gè)具有n個(gè)頂點(diǎn)e條邊的圖G，鄰接表表示的空間復(fù)雜度為O(n+e)。若圖中邊的數(shù)目遠(yuǎn)遠(yuǎn)小于n2(即en2)（稀疏圖Sparse Graph），鄰接表表示比用鄰接矩陣表示節(jié)省存儲(chǔ)空間。若e接近于n2 (稠密圖 Dense Graph)，考慮到鄰接表中要附加鏈域，則應(yīng)取鄰接矩陣表示法為宜。 兩種主要存儲(chǔ)結(jié)構(gòu)的比較分析空間復(fù)雜度在無向圖中求頂點(diǎn)的度：鄰接矩陣中第i行(或第i列)上非零元素的個(gè)數(shù)即為頂點(diǎn)vi的度；在鄰接表表示中，頂點(diǎn)vi的度則是第i個(gè)邊表中的結(jié)點(diǎn)個(gè)數(shù)。在有向圖中求頂點(diǎn)的度。采用鄰接矩陣表示比鄰接表表示更方便：鄰接矩陣中的第i行上非零元素的個(gè)數(shù)是頂

41、點(diǎn)vi的出度OD(vi)，第i列上非零元素的個(gè)數(shù)是頂點(diǎn)vi的入度ID(vi)，頂點(diǎn)vi的度即是二者之和。在鄰接表表示中，第i個(gè)邊表(即出邊表)上的結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)vi的出度，求vi的入度較困難，需遍歷各頂點(diǎn)的邊表。若有向圖采用逆鄰接表表示，則與鄰接表表示相反（此時(shí)可采用鄰接多重表）。求頂點(diǎn)的度在鄰接矩陣表示中，(vi，vj)或vi，vj是否是圖的一條邊，只要判定矩陣中的第i行第j列上的那個(gè)元素是否為零即可；在鄰接表表示中，需掃描第i個(gè)邊表，最壞情況下要耗費(fèi)O(n)時(shí)間。邊存在的判定在鄰接矩陣中求邊的數(shù)目e，必須檢測整個(gè)矩陣，所耗費(fèi)的時(shí)間是O(n2)，與e的大小無關(guān)；而在鄰接表表示中，只要對每個(gè)邊

42、表的結(jié)點(diǎn)個(gè)數(shù)計(jì)數(shù)即可求得e，所耗費(fèi)的時(shí)間是O(e+n)。因此，當(dāng)en2時(shí)，采用鄰接表表示更節(jié)省時(shí)間。 邊的數(shù)量操作鄰接矩陣鄰接表1求頂點(diǎn)的度遍歷矩陣的一行（列）遍歷邊鏈表2找頂點(diǎn)遍歷頂點(diǎn)數(shù)組遍歷頂點(diǎn)數(shù)組3邊存在的判定O(1)遍歷邊鏈表4求邊的數(shù)量遍歷整個(gè)矩陣遍歷所有邊鏈表5插入邊O(1)邊鏈表中插入結(jié)點(diǎn)操作鄰接矩陣鄰接表6刪除邊O(1)遍歷邊鏈表7插入頂點(diǎn)O(1)O(1)8刪除頂點(diǎn)O(|V|)O(|E|)9找第一個(gè)鄰接頂點(diǎn)遍歷矩陣的一行遍歷邊鏈表10找下一個(gè)鄰接頂點(diǎn)遍歷矩陣的一行遍歷邊鏈表6.3 圖的遍歷從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，就叫

43、做圖的遍歷( Graph Traversal )。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個(gè)頂點(diǎn)i被訪問，就立即讓 visitedi為1，防止它被多次訪問。深度優(yōu)先搜索DFS ( Depth First Search )深度優(yōu)先搜索的示例通過演示了解圖的深度優(yōu)先遍歷過程DFS在訪問圖中某一起始頂點(diǎn)v后，由v出發(fā)，訪問它的任一鄰接頂點(diǎn)w1；再從w1出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點(diǎn)w2；然后再從w2

44、出發(fā)，進(jìn)行類似的訪問， 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn)u為止接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。TemplateVoid DFS (Graph& G, const T& v)/從頂點(diǎn)出發(fā)，對圖G進(jìn)行深度優(yōu)先遍歷的主過程 int i，loc=G.NumberOfVertices()/取圖中的頂點(diǎn)個(gè)數(shù) Bool visited=new booln;/創(chuàng)建輔助數(shù)組 for (int i=0;

45、in; i+) Visitedi=false; loc=G.getVertexPos(v); DFS(G, loc, visited); Delete visited; 圖的深度優(yōu)先搜索算法TemplateVoid DFS(Graph&G, int v, bool visited)/子過程從頂點(diǎn)位置V出發(fā)，以深度優(yōu)先的次序訪問所有可讀入的尚未訪問過的頂點(diǎn)，算法中用到一個(gè)輔助數(shù)組visited,對已訪問過的頂點(diǎn)作訪問標(biāo)記 CoutG.getValue(v)”;/訪問頂點(diǎn)v Visitedv=true; /頂點(diǎn)v做訪問標(biāo)記 int w=G.getFirstNeighor(v); /找頂點(diǎn)v的第一個(gè)

46、鄰接頂點(diǎn)w while (w!=-1) if (visitedw=false) DFS(G, w, visited); /若w未訪問過，遞歸訪問頂點(diǎn)w w=G.getNextNeighbor(v,w); ; 算法分析圖中有n個(gè)頂點(diǎn)，e條邊。如果用鄰接表表示圖，沿邊鏈可以找到某個(gè)頂點(diǎn)v的所有鄰接頂點(diǎn)w。由于總共有2e個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間為O(e)。而且對所有頂點(diǎn)遞歸訪問1次，所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n2)。廣度優(yōu)先搜索BFS ( Breadth First Search

47、)廣度優(yōu)先搜索的示例 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹通過演示了解圖的廣度優(yōu)先遍歷過程使用廣度優(yōu)先搜索在訪問了起始頂點(diǎn)v之后，由v出發(fā)，依次訪問v的各個(gè)未曾被訪問過的鄰接頂點(diǎn)w1, w2, , wt，然后再順序訪問w1, w2, , wt的所有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點(diǎn)， 如此做下去，直到圖中所有頂點(diǎn)都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。為了實(shí)現(xiàn)逐層訪問，算法中使用了一個(gè)隊(duì)列，用來記憶正在訪問的這一

48、層和上一層的頂點(diǎn)，以便于向下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復(fù)訪問，需要一個(gè)輔助數(shù)組visited，給被訪問過的頂點(diǎn)加標(biāo)記。TemplateVoid BFS(Graph&G, const T& v)/從頂點(diǎn)v出發(fā)，以廣度優(yōu)先的次序橫向搜索圖，算法中使用了 一個(gè)隊(duì)列 int i, w, n=G.NumberOfVertices( ); /取圖中的頂點(diǎn)個(gè)數(shù) Bool * visited=new booln; /visited 頂點(diǎn)是否訪問過 for (i=0; in; i+) visitedi=false; /初始化 int loc=G.getVertexPos(v); /取頂點(diǎn)號(hào) Co

49、untG.getValue(loc);訪問頂點(diǎn)v,做已訪問標(biāo)記 Visitedloc=true; Queue Q; Q.EnQueue(loc); /頂點(diǎn)進(jìn)隊(duì)列，實(shí)現(xiàn)分層訪問 while (!Q.IsEmpty( ) /循環(huán)，訪問所有頂點(diǎn) Q.DeQueue(loc); /從隊(duì)列中退出頂點(diǎn)loc w=G.getFirstNeighor(loc); /找頂點(diǎn)loc的第一個(gè)了鄰接頂點(diǎn)w圖的廣度優(yōu)先搜索算法 while (w!=-1) 若鄰接頂點(diǎn)w存在 if（visitedw=false） CoutG.getValue(w); visitedw=true; Q.EnQueue(w);/頂點(diǎn)w進(jìn)隊(duì)列

50、w=G.getNextNeighbor(loc, w) /找頂點(diǎn)loc的下一個(gè)鄰接頂點(diǎn) Delete visited; 算法分析如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + + dn-1 = O(e)，其中的 di 是頂點(diǎn) i 的度。所有頂點(diǎn)均進(jìn)出隊(duì)列1次，所以總的時(shí)間代價(jià)是O(n+e)。如果使用鄰接矩陣，則對于每一個(gè)被訪問過的頂點(diǎn)，循環(huán)要檢測矩陣中的 n 個(gè)元素，總的時(shí)間代價(jià)為O(n2)。例圖中給出了7個(gè)頂點(diǎn)組成的無向圖，從頂點(diǎn)1出發(fā)，對它進(jìn)行深度優(yōu)先遍歷得到的的頂點(diǎn)序列是（1），而進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是（2）。1345267(1) 1354267 1347625

51、 1534276 1247653 以上都錯(cuò) (2) 1534267 1726453 1354276 1247653 以上都錯(cuò) （1）1534276 （2）1354276例畫出圖中給出的無向圖的鄰接表表示，使得其中無向邊結(jié)點(diǎn)表中第一個(gè)頂點(diǎn)號(hào)小于第二個(gè)頂點(diǎn)號(hào)，同時(shí)請列出從頂點(diǎn)1開始的深度優(yōu)先和廣度優(yōu)先遍歷所得到的頂點(diǎn)序列和邊序列。154623154623V1V2V3V4V5V62356134124623561461345154623深度優(yōu)先遍歷：1，2，3，4，5，6(1，2) (2，3) (3，4) (4，5) (5，6)廣度優(yōu)先遍歷1，2，3，5，6，4(1，2) (1，3) (1，5) (1

52、，6) (2，4)V6V5V4V3V2V12356134124623561461345連通分量 (Connected component)當(dāng)無向圖為非連通圖時(shí)，從圖中某一頂點(diǎn)出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn)，只能訪問到該頂點(diǎn)所在的最大連通子圖(連通分量)的所有頂點(diǎn)。若從無向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷，可求得無向圖的所有連通分量。在算法中，需要對圖的每一個(gè)頂點(diǎn)進(jìn)行檢測：若已被訪問過，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個(gè)連通分量。對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生

53、成森林。Templatevoid Components(Graph&G)/通過DFS,找出無向圖的所有連通分量 int i，n=G.NumberOfVertices();/取圖中頂點(diǎn)個(gè)數(shù) bool * visited=new booln;/visited 記錄頂點(diǎn)是否訪問過 for (int i=0;in;i+) visitedi=false; /初始化，表示所有頂點(diǎn)未訪問過 for(i=0;in;i+) /順序掃描所有頂點(diǎn) for(i=0;in;i+) . if（visitedi=false） /若沒有訪問過，則訪問這個(gè)連通分量 DFS(G, i ,visited);/未訪問，出發(fā)訪問 po

54、net() /輸出這個(gè)連通分量 Delete visited; 確定連通分量的算法重連通分量 (Biconnected Component)在無向連通圖G中，當(dāng)且僅當(dāng)刪去G中的頂點(diǎn)v及所有依附于v的所有邊后，可將圖分割成兩個(gè)或兩個(gè)以上的連通分量，則稱頂點(diǎn)v為關(guān)節(jié)點(diǎn)。1,3,5,7是關(guān)節(jié)點(diǎn)安全的通信網(wǎng)絡(luò)應(yīng)該是重連通的沒有關(guān)節(jié)點(diǎn)的連通圖叫做重連通圖。在重連通圖上, 任何一對頂點(diǎn)之間至少存在有兩條路徑, 在刪去某個(gè)頂點(diǎn)及與該頂點(diǎn)相關(guān)聯(lián)的邊時(shí), 也不破壞圖的連通性。一個(gè)連通圖G如果不是重連通圖，那么它可以包括幾個(gè)重連通分量。在一個(gè)無向連通圖G中, 重連通分量可以利用深度優(yōu)先生成樹找到。 當(dāng)且僅當(dāng)u在生

55、成樹中是v的祖先，或者v是u的祖先時(shí)，非生成樹的邊(u,v)就是一條回邊（用虛線表示，如(3,1)(5,7)）。不是回邊的非生成樹的邊叫做交叉邊。dfn 頂點(diǎn)的深度優(yōu)先數(shù)，標(biāo)明進(jìn)行深度優(yōu)先搜索時(shí)各頂點(diǎn)訪問的次序。如果在深度優(yōu)先生成樹中，頂點(diǎn)u是頂點(diǎn)v的祖先, 則有dfnu dfnv。深度優(yōu)先生成樹的根是關(guān)節(jié)點(diǎn)的充要條件是它至少有兩個(gè)子女。其它頂點(diǎn)u是關(guān)節(jié)點(diǎn)的充要條件是它至少有一個(gè)子女 w, 從w出發(fā),不能通過w、w的子孫及一條回邊所組成的路徑到達(dá)u的祖先。在圖G的每一個(gè)頂點(diǎn)上定義一個(gè)low值，lowu 是從 u或u的子孫出發(fā)通過回邊可以到達(dá)的最低深度優(yōu)先數(shù)。u是關(guān)節(jié)點(diǎn)的充要條件是： u是具有兩

56、個(gè)以上子女的生成樹的根 u不是根，但它有一個(gè)子女w，使得 loww dfnu這時(shí)w及其子孫不存在指向頂點(diǎn)u的祖先的回邊。lowu = min dfnu, min loww | w 是 u 的一個(gè)子女 , min dfnx | (u, x) 是一條回邊 void Graph:DfnLow ( const int x ) /公有函數(shù)：從頂點(diǎn)x開始深度優(yōu)先搜索 int num = 1; / num是訪問計(jì)數(shù)器 dfn = new intNumVertices; low = new intNumVertices; /dfn是深度優(yōu)先數(shù), low是最小祖先訪問順序號(hào) for ( int i = 0; i

57、 NumVertices; i+ ) dfni = lowi = 0; /給予訪問計(jì)數(shù)器num及dfnu, lowu初值 DfnLow ( x, -1 ); /從根x開始 delete dfn; delete low;計(jì)算dfn與low的算法 (1)void Graph:DfnLow ( const int u, const int v ) /私有函數(shù)：從頂點(diǎn)u開始深度優(yōu)先搜索計(jì)算dfn/ 和low。在產(chǎn)生的生成樹中v是u的雙親。 dfnu = lowu = num+; int w = GetFirstNeighbor (u); while ( w != -1 ) /對u所有鄰接頂點(diǎn)w循環(huán) i

58、f ( dfnw = 0 ) /未訪問過, w是u的孩子 DfnLow ( w, u ); /從w遞歸深度優(yōu)先搜索 lowu = min2 ( lowu, loww ); /子女w的loww先求出, 再求lowu 計(jì)算dfn與low的算法 (2)else if ( w != v ) /w訪問過且w不是v，是回邊 lowu = min2 ( lowu, dfnw ); /根據(jù)回邊另一頂點(diǎn)w調(diào)整lowu w = GetNextNeighbor (u, w); /找頂點(diǎn)u在w后面的下一個(gè)鄰接頂點(diǎn) 在算法DfnLow增加一些語句, 可把連通圖的邊劃分到各重連通分量中。首先, 根據(jù) DfnLow (w,

59、 u)的返回, 計(jì)算loww。如果loww dfnu，則開始計(jì)算新的重連通分量。在算法中利用一個(gè)棧， 在遇到一條邊時(shí)保存它?？稍诤瘮?shù)Biconnected中就能輸出一個(gè)重連通分量的所有的邊。void Graph:Biconnected ( ) /公有函數(shù)：從頂點(diǎn)0開始深度優(yōu)先搜索 int num = 1; /訪問計(jì)數(shù)器num dfn = new intNumVertices; /dfn是深度優(yōu)先數(shù) low = new intNumVertices; /low是最小祖先號(hào) for ( int i = 0; i 1 時(shí)輸出重連通分量（1）void Graph:Biconnected ( const

60、 int u, const int v ) /私有函數(shù)：計(jì)算dfn與low, 根據(jù)其重連通分量輸/出Graph的邊。在產(chǎn)生的生成樹中, v 是 u 的雙親/結(jié)點(diǎn), S 是一個(gè)初始為空的棧，應(yīng)聲明為圖的數(shù)/據(jù)成員。 int x, y, w; dfnu = lowu = num+; w = GetFirstNeighbor (u); /找頂點(diǎn)u的第一個(gè)鄰接頂點(diǎn)w while ( w != - 1 ) if ( v != w & dfnw 1 時(shí)輸出重連通分量（2） if ( dfnw = 0 ) /未訪問過, w是u的孩子 Biconnected (w, u); /從w遞歸深度優(yōu)先訪問 lowu