资源描述：
《图的连通性问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图的连通性问题内容概要并查集割点和桥强连通分量TarjanKosaraju1.并查集并查集是一种用来管理元素分组的数据结构并查集使用树形结构进行存储并查集具有两个操作:查询元素a和元素b是否属于同一个分组合并元素a和元素b所在的分组注意:并查集虽然能够进行合并操作,但却无法进行分割操作1.并查集15234a.初始化1.并查集12211b.合并32456132456样例1样例21.并查集c.查询1324563256的根是的根是141.并查集d.代码实现1.并查集1.并查集1.并查集1.并查集e.问题132561
2、43256141.并查集f.优化11.并查集e.问题2132456132456132456方式1方式21.并查集f.优化2对于问题2,我们可以记录每个树的高度合并时,如果两棵树的高度不同那么我们将高度低的树合并到高度高的树1.并查集g.优化后的代码1.并查集1.并查集2.割点和桥割点:在无向联通图G=(V,E)中,如果删除一个点u及其相关的边,会使得新的图不连通,那么点u就称为图G的一个割点桥(割边):在无向联通图G=(V,E)中,如果删除一条边e=(u,v)后,会使得新的图不连通,那么边e=(u,v)就称为
3、图G的桥,又称为割边a.概念2.割点和桥b.性质一个无向连通图,如果没有割点,那么任意两点之间,都存在点集互不相交(除了起点与终点外)的两条路径一个无向连通图,如果没有桥,那么任意两点之间,都存在边集互不相交的两条路径2.割点和桥45613251342图1图22.割点和桥问题:那么我们该如何求解割点(桥)呢？尝试删除每个节点(边)，然后用DFS判断连通分量是否增加深入挖掘DFS的性质，在线性时间(即O(V+E)时间)内求解所有的割点(桥)时间复杂度O(V(V+E))2.割点和桥c.DFS树ACBDFEAEBD
4、FC(1,12)(2,11)(3,10)(4,7)(5,6)(8,9)图1图2黑色的边称为树边对图1进行DFS就能得到图2(不唯一)，图2就称为图1的DFS树，又称为深搜树每个节点都有一对数字(x,y)x表示第一次访问该点的次序y表示第二次访问该点的次序红色的箭头称为返祖边(或者叫反向边)2.割点和桥在无向连通图G的DFS树中，非根节点u是G的割点当且仅当u存在一个子节点v，使得v及其后代都没有反向边连回u的祖先(不含u)。d.定理2.割点和桥证明：ufvufv图1图2如图，考虑u的任意子结点v。如果v及其后
5、代不能连回f，则删除u之后，f和v不在联通；反之，如果v或者它的某一个后代存在一条反向边连回f，则删除u之后，以v根的整棵子树中的所有结点都可以利用这条反向边与f连通。如果所有子树中的结点都和f连通，根据“连通”关系的传递性，整个图就是连通的。2.割点和桥f.实现为了方向起见，pre[u]为u在DFS树的先序遍历的顺序，low[u]为结点u及其后代所能连回的最早祖先的pre值。当节点u存在一个子结点v，使得low[v]≥pre[u]，那么结点u就为割点。另外，不难发现当low[v]>pre[u]时，那么e=(
6、u,v)即为桥(割边)。于是我们可以将定理写成：{min(low[u],low[v])(u,v)为树边min(low[u],pre[v])(u,v)为返祖边且v不是u的父节点2.割点和桥g.代码(以割点为例)2.割点和桥2.割点和桥3.强连通分量a.概念一个有向图G=(V,E)被称为强连通图，当且仅当图中任意两点间都存在一条路径。即对于图中任意两点u和v，存在u到v的路径和v到u的路径。强连通分量(StronglyConnectedComponent,SCC)是指一个有向图G的一个极大强连通子图。b.性质一个
7、有向环是最简单的强连通图。如果一个有向图G的所有强连通分量都只有一个点，那么这个图是有向无环图，即存在拓扑序。3.强连通分量c.强连通分量分解任意的有向图都可以分解成若干不相交的强连通分量，这就是强连通分量分解。把分解之后的强连通分量缩成一个顶点，我们就得到了一个DAG(有向无环图)。1574328612,3,485,6,71574328612,3,485,6,7问题：我们应该如果求解有向图的各个强连通分量呢？我们再次借助DFS，如图，如果我们从8开始DFS，将得到只包含{8}的一棵DFS树;从5出发，得到{
8、5,6,7};再从2出发，得到{2,3,4};从1出发，得到{1}。可以发现我们“轻而易举”的就得到了SCC。细心的同学会发现，这种方式与遍历的顺序有着极大的关系。3.强连通分量Kosaraju算法第二次DFS时，先将所有边反向，然后从标号最大的顶点为起点就行DFS。这样每次DFS所遍历的顶点集合就构成了一个强连通分量。对于其他剩余的未访问的顶点，不断重复以上过程。该算法只进行了两次DFS，故时间复
