连通图的割点、割边(桥)、块、缩点,有向图的强连通分量

连通图的割点、割边(桥)、块、缩点,有向图的强连通分量

ID:10071112

大小:152.50 KB

页数:12页

时间:2018-05-23

连通图的割点、割边(桥)、块、缩点,有向图的强连通分量_第1页
连通图的割点、割边(桥)、块、缩点,有向图的强连通分量_第2页
连通图的割点、割边(桥)、块、缩点,有向图的强连通分量_第3页
连通图的割点、割边(桥)、块、缩点,有向图的强连通分量_第4页
连通图的割点、割边(桥)、块、缩点,有向图的强连通分量_第5页
资源描述:

《连通图的割点、割边(桥)、块、缩点,有向图的强连通分量》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、连通图的割点、割边(桥)、块、缩点,有向图的强连通分量一、基本概念无向图割点:删掉它之后(删掉所有跟它相连的边),图必然会分裂成两个或两个以上的子图。块:没有割点的连通子图割边:删掉一条边后,图必然会分裂成两个或两个以上的子图,又称桥。缩点:把没有割边的连通子图缩为一个点,此时满足任意两点间都有两条路径相互可达。求块跟求缩点非常相似,很容易搞混,但本质上完全不同。割点可以存在多个块中(假如存在k个块中),最终该点与其他点形成k个块,对无割边的连通子图进行缩点后(假设为k个),新图便变为一棵k个点由k-1条割边连接成的树,倘若其中有一条边不是割边

2、,则它必可与其他割边形成一个环,而能继续进行缩点。有割点的图不一定有割边,如:              3是割点,分别与(1,2)和(4,5)形成两个无割点的块 有割边的图也不定有割点,如:                       w(1,2)为割边,有向图强连通分量:有向图中任意两点相互可达的连通子图,其实也相当于无向图中的缩点二、算法无向图借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边,用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。dfn[i]表示DFS过程中到达点i的时间,low[i]表示能通

3、过其他边回到其祖先的最早时间。low[i]=min(low[i],dfn[son[i]])设v,u之间有边w(v,u),从v->u:  如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先,此时如果拿掉v,则必定把v的祖先和v的儿子u,及它的子孙分开,于是v便是一个割点,v和它的子孙形成一个块。   如果low[u]>dfn[v]时,则说明u不仅不能到达v的祖先,连v也不能通过另外一条边直接到达,从而它们之间的边w(v,u)便是割边,求割边的时候有一个重边的问题要视情况处理,如果v,u之间有两条无向边,需要仍视为割边的话,

4、则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去,从而第二条无向重边不会被遍历而导致low[u]==dfn[v],而在另外一些问题中,比如电线连接两台设备A,B如果它们之间有两根电线,则应该视为是双连通的,因为任何一条电线出问题都不会破坏A和B之间的连通性,这个时候,我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号,在开始遍历v->u前检查它的id是否在上一次u->v时被标记,这样如果两点之间有多条边时,每次遍历都只标记其中一条,还可以通过其他边回去,形成第

5、二条新的路  求割点的时候,维护一个栈st每遍历到一个顶点v则把它放进去,对它的子孙u如果dfn[u]为0,则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v],如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出,这些点与v形成一个块,如果u的子孙x也是一个割点,这样做会不会错把它们和v,u放在一起形成一个块呢,这种情况是不会发生的,如果发现x是一个割点,则DFS到x那一步后栈早就把属于x的子孙弹出来了,而只剩下v,u的子孙,它们之间不存在割点,否则在回溯到v之前也早就提前出栈了!画一个图照着代码模拟一下可

6、以方便理解。  求割边也是一样的。有向图有向图强连通分量的算法有两个,一个是Kosaraju,另一个是Tarjan,前者需要两次DFS,代码量偏大但容易理解,后者只需要一次DFS和维护一个栈便可以,实现简单,详见这里>>强连通分量KosarajuPKTarjan2010-04-2216:23Kosaraju算法对每个不在树中的点开始DFS一次,并记录离开各点的时间,这里是离开的时间,而不是到达时的,比如有图1->22->3则1,2,3分别对应的时间是321,因为3没有出边,所以最先离开,其次是2,最后是1,DFS后,在同一棵树中的点,如果dfn

7、[v]>dfn[u]则说明点从v有可能到达u,而这棵树中的dfn[]最大的点,肯定可以到达每个点,从而在原图的逆图中,每次都选没有访问过的最大的dfn值开始DFS,如果可达点x则说明它们是强连通的voidDFS_T(intu){   inti,v;   if(used[u])return;   used[u]=1;id[u]=scc;   for(i=q[u];i!=-1;i=Tedge[i].pre)   {       v=Tedge[i].d;       if(!used[v])DFS_T(v);   }}voidDFS(intv){ 

8、  inti,u;   if(used[v])return;   used[v]=1;   for(i=p[v];i!=-1;i=edge[i].pr

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。