數(shù)據(jù)結構課件第六章

1、第六章 圖圖的基本概念圖的存儲結構圖的遍歷最小生成樹最短路徑 活動網(wǎng)絡 圖的定義 圖是由頂點的有限集合(vertex)及頂點間的關系集合組成的一種數(shù)據(jù)結構： Graph(V, E ) 其中： V = x | x 某個數(shù)據(jù)對象是頂點的有窮非空集合； E = (x,y) | x,y V 是頂點之間關系的有窮集合，也叫做邊(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 有向圖與無向圖 在有向圖中，頂點對是有序的。在無向圖中，頂點對(x, y)是無序的。完全圖 若有n個頂點的無向圖有n(n-1)/2 條邊, 則此圖為完全無向圖。有n個頂點的有向圖有n(n-1) 條邊，則此圖為完全有向圖。鄰接頂點 如果(u, v)是E(G)中的一條邊，則稱u與v 互為鄰接頂點，邊(u, v)使得頂點u, v之間相關聯(lián) 。權 某些圖的邊具有與它相關的數(shù)，稱之為權。這種帶權圖叫做網(wǎng)絡。子圖 設有兩個圖 G(V, E) 和G(V, E)。若

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

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

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

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

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

8、j列1的個數(shù)可得頂點j的入度。在無向圖中，統(tǒng)計第i行(列)1的個數(shù)可得頂點i的度。網(wǎng)絡的鄰接矩陣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); /構造函數(shù) Graphmtx( delete VerticesList; delete Edge; ) T GetValue ( int i ) /取頂點 return i = 0 & i numVertices ? VerticesListi : NULL; E GetWeight (int v1, int v2 ) /取邊上的權 return v1!=-1&v2!=-1 ? Edgev1v2 : 0;用鄰接矩陣表示的圖的類的定義 int GetFirstN

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

13、 ( T vertex ) /給出頂點在圖中的位置 for ( i=1; i numVertices ) if (VerticesListi = vertex) return i; return 0; template Graphmtx:Graph( int sz)/構造函數(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;鄰接矩陣實現(xiàn)的部分圖操作（構造）template int Graphmtx:getFirstNeighbor(int v)/給出頂點位置v的第一個鄰接頂點的位置，如果找 不到，則函數(shù)返回-1。 if ( v != -1 ) for ( int col=0; col0 & EdgevcolmaxWeight ) return col; return -1; 鄰接矩陣實現(xiàn)的部分圖操作（找

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

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

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

18、&v1-1& v2numVertices&Edgev1v2=maxWeight) /插入條件 Edgev1v2=Edgev2v1=cost; numEdges+;return ture; else return false; 鄰接矩陣實現(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;鄰接矩陣實現(xiàn)的部分圖操作（刪除一條邊）template istream& operator istream&in,Graphmtx&G /通過從輸入流對象in輸入n個頂點信息和e條無向邊 的信息建立用鄰接矩陣表示的圖G。 /鄰接矩陣初始化的工作已經(jīng)在構造函數(shù)中完成。 int i, j, k, n, m; T e1, e2; E weight; innm; /輸入頂點數(shù)n和邊數(shù)m for (i=0; ie1;G.insertVertex(e1); i=0;通過輸入建立圖的鄰接矩陣表示 while (ie1e2weight; /輸入端點信息 j=G.getVertexPos(e1); k=

20、G.getVertexPos(e2); /查頂點號 if (j=-1|k=-1) cout邊兩端點信息有誤，重新輸入！endl; else G.inserEdge(j, k, weight); i+; return in;template ostream& operator (ostream& out,Graphmtx&G) /輸出圖的所有頂點和邊的信息 int i, j, k, n, m; T e1, e2; E w; n =G.NumberOfVertices(); m=G.NumberOfEdges(); outn,mendl; /輸出頂點數(shù)與邊數(shù) 輸出鄰接矩陣表示的圖的頂點和邊信息 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)無向圖的鄰接表把同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，鏈表的每一個結點代表一條邊，叫做邊結點，結點中保存有與該邊相關聯(lián)的另一頂點的頂點下標dest和指向同一鏈表中下一個邊結點的指針link。有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第i個邊鏈表鏈接的邊都是頂點i發(fā)出的邊。也叫做出邊表。在有向圖的逆鄰接表中，第i個邊鏈表鏈

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

23、(int num, E weight):dest(num), cost(weight), link(NULL) /構造函數(shù) bool perator!=(Edge&R)const /判邊不等否 return(dest!=R.dest) ? true : false; ; 鄰接表表示的圖的類定義template struct Vertex /頂點的定義 T data; /頂點的名字 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); /構造函數(shù) Graphlnk(); /析構函數(shù) T getValue(int i) /取位置為i的頂點中的值 return(i=0&iNumVertices) ? NodeTablei.data : 0; E getWeight(int v1,int v2); /返回邊(v1,v2)上的權值 bool insertVertex(const T& vertex); /插入一個頂點vertex b

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

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

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

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

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

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

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

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

33、/與頂點v相關聯(lián)的邊數(shù)減1 numVertices-; /圖的頂點個數(shù)減1 NodeTablev.data=NodeTablenumVertices.data; /填補 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)/在帶權圖中插入一條邊(v1,v2)，若此邊存在或參數(shù)不合理， 函數(shù)返回FALSE，否則返回TRUE。對于非帶權圖，最后一 個參數(shù)weight不要。算法中相應語句也不要。 if (v1=0&v1=0&v2numVertices) Edge *q,*p=NodeTablev1.adj; /v1對應的邊鏈表頭指針 while(p!=NULL&p-dest!=v2) /尋找鄰接頂點v2 p=p-link; if (p!=NULL) return false; /找到此邊，不插入 p=new Edge; q=new Edge; /否則創(chuàng)建新結點 p-dest=v2; p-cost

35、=weight; p-link=NodeTablev1.adj; /鏈入v1邊鏈表 NodeTablev1.adj=p;鄰接表部分成員函數(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對應邊鏈表中找被刪邊 q=p; p=p-link; if (p!=NULL) /找到被刪邊結點 if (p=s) NodeTablev1.adj=p-link; /該結點是邊鏈表首結點 else q-link=p-link; /不是，重新鏈接 delete p; else return false; /沒有找到被刪邊結點鄰接表部分成員函數(shù)的實現(xiàn)（刪除一條邊） p=NodeTablev2.adj; q=NULL, s=p; /v2對應邊鏈表中刪除 while (p-dest!=v1) q=p; p=p-link;

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

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

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

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

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

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

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

44、出發(fā)，進行類似的訪問， 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。TemplateVoid DFS (Graph& G, const T& v)/從頂點出發(fā)，對圖G進行深度優(yōu)先遍歷的主過程 int i，loc=G.NumberOfVertices()/取圖中的頂點個數(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)/子過程從頂點位置V出發(fā)，以深度優(yōu)先的次序訪問所有可讀入的尚未訪問過的頂點，算法中用到一個輔助數(shù)組visited,對已訪問過的頂點作訪問標記 CoutG.getValue(v)”;/訪問頂點v Visitedv=true; /頂點v做訪問標記 int w=G.getFirstNeighor(v); /找頂點v的第一個

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

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

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

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

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

51、 1534276 1247653 以上都錯 (2) 1534267 1726453 1354276 1247653 以上都錯 （1）1534276 （2）1354276例畫出圖中給出的無向圖的鄰接表表示，使得其中無向邊結點表中第一個頂點號小于第二個頂點號，同時請列出從頂點1開始的深度優(yōu)先和廣度優(yōu)先遍歷所得到的頂點序列和邊序列。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)當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷，可求得無向圖的所有連通分量。在算法中，需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生

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

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

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

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

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

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

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

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