图的连通性问题

1、信息学院信息技术教研室VsVtV2V4V3V12484279146V1V8V9V10V7V4V3V6V5V2王桂平王桂平第第8 8章章 图的连通性问题图的连通性问题2连通性初步如果一个无向图是非连通图，从某个顶点出发，能否遍历到所有的顶点？对非连通图，从某个顶点出发进行遍历，只能遍历到它所在的连通子图上的所有顶点。依次从每个未访问过的顶点出发进行遍历，就可以遍历完所有的顶点，并且可以得到非连通图的连通分量个数。/从顶点从顶点n出发，出发，DFS遍历遍历int DFS( int n ) visitedn=1; for(int i=1; i=nodes; i+) if( nodeni=1 &

2、; !visitedi ) DFS(i); return 0;/依次从每个未访问过的顶点依次从每个未访问过的顶点/出发出发DFSsubnets=0;for( int n=1; n=nodes; n+ ) if(!visitedn) DFS(n); subnets+; 3关节点及重连通图0123456789 关节点：在一个无向连通图关节点：在一个无向连通图G中，当且仅当删去中，当且仅当删去G中的顶中的顶点点v及其所关联的边后，可将图分割成及其所关联的边后，可将图分割成2个或个或2个以上的个以上的连通分量，则称顶点连通分量，则称顶点v为关节点为关节点(Articulation Point)，或，或

3、者称为割顶。者称为割顶。图图(1)中，顶中，顶点点1、3、5、7都是关节点都是关节点 重连通图：没有关节点的连通图。在重连通图上，任何重连通图：没有关节点的连通图。在重连通图上，任何一对顶点之间至少存在有一对顶点之间至少存在有2条路径，在删去某个顶点及其条路径，在删去某个顶点及其所关联的边时，也不破坏图的连通性。所关联的边时，也不破坏图的连通性。4重连通分量 如果连通图如果连通图G不是重连通图，那么它可以包括几个重连不是重连通图，那么它可以包括几个重连通分量。一个连通图的重连通分量是该图的极大连通子通分量。一个连通图的重连通分量是该图的极大连通子图。图。 图图(1)包含了包含了6个连通分量个连

4、通分量01234567891775判断关节点的朴素方法依次去掉每个顶点（及其所关联的边），然后用依次去掉每个顶点（及其所关联的边），然后用DFS去搜索整个图，去搜索整个图，可得到该图的连通分量的个数，如果是大于可得到该图的连通分量的个数，如果是大于2，则该顶点是关节点。，则该顶点是关节点。(这种方法复杂度很高，只适合规模较小的题目这种方法复杂度很高，只适合规模较小的题目)例子：例子：ZOJ 1311/依次去掉每个顶点依次去掉每个顶点(及其所关联的边及其所关联的边)，用，用DFS遍历剩下的子图，得连通分量个数遍历剩下的子图，得连通分量个数for(int m=1; m=nodes; m+)int

5、subnets=0; /子网数目子网数目memset(visited,0,sizeof(visited);for( int n=1; n1) SPF+;6/去掉第去掉第m个顶点及其所关联的边，从第个顶点及其所关联的边，从第n个顶点出发进行个顶点出发进行DFSint DFS( int m, int n )visitedn=1;for(int i=1; i=nodes; i+)if( i=m ) continue; /不考虑第不考虑第m个顶点个顶点if( nodeni=1 & !visitedi )DFS(m,i);return 0;7 从顶点从顶点3出发进行深度优先搜索，得到图出发进行深

6、度优先搜索，得到图(b)所示的生成所示的生成树，并改画成图树，并改画成图(c)所示的树形形状。所示的树形形状。 图图(c)中每个顶点外侧的数字标明了进行深度优先搜索时中每个顶点外侧的数字标明了进行深度优先搜索时各顶点访问的次序，称为顶点的各顶点访问的次序，称为顶点的深度优先数深度优先数，可以记在，可以记在数组数组dfn中。中。0123456789(a)0123456789(b)1234510987601234(c)1234510987697658求关节点的算法8注意：如果u和v是2个顶点，且在深度优先搜索生成树中u是v的祖先，则有dfnu=dfnu01234(c)1234510987697658哪些顶点是关节点？14问题：找到关节点以后，去掉该关节点，将原来的连通