同濟(jì)大學(xué)計(jì)算機(jī)編程課件c++ds08

1、圖的基本概念圖的存儲(chǔ)表示圖的遍歷與連通性 最小生成樹(shù)最短路徑 活動(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ù)對(duì)象} 是頂點(diǎn)的有窮非空集合； E = {(x, y) | x, y ? V } 或 E

2、 = { | x, y ? V && Path (x, y)} 是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。Path (x, y)表示從 x 到 y 的一條單向通路, 它是有方向的。,,,,,,,,,,,,,,,,,,,有向圖與無(wú)向圖 在有向圖中，頂點(diǎn)對(duì) 是有序的。在無(wú)向圖中，頂點(diǎn)對(duì)(x, y)是無(wú)序的。完全圖 若有 n 個(gè)頂點(diǎn)的無(wú)向圖有 n(n-1)/2 條邊, 則此圖為完全無(wú)向圖。有 n

3、個(gè)頂點(diǎn)的有向圖有n(n-1) 條邊, 則此圖為完全有向圖。,,,,,,,,,,,,,,,,,,,,,,,,,,0,0,0,0,1,1,1,1,2,2,2,2,6,5,4,3,3,,,,鄰接頂點(diǎn) 如果 (u, v) 是 E(G) 中的一條邊，則稱(chēng) u 與 v 互為鄰接頂點(diǎn)。子圖 設(shè)有兩個(gè)圖 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’? V 且 E‘?E, 則稱(chēng) 圖G’ 是 圖G 的子圖。權(quán) 某些圖的邊具有與

4、它相關(guān)的數(shù), 稱(chēng)之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。,,,,,,,,,0,1,2,3,,子圖,,,,,,0,1,3,,,,,,,0,1,2,3,,,,,0,2,3,頂點(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

5、, E) 中, 若從頂點(diǎn) vi 出發(fā), 沿一些邊經(jīng)過(guò)一些頂點(diǎn) vp1, vp2, …, vpm，到達(dá)頂點(diǎn)vj。則稱(chēng)頂點(diǎn)序列 (vi vp1 vp2 ... vpm vj) 為從頂點(diǎn)vi 到頂點(diǎn) vj 的路徑。它經(jīng)過(guò)的邊(vi, vp1)、(vp1, vp2)、...、(vpm, vj) 應(yīng)是屬于E的邊。,路徑長(zhǎng)度 非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。簡(jiǎn)單路徑 若路徑上各頂點(diǎn) v1,

6、v2,...,vm 均不 互相重復(fù), 則稱(chēng)這樣的路徑為簡(jiǎn)單路徑?；芈?若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn)vm 重合, 則稱(chēng)這樣的路徑為回路或環(huán)。,,,,,,,,,,,0,1,2,3,,,,,,,,,,,0,1,2,3,,,,,,,,,,,0,1,2,3,,,,,,,,,,,,連通圖與連通分量 在無(wú)向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱(chēng)頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱(chēng)此圖是連通圖。非

7、連通圖的極大連通子圖叫做連通分量。強(qiáng)連通圖與強(qiáng)連通分量 在有向圖中, 若對(duì)于每一對(duì)頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的路徑, 則稱(chēng)此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。生成樹(shù) 一個(gè)連通圖的生成樹(shù)是其極小連通子圖，在n個(gè)頂點(diǎn)的情形下，有n-1條邊。,圖的抽象數(shù)據(jù)類(lèi)型class Graph {public: Graph ( ); void InsertVerte

8、x ( Type & vertex ); void InsertEdge ( int v1, int v2, int weight ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); int IsEmpty ( ); Type GetWeight ( int v1, int v2 );

9、 int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); },,圖的存儲(chǔ)表示,在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖 A = (V, E)是一個(gè)有 n 個(gè)頂點(diǎn)的圖, 圖的鄰接矩陣是一個(gè)二維數(shù)組 A.edge[n][n]，定義：,鄰接矩陣 (Adjacency Matr

10、ix),,,無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的;有向圖的鄰接矩陣可能是不對(duì)稱(chēng)的。,,,,,,,,,0,1,2,3,,0,,1,,2,,,在有向圖中, 統(tǒng)計(jì)第 i 行 1 的個(gè)數(shù)可得頂點(diǎn) i 的出度，統(tǒng)計(jì)第 j 列 1 的個(gè)數(shù)可得頂點(diǎn) j 的入度。在無(wú)向圖中, 統(tǒng)計(jì)第 i 行 (列) 1 的個(gè)數(shù)可得頂點(diǎn)i 的度。,網(wǎng)絡(luò)的鄰接矩陣,,,,,,,,,,,,,,,8,6,3,1,2,9,5,4,2,0,3,1,用鄰接矩陣表示的圖的類(lèi)的定義cons

11、t int MaxValue = ……;const int MaxEdges = 50;const int MaxVertices = 10;,template class Graph {private: Type VerticesList[MaxVertices]; float Edge[MaxVertices][MaxVertices]; int numberEdges; int n

12、umberVertices; int GetVertexPos ( const Type vertex ) { for ( int i = 0; i < numberVertices; i++ ) if ( VerticesList[i] == Vertex ) return i; return -1; },public: Graph ( int sz = MaxE

13、dges ); int GraphEmpty ( )const { return numberEdges == 0; } int GraphFull( ) const { return numberVertices == MaxVertices || numberEdges == MaxEdges; } int NumberOfVerti

14、ces ( ) { return numberVertices; } int NumberOfEdges ( ) { return numberEdges; },Type GetValue ( int i ) { return i >= 0 && i <= numberVertices ? VerticesList

15、[i] : NULL; } float GetWeight ( int u, int v ) { if (u != -1 && v != -1) return Edge[u][v]; else return 0; } int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v, int w

16、); void InsertVertex ( const Type vertex ); void InsertEdge ( int u, int v, float weight );,void RemoveVertex ( int v ); void RemoveEdge ( int u, int v );}鄰接矩陣實(shí)現(xiàn)的部分圖操作template Graph :: Graph ( int

17、 sz ) { //構(gòu)造函數(shù) for ( int i = 0; i < sz; i++ ) for ( int j = 0; j < sz; j++ ) Edge[i][j] = 0; NumberEdges = 0;},template int Graph ::GetFirstNeighbor ( const int v ) {//給出頂點(diǎn)位置為 v 的第一個(gè)鄰接頂點(diǎn)的位置

18、 if ( v != -1 ) { for ( int j = 0; j 0 && Edge[v][j] < MaxValue ) return j; } else return -1;},template int Graph ::GetNextNeighbor ( int v, int w ) {//給出頂點(diǎn)v的某鄰接頂點(diǎn)w的下

19、一個(gè)鄰接頂點(diǎn) if ( v != -1 && w != -1 ) { for ( int j = w+1; j 0 && Edge[v][j] < MaxValue ) return j; } return -1;},鄰接表 (Adjacency List),無(wú)向圖的鄰接表 同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同

20、一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn)), 結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo) dest 和指針 link。,,,,,,,,A,B,C,D,data adj,,,ABCD,,,,0123,,,,,,dest link,,,,,,,,,,,,,,dest link,?,?,?,?,1,3,0,2,1,0,有向圖的鄰接表和逆鄰接表,,,,A,,B,,C,,,data adj,,,ABC,,,012,,,,dest link,,

21、,,,,,dest link,?,鄰接表 (出邊表),data adj,,,ABC,,,012,,,,dest link,,,,逆鄰接表 (入邊表),,,,1,0,2,?,?,?,?,?,0,1,1,網(wǎng)絡(luò) (帶權(quán)圖) 的鄰接表,帶權(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)的鏈入順序任意，視邊

22、結(jié)點(diǎn)輸入次序而定。設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則用鄰接表表示無(wú)向圖時(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)。,鄰接表表示的圖的類(lèi)定義#define DefaultSize 10template class Graph;template struct Edge { //邊結(jié)點(diǎn)friend class Graph; int de

23、st;//目標(biāo)頂點(diǎn)下標(biāo) float cost; //邊上的權(quán)值 Edge * link; //下一邊鏈接指針 Edge ( ) { } //構(gòu)造函數(shù) Edge ( int D, float C ) : dest (D), cost (C), link (NULL) { },in

24、t operator != ( Edge& E ) const { return dest != E.dest; } }template struct Vertex { //頂點(diǎn)friend class Graph ; Type data; //頂點(diǎn)數(shù)據(jù) Edge *adj; //邊鏈表頭指針}template class Graph { //圖類(lèi)priva

25、te:,Vertex * NodeTable; //頂點(diǎn)表 int numberVertices; //當(dāng)前頂點(diǎn)個(gè)數(shù) int MaxVertices; //最大頂點(diǎn)個(gè)數(shù) int numberEdges; //當(dāng)前邊數(shù) int GetVertexPos ( const Type vertex );public:

26、Graph ( int sz ); ~Graph ( ); int GraphEmpty ( ) const { return numberEdges == 0; },int GraphFull ( ) const { return numberVertices == MaxVertices; } Type GetValue ( int i ) { return i

27、 >= 0 && i < numberVertices ? NodeTable[i].data : NULL; } int NumberOfVertices ( ) { return numberVertices; } int NumberOfEdges ( ) { return numberEdges; } void InsertVe

28、rtex ( Type vertex ); void RemoveVertex ( int v );,void InsertEdge ( int u, int v, float weight ); void RemoveEdge ( int u, int v ); float GetWeight ( int u, int v ); int GetFirstNeighbor ( int v );

29、 int GetNextNeighbor ( int v, int w );},鄰接表的構(gòu)造函數(shù)和析構(gòu)函數(shù)template Graph :: Graph ( int sz = DefaultSize ) : MaxVertices (sz) { int n, e, k, i, j; Type name, tail, head; float weight; NodeTab

30、le = new Vertex [sz]; //創(chuàng)建頂點(diǎn)表 cin >> numberVertices; //輸入頂點(diǎn)個(gè)數(shù),for ( int i = 0; i > name; InsertVertex ( name ); } //輸入各頂點(diǎn)信息 cin >> e;

31、 //輸入邊條數(shù) for ( i = 0; i > tail >> head >> weight; k = GetVertexPos ( tail ); j = GetVertexPos ( head ); InsertEdge ( k, j, weight ); //插入邊 }},templat

32、e Graph :: ~Graph ( ) { for ( int i = 0; i link; delete p; p = NodeTable[i].adj; } } delete [ ] NodeTable; //釋放頂點(diǎn)表},鄰接表部分成員函數(shù)的實(shí)現(xiàn)template int Graph ::GetVe

33、rtexPos ( const Type vertex ) {//根據(jù)頂點(diǎn)名vertex查找它在鄰接表中位置 for ( int i = 0; i < numberVertices; i++ ) if ( NodeTable[i].data == vertex ) return i; return -1;},template int Graph ::GetFirst

34、Neighbor ( int v ) {//查找頂點(diǎn) v 第一個(gè)鄰接頂點(diǎn)在鄰接表中位置 if ( v != -1 ) { //若頂點(diǎn)存在 Edge * p = NodeTable[v].adj; if ( p != NULL ) return p->dest; } return -1;

35、 //若頂點(diǎn)不存在},template int Graph :: GetNextNeighbor ( int v, int w ) {//查找頂點(diǎn) v 在鄰接頂點(diǎn) w 后下一個(gè)鄰接頂點(diǎn) if ( v != -1 ) { Edge * p = NodeTable[v].adj; while ( p != NULL ) { if ( p->dest == w &a

36、mp;& p->link != NULL ) return p->link->dest; //返回下一個(gè)鄰接頂點(diǎn)在鄰接表中位置 else p = p->link; } },,return -1; //沒(méi)有查到下一個(gè)鄰接頂點(diǎn)}template float Graph :: GetWeight ( int u, int v

37、) { if ( u != -1 && v != -1 ) { Edge *p = NodeTable[u].adj; while ( p != NULL ) if ( p->dest == v ) return p->cost; else p = p->link; } return 0;},鄰接多重表 (Adjacency

38、Multilist),在鄰接多重表中, 每一條邊只有一個(gè)邊結(jié)點(diǎn)。為有關(guān)邊的處理提供了方便。無(wú)向圖的情形邊結(jié)點(diǎn)的結(jié)構(gòu),mark vertex1 vertex2 path1 path2,,,,,其中, mark 是記錄是否處理過(guò)的標(biāo)記; vertex1和vertex2是該邊兩頂點(diǎn)位置。path1域是鏈接指針, 指向下一條依附頂點(diǎn)vertex1的邊；path2 是指向下一條依附頂點(diǎn)vertex2的邊鏈接指針。,頂點(diǎn)結(jié)點(diǎn)的結(jié)

39、構(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è)單鏈表中。,data Firstout,,需要時(shí)還可設(shè)置一個(gè)存放與該邊相關(guān)的權(quán)值的域 cost。,,,,鄰接多重表的結(jié)構(gòu),,,,,,,,,,,,,,mark vtx1 vtx2 path1 pa

40、th2,,,,,,,? ?,? ?,0 1,0 2,1 3,e1,e2,e3,data Fout,,,,,,,,,,,,,,,,,,,,,A,B,C,D,0,1,2,3,,,,,,e1,e2,e3,A,B,C,D,,從頂點(diǎn) i 出發(fā), 可以循鏈找到所有依附于該頂點(diǎn)的邊，也可以找到它的所有鄰接頂點(diǎn)。,有向圖的情形在用鄰接表表示有向圖時(shí), 有時(shí)需要同時(shí)使用鄰接表和逆鄰接表。用有向圖的鄰接多重表(十字鏈表)可把兩個(gè)表結(jié)合起來(lái)

41、表示。邊結(jié)點(diǎn)的結(jié)構(gòu),mark vertex1 vertex2 path1 path2,,,,,其中，mark是處理標(biāo)記；vertex1和vertex2指明該有向邊始頂點(diǎn)和終頂點(diǎn)的位置。path1是指向始頂點(diǎn)與該邊相同的下一條邊的指針；path2是指向終頂點(diǎn)與該邊相同的下一條邊的指針。需要時(shí)還可有權(quán)值域cost。,頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu) 每個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)，它相當(dāng)于出邊表和入邊表的表頭結(jié)點(diǎn)：其中，數(shù)據(jù)成員data存放與該

42、頂點(diǎn)相關(guān)的信息，指針Firstin指示以該頂點(diǎn)為始頂點(diǎn)的出邊表的第一條邊，F(xiàn)irstout指示以該頂點(diǎn)為終頂點(diǎn)的入邊表的第一條邊。,data Firstin Firstout,,,,,,鄰接多重表的結(jié)構(gòu),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,mark vtx1 vtx2 path1 path2,,,,,,,?,?,? ?,? ?,? ?,? ?,0 1,0 3,1 2,2

43、 3,3 4,4 0,e1,e2,e3,e4,e5,e6,data Fin Fout,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,A,B,C,D,E,0,1,2,3,4,,,,,,,,,,e1,e2,e3,e4,e5,e6,A,B,C,D,E,圖的遍歷與連通性,從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一 些邊訪(fǎng)遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次，就叫做圖的遍歷 ( Graph

44、 Traversal )。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪(fǎng)問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。為了避免重復(fù)訪(fǎng)問(wèn)，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)的輔助數(shù)組 visited [ ]。,輔助數(shù)組 visited [ ] 的初始狀態(tài)為 0, 在圖的遍歷過(guò)程中, 一旦某一個(gè)頂點(diǎn) i 被訪(fǎng)問(wèn), 就立即讓 visited [i] 為 1, 防止它被多次訪(fǎng)問(wèn)。圖的遍歷的分類(lèi):深度優(yōu)先搜索

45、 DFS (Depth First Search)廣度優(yōu)先搜索 BFS (Breadth First Search),,,,,,,,深度優(yōu)先搜索DFS ( Depth First Search ),深度優(yōu)先搜索的示例,,,,,,,A,C,D,E,,,,,G,B,F,I,,H,,,,,,,,,,A,C,D,E,,,,,G,B,F,I,,H,1,2,3,4,,,,,,,,,5,,,,,,,,,6,7,8,9,

46、1,2,3,4,5,6,7,8,9,前進(jìn),,回退,,深度優(yōu)先搜索過(guò)程 深度優(yōu)先生成樹(shù),DFS 在訪(fǎng)問(wèn)圖中某一起始頂點(diǎn) v 后, 由 v 出發(fā), 訪(fǎng)問(wèn)它的任一鄰接頂點(diǎn) w1; 再?gòu)?w1 出發(fā),訪(fǎng)問(wèn)與 w1鄰 接但還沒(méi)有訪(fǎng)問(wèn)過(guò)的頂點(diǎn) w2; 然后再?gòu)?w2 出發(fā), 進(jìn)行類(lèi)似的訪(fǎng)問(wèn), … 如此進(jìn)行下去, 直至到達(dá)所有的鄰接頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)的頂點(diǎn) u 為止。接著, 退回一步, 退到前一次剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn), 看是

47、否還有其它沒(méi)有被訪(fǎng)問(wèn)的鄰接頂點(diǎn)。如果有, 則訪(fǎng)問(wèn)此頂點(diǎn), 之后再?gòu)拇隧旤c(diǎn)出發(fā), 進(jìn)行與前述類(lèi)似的訪(fǎng)問(wèn); 如果沒(méi)有, 就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程, 直到連通圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。,圖的深度優(yōu)先搜索算法template void DFS (Graph& G) { int n = G.NumberOfVertices( ); static int * visited = new int [n]

48、; for ( int i = 0; i ,void DFS ( Graph& G, int v, int visited [ ] ) { cout << G.GetValue (v) << ‘ ’; //訪(fǎng)問(wèn)頂點(diǎn) v visited[v] = 1; //頂點(diǎn) v 作訪(fǎng)問(wèn)標(biāo)記 int w = G.GetFirstNeighbo

49、r (v); while ( w != -1 ) { //若鄰接頂點(diǎn) w 存在 if ( !visited[w] ) DFS ( G, w, visited ); //若頂點(diǎn) w 未訪(fǎng)問(wèn)過(guò), 遞歸訪(fǎng)問(wèn)頂點(diǎn) w w = G.GetNextNeighbor ( v, w ); //取頂點(diǎn) v 排在 w 后的下一個(gè)鄰接頂點(diǎn) }},,廣度優(yōu)先搜索BFS (

50、 Breadth First Search ),廣度優(yōu)先搜索的示例,,,,,,,,,,,,,A,C,D,E,,,,,G,B,F,I,,H,,,,,,,,,,A,C,D,E,,,,G,B,F,,H,1,2,3,4,,,5,,,,,,,6,7,8,9,1,2,3,4,5,6,7,8,9,廣度優(yōu)先搜索過(guò)程 廣度優(yōu)先生成樹(shù),,,,,,,,,I,BFS在訪(fǎng)問(wèn)了起始頂點(diǎn) v 之后, 由 v 出發(fā), 依次訪(fǎng)問(wèn) v 的各個(gè)未被

51、訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn) w1, w2, …, wt, 然后再順序訪(fǎng)問(wèn) w1, w2, …, wt 的所有還未被訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn)。再?gòu)倪@些訪(fǎng)問(wèn)過(guò)的頂點(diǎn)出發(fā)，再訪(fǎng)問(wèn)它們的所有還未被訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn)，… 如此做下去，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。廣度優(yōu)先搜索是一種分層的搜索過(guò)程, 每向前走一步可能訪(fǎng)問(wèn)一批頂點(diǎn), 不像深度優(yōu)先搜索那樣有往回退的情況。因此, 廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程。,為了實(shí)現(xiàn)逐層訪(fǎng)問(wèn), 算法中使用了一個(gè)隊(duì)列,以記憶正在訪(fǎng)問(wèn)

52、的這一層和上一層的頂點(diǎn),以便于向下一層訪(fǎng)問(wèn)。為避免重復(fù)訪(fǎng)問(wèn), 需要一個(gè)輔助數(shù)組 visited [ ]，給被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)加標(biāo)記。,圖的廣度優(yōu)先搜索算法template void BFS ( Graph & G, int v ) { int n = G.NumberOfVertices( ); int * visited = new int[n]; for ( int i = 0; i <

53、 n; i++ ) visited[i] = 0;,cout q; q.EnQueue (v); //進(jìn)隊(duì)列 while ( !q.IsEmpty ( ) ) { //隊(duì)空搜索結(jié)束 q.GetFront(v); q.DeQueue ( ); int w = G.GetFirstNeighbor (v); while ( w != -1 ) {

54、//若鄰接頂點(diǎn) w 存在 if ( !visited[w] ) { //未訪(fǎng)問(wèn)過(guò) cout << G.GetValue (w) << ‘ ’; visited[w] = 1; q.EnQueue (w); } w = G.GetNextNeighbor (v, w); }

55、 //重復(fù)檢測(cè) v 的所有鄰接頂點(diǎn),} //外層循環(huán)，判隊(duì)列空否 delete [ ] visited; },連通分量 (Connected component),當(dāng)無(wú)向圖為非連通圖時(shí), 從圖中某一頂點(diǎn)出發(fā), 利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn), 只能訪(fǎng)問(wèn)到該頂點(diǎn)所在的最大連通子圖(連通分量)的所有頂點(diǎn)。,,若從無(wú)向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷, 可求得無(wú)向圖的所

56、有連通分量。在算法中, 需要對(duì)圖的每一個(gè)頂點(diǎn)進(jìn)行檢測(cè)：若已被訪(fǎng)問(wèn)過(guò)，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪(fǎng)問(wèn)，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個(gè)連通分量。對(duì)于非連通的無(wú)向圖，所有連通分量的生成樹(shù)組成了非連通圖的生成森林。,,,,,,,,,,,,,,,,,,,,,,,A,C,D,E,,,,I,B,F,O,,G,,H,,J,,N,,M,,L,,K,非連通無(wú)向圖,,,,,,,,,,,,,,A,,H,,K,,,,,C,

57、D,E,,,,I,B,F,O,,G,,J,,N,,M,,L,,,,,,,,,,,,,非連通圖的連通分量,確定連通分量的算法 template void Components ( Graph & G ) { int n = G.NumberOfVertices( ); static int *visited = new int[n]; for ( int i = 0; i < n; i+

58、+ ) visited[i] = 0; for ( i = 0; i < n; i++ ) if ( !visited[i] ) { //檢測(cè)頂點(diǎn)是否訪(fǎng)問(wèn)過(guò) DFS ( G, i, visited ); //未訪(fǎng)問(wèn), 出發(fā)訪(fǎng)問(wèn) OutputNewComponent ( ); //連通分量 },,,,,,,,,,,【例】以深度優(yōu)先搜索方法從頂點(diǎn) 出發(fā)遍歷圖,

59、建立深度優(yōu)先生成森林。,A,B,C,D,E,F,G,,,,,,A,A,B,D,E,C,F,G,有向圖,深度優(yōu)先生成森林,,,,,,,delete [ ] visited; },template void DFS_Forest ( Graph& G, Tree &T ) { TreeNode * rt, * subT; int n = G.NumberOf

60、Vertices( ); static int *visited = new int[n]; //訪(fǎng)問(wèn)數(shù)組 for ( int i = 0; i < n; i++ ) visited [i] = 0; for ( i = 0; i < n; i++ ) //遍歷所有頂點(diǎn) if ( !visited[i] ) { //頂點(diǎn) i 未訪(fǎng)問(wèn)過(guò) if (

61、T.IsEmpty ( ) ) //原為空森林,建根 subT = rt = T.BuildRoot( G.GetValue(i) ); //頂點(diǎn) i 的值成為根 rt 的值,else subT = T.InsertRightSibling (subT, G.GetValue(i)); //頂點(diǎn) i 的值成為 sub

62、T 右兄弟的值 DFS_Tree ( G, T, subT, i, visited ); //從頂點(diǎn) i 出發(fā)深度優(yōu)先遍歷, 建子樹(shù) }}template void DFS_Tree ( Graph& G, Tree&T, TreeNode * rt, int v, int visited [ ] ) {,TreeNode * p; visited[v]

63、 = 1; //頂點(diǎn)v作訪(fǎng)問(wèn)過(guò)標(biāo)志 int w = G.GetFirstNeighbor (v); //取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)w int FirstChild = 1; //第一個(gè)未訪(fǎng)問(wèn)子女應(yīng)是v的左子女 while ( w != -1 ) { //鄰接頂點(diǎn)w存在 if ( ! visited [w] ) { //w未訪(fǎng)問(wèn)過(guò)

64、, 將成為v的子女 if ( FirstChild ) { p = T.InsertLeftChild ( rt, G.GetValue(w) ); //p插入為rt的左子女,FirstChild = 0; //建右兄弟 } else p = T.InsertRightSibling ( p, G.GetV

65、alue(w) ); // p 插入為 p 的左子女 DFS_Tree ( G, T, p, w, visited ); //遞歸建立 w 的以 p 為根的子樹(shù) } //鄰接頂點(diǎn) w 處理完 w = G.GetNextNeighbor ( v, w ); //取 v 的下一個(gè)鄰接頂點(diǎn) w } //

66、回到 while 判鄰接頂點(diǎn) w 存在},,重連通分量 (Biconnected Component),在無(wú)向連通圖G中, 當(dāng)且僅當(dāng)刪去G中的頂點(diǎn)v及所有依附于v的所有邊后, 可將圖分割成兩個(gè)或兩個(gè)以上的連通分量，則稱(chēng)頂點(diǎn)v為關(guān)節(jié)點(diǎn)。沒(méi)有關(guān)節(jié)點(diǎn)的連通圖叫做重連通圖。在重連通圖上, 任何一對(duì)頂點(diǎn)之間至少存在有兩條路徑, 在刪去某個(gè)頂點(diǎn)及與該頂點(diǎn)相關(guān)聯(lián)的邊時(shí), 也不破壞圖的連通性。一個(gè)連通圖G如果不是重連通圖，那么它可以包括幾個(gè)重連

67、通分量。,在一個(gè)無(wú)向連通圖G中, 重連通分量可以利用深度優(yōu)先生成樹(shù)找到。在圖中各頂點(diǎn)旁標(biāo)明的深度優(yōu)先數(shù), 給出進(jìn)行深度優(yōu)先搜索時(shí)各頂點(diǎn)訪(fǎng)問(wèn)的次序。深度優(yōu)先生成樹(shù)的根是關(guān)節(jié)點(diǎn)的充要條件是它至少有兩個(gè)子女。其它頂點(diǎn) u 是關(guān)節(jié)點(diǎn)的充要條件是它至少有一個(gè)子女 w, 從 w 出發(fā), 不能通過(guò) w、w 的子孫及一條回邊所組成的路徑到達(dá) u 的祖先。,,,,,,,,,,,,,,,,,,,,,,,,A,B,C,D,E,F,G,H,I,J,,,,

68、,,,,,,,,,,,,,,,,,,A,B,C,D,E,F,G,H,J,,,,,,,,,,,,,,,,,,,,,A,B,C,D,E,F,G,H,J,I,I,1,2,3,4,5,6,7,8,9,10,,根有兩 個(gè)子女,,,關(guān)節(jié)點(diǎn),關(guān)節(jié)點(diǎn),,關(guān)節(jié)點(diǎn),,在圖G的每一個(gè)頂點(diǎn)上定義一個(gè) low 值，low[u] 是從 u 或 u 的子孫出發(fā)通過(guò)回邊可以到達(dá)的最低深度優(yōu)先數(shù)。 low[u] = min { dfn[u],

69、 min{ low[w] | w 是 u 的一個(gè)子女 }, min{ dfn[x] | (u, x) 是一條回邊 } }u 是關(guān)節(jié)點(diǎn)的充要條件是： u 是具有兩個(gè)以上子女的生成樹(shù)的根 u 不是根，但它有一個(gè)子女 w，使得 low[w] ? dfn[u]這時(shí) w 及其子孫不存在指向頂點(diǎn) u 的祖先的回邊。,計(jì)算dfn與low的算法 (1)

70、template void DfnLow ( Graph& G, int x ) {//從頂點(diǎn)x開(kāi)始深度優(yōu)先搜索 int num = 1; //num是訪(fǎng)問(wèn)計(jì)數(shù)器 int n = G.NumberOfVertices( ); static int * dfn = new int[n]; static int * low = new int[n]; //dfn是