图的连通性问题

第8章图的连通性问题连通性初步Question：如果一个无向图是非连通图，从某个顶点出发，能否遍历到所有的顶点？Answer：对非连通图，从某个顶点出发进行遍历，只能遍历到它所在的连通子图上的所有顶点。依次从每个未访问过的顶点出发进行遍历，就可以遍历完所有的顶点，并且可以得到非连通图的连通分量个数。//从顶点n出发，DFS遍历intDFS(intn){visited[n]=1;for(inti=1;i<=nodes;i++){if(node[n][i]==1&&!visited[i])DFS(i);}return0;}//依次从每个未访问过的顶点//出发DFSsubnets=0;for(intn=1;n<=nodes;n++){

if(!visited[n]){DFS(n);subnets++;}}关节点及重连通图0123456789关节点：在一个无向连通图G中，当且仅当删去G中的顶点v及其所关联的边后，可将图分割成2个或2个以上的连通分量，则称顶点v为关节点(ArticulationPoint)，或者称为割顶。图(1)中，顶点1、3、5、7都是关节点重连通图：没有关节点的连通图。在重连通图上，任何一对顶点之间至少存在有2条路径，在删去某个顶点及其所关联的边时，也不破坏图的连通性。重连通分量如果连通图G不是重连通图，那么它可以包括几个重连通分量。一个连通图的重连通分量是该图的极大连通子图。图(1)包含了6个连通分量0123456789177判断关节点的朴素方法依次去掉每个顶点（及其所关联的边），然后用DFS去搜索整个图，可得到该图的连通分量的个数，如果是大于2，则该顶点是关节点。(这种方法复杂度很高，只适合规模较小的题目)例子：ZOJ1311//依次去掉每个顶点(及其所关联的边)，用DFS遍历剩下的子图，得连通分量个数for(intm=1;m<=nodes;m++){

intsubnets=0;//子网数目 memset(visited,0,sizeof(visited));

for(intn=1;n<=nodes;n++){

if(m==n)continue;//跳过顶点n(并不需要真正去掉顶点n)

if(!visited[n]){ DFS(m,n);//去掉顶点m，从顶点n出发DFS subnets++; } }

if(subnets>1)SPF++;}//去掉第m个顶点及其所关联的边，从第n个顶点出发进行DFSintDFS(intm,intn){ visited[n]=1;

for(inti=1;i<=nodes;i++) {

if(i==m)continue;//不考虑第m个顶点

if(node[n][i]==1&&!visited[i]) DFS(m,i); }

return0;}从顶点3出发进行深度优先搜索，得到图(b)所示的生成树，并改画成图(c)所示的树形形状。图(c)中每个顶点外侧的数字标明了进行深度优先搜索时各顶点访问的次序，称为顶点的深度优先数，可以记在数组dfn中。0123456789(a)0123456789(b)1234510987601234(c)1234510987697658求关节点的算法注意：如果u和v是2个顶点，且在深度优先搜索生成树中u是v的祖先，则有dfn[u]<dfn[v]，表明u的深度优先数小于v，u先于v被访问。01234(c)1234510987697658回边与交叉边回边：当且仅当u在生成树中是v的祖先，或者v是u的祖先，非生成树的边(u,v)才成为一条回边。如图(a)中的(1,3)、(5,7)都是回边。交叉边：除生成树的边、回边外，原图中的其他边称为交叉边。一旦生成树确定以后，那么原图中的边只可能有回边和生成树的边，交叉边实际上是不存在的。为什么？假设图(a)中存在边(1,7)(这就是所谓的交叉边)，那么顶点7(甚至其他顶点都)只能位于顶点3的左边这条子树中。0123456789(a)01234(c)1234510987697658顶点u是关节点的充要条件：如果顶点u是深度优先搜索生成树的根，则u至少有2个子女；为什么？删除u，它的子女所在的子树就断开了，你不用担心这些子树之间(在原图中)可能存在边，因为交叉边是不存在的。如果u不是生成树的根，则它至少有一个子女w，从w出发，不可能通过w、w的子孙，以及一条回边组成的路径到达u的祖先。(这时删去顶点u及其所关联的边，则以顶点w为根的子树就从搜索树中脱离了。)顶点5为什么是关节点？顶点6为什么不是关节点？0123456789(a)01234(c)1234510987697658因此，可对图G的每个顶点u定义一个low值，low[u]是从u或u的子孙出发通过回边可以到达的最低深度优先数。Low[u]=Min{dfn[u],Min{low[w]|w是u的一个子女},min{dfn[v]|(u,v)是一条回边}}因此，顶点u是关节点的充要条件是：u或者是具有两个以上子女的一个生成树的根，或者虽然不是一个根，但它有一个子女w，使得low[w]>=dfn[u]，这时w及其子孙不存在指向顶点u的祖先的回边。(这时删去顶点u及其所关联的边，则以顶点w为根的子树就从搜索树中脱离了。)顶点0123456789dfn54312678109low510low19low16low16low16第一棵子树，回退顺序：0,1,2,4,3第二棵子树，回退顺序：8,9,7,6,501234(c)1234510987697658在DFS的回退过程计算每个顶点的low值：Low[u]=Min{dfn[u],Min{low[w]|w是u的一个子女},min{dfn[v]|(u,v)是一条回边} }在回退过程计算顶点的low值0123456789(a)前进回退顶点0123456789dfn54312678109low510low19low16low16low16第一棵子树,回退顺序0,1,2,4,3第二棵子树,回退顺序8,9,7,6,5顶点u是关节点的充要条件：u是根，且有2个以上的子女u不是根，但存在一个子女w，使得low[w]>=dfn[u]01234(c)123