同濟大學計算機編程課件c++ds08

1、圖的基本概念圖的存儲表示圖的遍歷與連通性 最小生成樹最短路徑 活動網(wǎng)絡,第八章 圖,圖的基本概念,圖定義 圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph＝( V, E ) 其中 V = { x | x ? 某個數(shù)據(jù)對象} 是頂點的有窮非空集合； E = {(x, y) | x, y ? V } 或 E

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

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

4、它相關的數(shù), 稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡。,,,,,,,,,0,1,2,3,,子圖,,,,,,0,1,3,,,,,,,0,1,2,3,,,,,0,2,3,頂點的度 一個頂點v的度是與它相關聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中, 頂點的度等于該頂點的入度與出度之和。頂點 v 的入度是以 v 為終點的有向邊的條數(shù), 記作 ID(v); 頂點 v 的出度是以 v 為始點的有向邊的條數(shù), 記作 OD(v)。路徑 在圖 G＝(V

5、, 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的邊。,路徑長度 非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑 若路徑上各頂點 v1,

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

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

10、ix),,,無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。,,,,,,,,,0,1,2,3,,0,,1,,2,,,在有向圖中, 統(tǒng)計第 i 行 1 的個數(shù)可得頂點 i 的出度，統(tǒng)計第 j 列 1 的個數(shù)可得頂點 j 的入度。在無向圖中, 統(tǒng)計第 i 行 (列) 1 的個數(shù)可得頂點i 的度。,網(wǎng)絡的鄰接矩陣,,,,,,,,,,,,,,,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 );}鄰接矩陣實現(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 ) {//給出頂點位置為 v 的第一個鄰接頂點的位置

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 ) {//給出頂點v的某鄰接頂點w的下

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

20、一個邊鏈表中，每一個鏈結(jié)點代表一條邊(邊結(jié)點), 結(jié)點中有另一頂點的下標 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)絡 (帶權(quán)圖) 的鄰接表,帶權(quán)圖的邊結(jié)點中保存該邊上的權(quán)值 cost。頂點 i 的邊鏈表的表頭指針 adj 在頂點表的下標為 i 的頂點記錄中，該記錄還保存了該頂點的其它信息。在鄰接表的邊鏈表中，各個邊結(jié)點的鏈入順序任意，視邊

22、結(jié)點輸入次序而定。設圖中有 n 個頂點，e 條邊，則用鄰接表表示無向圖時，需要 n 個頂點結(jié)點，2e 個邊結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需 n 個頂點結(jié)點，e 個邊結(jié)點。,鄰接表表示的圖的類定義#define DefaultSize 10template class Graph;template struct Edge { //邊結(jié)點friend class Graph; int de

23、st;//目標頂點下標 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 { //頂點friend class Graph ; Type data; //頂點數(shù)據(jù) Edge *adj; //邊鏈表頭指針}template class Graph { //圖類priva

25、te:,Vertex * NodeTable; //頂點表 int numberVertices; //當前頂點個數(shù) int MaxVertices; //最大頂點個數(shù) int numberEdges; //當前邊數(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)建頂點表 cin >> numberVertices; //輸入頂點個數(shù),for ( int i = 0; i > name; InsertVertex ( name ); } //輸入各頂點信息 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; //釋放頂點表},鄰接表部分成員函數(shù)的實現(xiàn)template int Graph ::GetVe

33、rtexPos ( const Type vertex ) {//根據(jù)頂點名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 ) {//查找頂點 v 第一個鄰接頂點在鄰接表中位置 if ( v != -1 ) { //若頂點存在 Edge * p = NodeTable[v].adj; if ( p != NULL ) return p->dest; } return -1;

35、 //若頂點不存在},template int Graph :: GetNextNeighbor ( int v, int w ) {//查找頂點 v 在鄰接頂點 w 后下一個鄰接頂點 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; //返回下一個鄰接頂點在鄰接表中位置 else p = p->link; } },,return -1; //沒有查到下一個鄰接頂點}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é)點。為有關邊的處理提供了方便。無向圖的情形邊結(jié)點的結(jié)構(gòu),mark vertex1 vertex2 path1 path2,,,,,其中, mark 是記錄是否處理過的標記; vertex1和vertex2是該邊兩頂點位置。path1域是鏈接指針, 指向下一條依附頂點vertex1的邊；path2 是指向下一條依附頂點vertex2的邊鏈接指針。,頂點結(jié)點的結(jié)

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

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

42、頂點相關的信息，指針Firstin指示以該頂點為始頂點的出邊表的第一條邊，F(xiàn)irstout指示以該頂點為終頂點的入邊表的第一條邊。,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,圖的遍歷與連通性,從已給的連通圖中某一頂點出發(fā)，沿著一 些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷 ( Graph

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

47、否還有其它沒有被訪問的鄰接頂點。如果有, 則訪問此頂點, 之后再從此頂點出發(fā), 進行與前述類似的訪問; 如果沒有, 就再退回一步進行搜索。重復上述過程, 直到連通圖中所有頂點都被訪問過為止。,圖的深度優(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) << ‘ ’; //訪問頂點 v visited[v] = 1; //頂點 v 作訪問標記 int w = G.GetFirstNeighbo

49、r (v); while ( w != -1 ) { //若鄰接頂點 w 存在 if ( !visited[w] ) DFS ( G, w, visited ); //若頂點 w 未訪問過, 遞歸訪問頂點 w w = G.GetNextNeighbor ( v, w ); //取頂點 v 排在 w 后的下一個鄰接頂點 }},,廣度優(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在訪問了起始頂點 v 之后, 由 v 出發(fā), 依次訪問 v 的各個未被

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

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

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

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

56、有連通分量。在算法中, 需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(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] ) { //檢測頂點是否訪問過 DFS ( G, i, visited ); //未訪問, 出發(fā)訪問 OutputNewComponent ( ); //連通分量 },,,,,,,,,,,【例】以深度優(yōu)先搜索方法從頂點 出發(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++ ) //遍歷所有頂點 if ( !visited[i] ) { //頂點 i 未訪問過 if (

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

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

63、 = 1; //頂點v作訪問過標志 int w = G.GetFirstNeighbor (v); //取頂點v的第一個鄰接頂點w int FirstChild = 1; //第一個未訪問子女應是v的左子女 while ( w != -1 ) { //鄰接頂點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 為根的子樹 } //鄰接頂點 w 處理完 w = G.GetNextNeighbor ( v, w ); //取 v 的下一個鄰接頂點 w } //

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

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

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

70、template void DfnLow ( Graph& G, int x ) {//從頂點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是