數(shù)據(jù)結(jié)構(gòu)第七章 第三節(jié)A.ppt

1、7.4.4 關(guān)節(jié)點(diǎn)和重連通分量,定義：無向連通圖G=(V, E)中，如果刪去頂點(diǎn)v(以及與v關(guān)聯(lián)的邊)，G的剩余部分就變成不連通，則頂點(diǎn)v稱為G的一個(gè)關(guān)節(jié)點(diǎn)（articulation point）,不存在關(guān)節(jié)點(diǎn)的無向連通圖稱為雙連通圖（biconnected graph）,也稱為二連通圖,應(yīng)用：通信、交通、軍事、集成電路設(shè)計(jì)等,A,L,B,M,C,D,E,F,G,H,I,J,K,A,L,M,C,D,E,F,G,H,I,J,K,A,B,D,G,A,L,B,M,C,D,E,F,G,H,I,J,K,A,A,B,D,G,（1）生成樹的根有兩棵或以上的子樹,（2）生成樹的非葉子結(jié)點(diǎn)v, 其某棵子樹的根和

2、子樹中的其它結(jié)點(diǎn)均沒有指向v的祖先的回邊,A,B,G,D,關(guān)節(jié)點(diǎn)的條件：,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,visitedv深度優(yōu)先遍歷時(shí)訪問v的次序號(hào),w頂點(diǎn)v在深度優(yōu)先搜索樹上的孩子結(jié)點(diǎn),k頂點(diǎn)v在深度優(yōu)先搜索樹上由回邊連接的祖先結(jié)點(diǎn),(v, w), (v, k) E,G=(V, E),回溯函數(shù),v,w,k,1,2,3,4,5,6,7,8,9,10,11,12,13,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序

3、,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,A,lowv=mi

4、n(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.da

5、ta,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,2,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,2,A,lowv=

6、min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,2,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6

7、,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,2,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2

8、,2,3,3,4,4,2,1,5,5,6,6,7,7,2,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,2,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.ve

9、rticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,2,8,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,vis

10、itedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,8,2,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1

11、,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,2,5,5,8,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,2,5,5

12、,5,8,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,2,5,5,5,8,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,

13、G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,2,5,5,5,8,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3

14、,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,2,5,5,5,8,10,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visited

15、i,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,2,5,5,5,8,5,10,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,1

16、1,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,2,5,5,5,8,5,10,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K

17、,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,12,12,1,8,2,5,5,5,8,5,10,1,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3

18、,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,12,12,1,8,2,5,5,5,8,5,10,1,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5

19、,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,12,12,1,8,1,9,2,1,5,5,5,8,5,10,1,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7

20、,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,12,12,1,8,1,9,1,10,1,2,1,5,5,5,8,5,10,1,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,

21、8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,12,12,1,8,1,9,1,10,1,11,1,1,2,1,5,5,5,8,5,10,1,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,5,5,6,

22、6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,12,12,1,8,1,9,1,10,1,11,1,1,2,1,5,5,5,8,5,10,1,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1,1,2,2,3,3,4,4,2,1,

23、5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,12,12,1,8,1,9,13,13,1,12,1,10,1,11,1,1,2,1,5,5,5,8,5,10,1,1,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,i,G.verticsi.data,visitedi,lowi,求low值的順序,0,1,2,3,4,5,6,i,G.verticsi.data,visitedi,lowi,求low值的順序,7,8,9,10,11,12,A,B,C,D,E,F,G,H,I,J,K,L,M,1

24、,1,2,2,3,3,4,4,2,1,5,5,6,6,7,7,8,8,9,9,8,2,5,3,5,4,5,5,10,10,11,11,10,6,5,7,12,12,1,8,1,9,13,13,1,12,1,13,1,10,1,11,1,1,1,2,1,5,5,5,8,5,10,1,1,void FindArticul(ALGraph G) / 連通圖G以鄰接表作存儲(chǔ)結(jié)構(gòu)，查找并輸出G上全部關(guān)節(jié)點(diǎn)。 / 全局量count對(duì)訪問計(jì)數(shù)。 count=1; low0=visited0=1; / 設(shè)定鄰接表上0號(hào)頂點(diǎn)為生成樹的根 for(i=1;iadjvex; DFSArticul(G,v); / 從

25、第v頂點(diǎn)出發(fā)深度優(yōu)先查找關(guān)節(jié)點(diǎn) if(countnextarc) p=p-nextarc; v=p-adjvex; if(visitedv=0) DFSArticul(G,v); /while /if /FindArticul,A,A,B,G,D,A,A,B,G,D,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc;p;p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-

26、adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,void FindArticul(ALGraph G) / 連通圖G以鄰接表作存儲(chǔ)結(jié)構(gòu)，查找并輸出G上全部關(guān)節(jié)點(diǎn)。 / 全局量count對(duì)訪問計(jì)數(shù)。 count=

27、1; low0=visited0=1; / 設(shè)定鄰接表上0號(hào)頂點(diǎn)為生成樹的根 for(i=1;iadjvex; DFSArticul(G,v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先查找關(guān)節(jié)點(diǎn) if(countnextarc) p=p-nextarc; v=p-adjvex; if(visitedv=0) DFSArticul(G,v); /while /if /FindArticul,A,A,B,G,D,count=1,0,void FindArticul(ALGraph G) / 連通圖G以鄰接表作存儲(chǔ)結(jié)構(gòu)，查找并輸出G上全部關(guān)節(jié)點(diǎn)。 / 全局量count對(duì)訪問計(jì)數(shù)。 count=1; low0=v

28、isited0=1; / 設(shè)定鄰接表上0號(hào)頂點(diǎn)為生成樹的根 for(i=1;iadjvex; DFSArticul(G,v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先查找關(guān)節(jié)點(diǎn) if(countnextarc) p=p-nextarc; v=p-adjvex; if(visitedv=0) DFSArticul(G,v); /while /if /FindArticul,A,A,B,G,D,count=1,1,0,1,void FindArticul(ALGraph G) / 連通圖G以鄰接表作存儲(chǔ)結(jié)構(gòu)，查找并輸出G上全部關(guān)節(jié)點(diǎn)。 / 全局量count對(duì)訪問計(jì)數(shù)。 count=1; low0=visite

29、d0=1; / 設(shè)定鄰接表上0號(hào)頂點(diǎn)為生成樹的根 for(i=1;iadjvex; DFSArticul(G,v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先查找關(guān)節(jié)點(diǎn) if(countnextarc) p=p-nextarc; v=p-adjvex; if(visitedv=0) DFSArticul(G,v); /while /if /FindArticul,A,A,B,G,D,count=1,0,1,1,void FindArticul(ALGraph G) / 連通圖G以鄰接表作存儲(chǔ)結(jié)構(gòu)，查找并輸出G上全部關(guān)節(jié)點(diǎn)。 / 全局量count對(duì)訪問計(jì)數(shù)。 count=1; low0=visited0=1;

30、 / 設(shè)定鄰接表上0號(hào)頂點(diǎn)為生成樹的根 for(i=1;iadjvex; DFSArticul(G,v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先查找關(guān)節(jié)點(diǎn) if(countnextarc) p=p-nextarc; v=p-adjvex; if(visitedv=0) DFSArticul(G,v); /while /if /FindArticul,A,A,B,G,D,count=1,0,v,1,1,void FindArticul(ALGraph G) / 連通圖G以鄰接表作存儲(chǔ)結(jié)構(gòu)，查找并輸出G上全部關(guān)節(jié)點(diǎn)。 / 全局量count對(duì)訪問計(jì)數(shù)。 count=1; low0=visited0=1; /

31、設(shè)定鄰接表上0號(hào)頂點(diǎn)為生成樹的根 for(i=1;iadjvex; DFSArticul(G,v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先查找關(guān)節(jié)點(diǎn) if(countnextarc) p=p-nextarc; v=p-adjvex; if(visitedv=0) DFSArticul(G,v); /while /if /FindArticul,A,L,A,B,G,D,count=1,0,v,1,1,count=1,1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第co

32、unt個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B

33、,G,D,v0(1),2,1,1,1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v

34、0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B,G,D,v0(1),2,1,1,count=2, min(1)=2,1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) /

35、 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B,G,D,v0(1),2,1,1,count=2, min(1)=2,1,void DFSArticul(ALG

36、raph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(vi

37、sitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B,G,D,v0(1),2,1,1,count=2, min(1)=2,w(1),1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的

38、鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B,G,D,v0(1),2,1,1,count=2, min(1)=2,w(1),1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度

39、優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w

40、已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B,G,D,v0(1),2,1,1,count=2, min(1)=2,w(1),1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，

41、是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B,G,D,v0(1),2,1,1,count=2, min(1)=1,w(1),1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=m

42、in=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min;

43、/DFSArticul,A,L,A,B,G,D,v0(1),2,1,1,count=2, min(1)=1,w(1),1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回

44、前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B,G,D,v0(1),2,1,1,count=2, min(1)=1,w(1),1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn)

45、 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,A,B,G,D,v0(1

46、),2,1,1,count=2, min(1)=1,w(1),1,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) p

47、rintf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,M,A,B,G,D,v0(1),2,1,1,count=2, min(1)=1,w(1),2,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firsta

48、rc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,M,A,B,G,D,v0(1),2,1,1,count=2, min(2)=

49、?,w(1),v0(2),2,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.

50、verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,M,A,B,G,D,v0(1),2,1,1,count=3, min(2)=3,w(1),v0(2),3,2,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p

51、-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,M,A,B,G,D,v0(1),2,1,1,count=3, min(2)=3,w(1),v0(

52、2),3,2,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.vertices

53、v0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,M,A,B,G,D,v0(1),2,1,1,count=3, min(2)=3,w(1),v0(2),w(2),3,2,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-ne

54、xtarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 關(guān)節(jié)點(diǎn) else if(visitedwmin) min=visitedw; / w已訪問，w是v0在生成樹上的祖先 lowv0=min; /DFSArticul,A,L,M,A,B,G,D,v0(1),2,1,1,count=3, min(2)=3,w(1),v0(2),w(2),3,2,void DFSArticul(ALGraph G,int v0) / 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。 visitedv0=min=+count; / v0是第count個(gè)訪問的頂點(diǎn) for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 w=p-adjvex; / w為v0的鄰接頂點(diǎn) if(visitedw=0) / w未曾訪問，是v0的孩子 DFSArticul(G,w); / 返回前求得loww i