数据结构第七章 第三节A.ppt_第1页
数据结构第七章 第三节A.ppt_第2页
数据结构第七章 第三节A.ppt_第3页
数据结构第七章 第三节A.ppt_第4页
数据结构第七章 第三节A.ppt_第5页
已阅读5页，还剩154页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、7.4.4 关节点和重连通分量,定义：无向连通图G=(V, E)中，如果删去顶点v(以及与v关联的边)，G的剩余部分就变成不连通，则顶点v称为G的一个关节点（articulation point）,不存在关节点的无向连通图称为双连通图（biconnected graph）,也称为二连通图,应用：通信、交通、军事、集成电路设计等,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）生成树的非叶子结点v, 其某棵子树的根和

2、子树中的其它结点均没有指向v的祖先的回边,A,B,G,D,关节点的条件：,A,lowv=min(visitedv, loww, visitedk),A,B,G,D,visitedv深度优先遍历时访问v的次序号,w顶点v在深度优先搜索树上的孩子结点,k顶点v在深度优先搜索树上由回边连接的祖先结点,(v, w), (v, k) E,G=(V, E),回溯函数,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以邻接表作存储结构，查找并输出G上全部关节点。 / 全局量count对访问计数。 count=1; low0=visited0=1; / 设定邻接表上0号顶点为生成树的根 for(i=1;iadjvex; DFSArticul(G,v); / 从

25、第v顶点出发深度优先查找关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc;p;p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-

26、adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 else if(visitedwmin) min=visitedw; / w已访问，w是v0在生成树上的祖先 lowv0=min; /DFSArticul,void FindArticul(ALGraph G) / 连通图G以邻接表作存储结构，查找并输出G上全部关节点。 / 全局量count对访问计数。 count=

27、1; low0=visited0=1; / 设定邻接表上0号顶点为生成树的根 for(i=1;iadjvex; DFSArticul(G,v); / 从第v顶点出发深度优先查找关节点 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以邻接表作存储结构，查找并输出G上全部关节点。 / 全局量count对访问计数。 count=1; low0=v

28、isited0=1; / 设定邻接表上0号顶点为生成树的根 for(i=1;iadjvex; DFSArticul(G,v); / 从第v顶点出发深度优先查找关节点 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以邻接表作存储结构，查找并输出G上全部关节点。 / 全局量count对访问计数。 count=1; low0=visite

29、d0=1; / 设定邻接表上0号顶点为生成树的根 for(i=1;iadjvex; DFSArticul(G,v); / 从第v顶点出发深度优先查找关节点 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以邻接表作存储结构，查找并输出G上全部关节点。 / 全局量count对访问计数。 count=1; low0=visited0=1;

30、 / 设定邻接表上0号顶点为生成树的根 for(i=1;iadjvex; DFSArticul(G,v); / 从第v顶点出发深度优先查找关节点 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以邻接表作存储结构，查找并输出G上全部关节点。 / 全局量count对访问计数。 count=1; low0=visited0=1; /

31、设定邻接表上0号顶点为生成树的根 for(i=1;iadjvex; DFSArticul(G,v); / 从第v顶点出发深度优先查找关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第co

32、unt个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v

34、0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) /

35、 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的

38、邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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个顶点出发深度

39、优先遍历图G，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，

41、是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=m

42、in=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回

44、前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点

45、 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) p

47、rintf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firsta

48、rc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.

50、verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p

51、-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.vertices

53、v0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-ne

54、xtarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww if(loww=visitedv0) printf(%d %sn,v0,G.verticesv0.data); / 关节点 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，查找并输出关节点。 visitedv0=min=+count; / v0是第count个访问的顶点 for(p=G.verticesv0.firstarc; p; p=p-nextarc) / 对v0的每个邻接顶点检查 w=p-adjvex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 DFSArticul(G,w); / 返回前求得loww i

人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论