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

1、圖的基本概念圖的存儲表示圖的遍歷與連通性 最小生成樹最短路徑 活動網(wǎng)絡(luò),第八章 圖,圖的基本概念,圖定義 圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph＝( V, E ) 其中 V = { x | x ? 某個數(shù)據(jù)對象} 是頂點(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 的一條單向通路, 它是有方向的。,,,,,,,,,,,,,,,,,,,有向圖與無向圖 在有向圖中，頂點(diǎn)對 是有序的。在無向圖中，頂點(diǎn)對(x, y)是無序的。完全圖 若有 n 個頂點(diǎn)的無向圖有 n(n-1)/2 條邊, 則此圖為完全無向圖。有 n

3、個頂點(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) 中的一條邊，則稱 u 與 v 互為鄰接頂點(diǎn)。子圖 設(shè)有兩個圖 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’? V 且 E‘?E, 則稱 圖G’ 是 圖G 的子圖。權(quán) 某些圖的邊具有與

4、它相關(guān)的數(shù), 稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。,,,,,,,,,0,1,2,3,,子圖,,,,,,0,1,3,,,,,,,0,1,2,3,,,,,0,2,3,頂點(diǎn)的度 一個頂點(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)過一些頂點(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ù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑 若路徑上各頂點(diǎn) v1,

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

7、連通圖的極大連通子圖叫做連通分量。強(qiáng)連通圖與強(qiáng)連通分量 在有向圖中, 若對于每一對頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的路徑, 則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。生成樹 一個連通圖的生成樹是其極小連通子圖，在n個頂點(diǎn)的情形下，有n-1條邊。,圖的抽象數(shù)據(jù)類型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 ); },,圖的存儲表示,在圖的鄰接矩陣表示中，有一個記錄各個頂點(diǎn)信息的頂點(diǎn)表，還有一個表示各個頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖 A = (V, E)是一個有 n 個頂點(diǎn)的圖, 圖的鄰接矩陣是一個二維數(shù)組 A.edge[n][n]，定義：,鄰接矩陣 (Adjacency Matr

10、ix),,,無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。,,,,,,,,,0,1,2,3,,0,,1,,2,,,在有向圖中, 統(tǒng)計第 i 行 1 的個數(shù)可得頂點(diǎn) i 的出度，統(tǒng)計第 j 列 1 的個數(shù)可得頂點(diǎn) j 的入度。在無向圖中, 統(tǒng)計第 i 行 (列) 1 的個數(shù)可得頂點(diǎn)i 的度。,網(wǎng)絡(luò)的鄰接矩陣,,,,,,,,,,,,,,,8,6,3,1,2,9,5,4,2,0,3,1,用鄰接矩陣表示的圖的類的定義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 的第一個鄰接頂點(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、一個鄰接頂點(diǎn) if ( v != -1 && w != -1 ) { for ( int j = w+1; j 0 && Edge[v][j] < MaxValue ) return j; } return -1;},鄰接表 (Adjacency List),無向圖的鄰接表 同一個頂點(diǎn)發(fā)出的邊鏈接在同

20、一個邊鏈表中，每一個鏈結(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)的其它信息。在鄰接表的邊鏈表中，各個邊結(jié)點(diǎn)的鏈入順序任意，視邊

22、結(jié)點(diǎn)輸入次序而定。設(shè)圖中有 n 個頂點(diǎn)，e 條邊，則用鄰接表表示無向圖時，需要 n 個頂點(diǎn)結(jié)點(diǎn)，2e 個邊結(jié)點(diǎn)；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需 n 個頂點(diǎn)結(jié)點(diǎn)，e 個邊結(jié)點(diǎn)。,鄰接表表示的圖的類定義#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 { //圖類priva

25、te:,Vertex * NodeTable; //頂點(diǎn)表 int numberVertices; //當(dāng)前頂點(diǎn)個數(shù) int MaxVertices; //最大頂點(diǎn)個數(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)個數(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 第一個鄰接頂點(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 后下一個鄰接頂點(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; //返回下一個鄰接頂點(diǎn)在鄰接表中位置 else p = p->link; } },,return -1; //沒有查到下一個鄰接頂點(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),在鄰接多重表中, 每一條邊只有一個邊結(jié)點(diǎn)。為有關(guān)邊的處理提供了方便。無向圖的情形邊結(jié)點(diǎn)的結(jié)構(gòu),mark vertex1 vertex2 path1 path2,,,,,其中, mark 是記錄是否處理過的標(biāo)記; vertex1和vertex2是該邊兩頂點(diǎn)位置。path1域是鏈接指針, 指向下一條依附頂點(diǎn)vertex1的邊；path2 是指向下一條依附頂點(diǎn)vertex2的邊鏈接指針。,頂點(diǎn)結(jié)點(diǎn)的結(jié)

39、構(gòu) 存儲頂點(diǎn)信息的結(jié)點(diǎn)表以順序表方式組織, 每一個頂點(diǎn)結(jié)點(diǎn)有兩個數(shù)據(jù)成員：其中，data 存放與該頂點(diǎn)相關(guān)的信息，F(xiàn)irstout 是指示第一條依附該頂點(diǎn)的邊的指針。在鄰接多重表中, 所有依附同一個頂點(diǎn)的邊都鏈接在同一個單鏈表中。,data Firstout,,需要時還可設(shè)置一個存放與該邊相關(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)。,有向圖的情形在用鄰接表表示有向圖時, 有時需要同時使用鄰接表和逆鄰接表。用有向圖的鄰接多重表(十字鏈表)可把兩個表結(jié)合起來

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)與該邊相同的下一條邊的指針。需要時還可有權(quán)值域cost。,頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu) 每個頂點(diǎn)有一個結(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ā)，沿著一 些邊訪遍圖中所有的頂點(diǎn)，且使每個頂點(diǎn)僅被訪問一次，就叫做圖的遍歷 ( Graph

44、 Traversal )。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個頂點(diǎn)之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組 visited [ ]。,輔助數(shù)組 visited [ ] 的初始狀態(tài)為 0, 在圖的遍歷過程中, 一旦某一個頂點(diǎn) i 被訪問, 就立即讓 visited [i] 為 1, 防止它被多次訪問。圖的遍歷的分類:深度優(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)先搜索過程 深度優(yōu)先生成樹,DFS 在訪問圖中某一起始頂點(diǎn) v 后, 由 v 出發(fā), 訪問它的任一鄰接頂點(diǎn) w1; 再從 w1 出發(fā),訪問與 w1鄰 接但還沒有訪問過的頂點(diǎn) w2; 然后再從 w2 出發(fā), 進(jìn)行類似的訪問, … 如此進(jìn)行下去, 直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。接著, 退回一步, 退到前一次剛訪問過的頂點(diǎn), 看是

47、否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有, 則訪問此頂點(diǎn), 之后再從此頂點(diǎn)出發(fā), 進(jìn)行與前述類似的訪問; 如果沒有, 就再退回一步進(jìn)行搜索。重復(fù)上述過程, 直到連通圖中所有頂點(diǎn)都被訪問過為止。,圖的深度優(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) << ‘ ’; //訪問頂點(diǎn) v visited[v] = 1; //頂點(diǎn) v 作訪問標(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 未訪問過, 遞歸訪問頂點(diǎn) w w = G.GetNextNeighbor ( v, w ); //取頂點(diǎn) v 排在 w 后的下一個鄰接頂點(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)先搜索過程 廣度優(yōu)先生成樹,,,,,,,,,I,BFS在訪問了起始頂點(diǎn) v 之后, 由 v 出發(fā), 依次訪問 v 的各個未被

51、訪問過的鄰接頂點(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)先搜索不是一個遞歸的過程。,為了實(shí)現(xiàn)逐層訪問, 算法中使用了一個隊列,以記憶正在訪問

52、的這一層和上一層的頂點(diǎn),以便于向下一層訪問。為避免重復(fù)訪問, 需要一個輔助數(shù)組 visited [ ]，給被訪問過的頂點(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)隊列 while ( !q.IsEmpty ( ) ) { //隊空搜索結(jié)束 q.GetFront(v); q.DeQueue ( ); int w = G.GetFirstNeighbor (v); while ( w != -1 ) {

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

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

56、有連通分量。在算法中, 需要對圖的每一個頂點(diǎn)進(jìn)行檢測：若已被訪問過，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個連通分量。對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。,,,,,,,,,,,,,,,,,,,,,,,A,C,D,E,,,,I,B,F,O,,G,,H,,J,,N,,M,,L,,K,非連通無向圖,,,,,,,,,,,,,,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] ) { //檢測頂點(diǎn)是否訪問過 DFS ( G, i, visited ); //未訪問, 出發(fā)訪問 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]; //訪問數(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 未訪問過 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)先遍歷, 建子樹 }}template void DFS_Tree ( Graph& G, Tree&T, TreeNode * rt, int v, int visited [ ] ) {,TreeNode * p; visited[v]

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

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 為根的子樹 } //鄰接頂點(diǎn) w 處理完 w = G.GetNextNeighbor ( v, w ); //取 v 的下一個鄰接頂點(diǎn) w } //

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

67、通分量。,在一個無向連通圖G中, 重連通分量可以利用深度優(yōu)先生成樹找到。在圖中各頂點(diǎn)旁標(biāo)明的深度優(yōu)先數(shù), 給出進(jìn)行深度優(yōu)先搜索時各頂點(diǎn)訪問的次序。深度優(yōu)先生成樹的根是關(guān)節(jié)點(diǎn)的充要條件是它至少有兩個子女。其它頂點(diǎn) u 是關(guān)節(jié)點(diǎn)的充要條件是它至少有一個子女 w, 從 w 出發(fā), 不能通過 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,,根有兩 個子女,,,關(guān)節(jié)點(diǎn),關(guān)節(jié)點(diǎn),,關(guān)節(jié)點(diǎn),,在圖G的每一個頂點(diǎn)上定義一個 low 值，low[u] 是從 u 或 u 的子孫出發(fā)通過回邊可以到達(dá)的最低深度優(yōu)先數(shù)。 low[u] = min { dfn[u],

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

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