图的连通性问题

1、内容概要内容概要 并查集 割点和桥 强连通分量 Tarjan Kosaraju1. 并查集 并查集是一种用来管理元素分组的数据结构 并查集使用树形结构进行存储 并查集具有两个操作: 查询元素A和元素B是否属于同一个分组 合并元素A和元素B所在的分组注意: 并查集虽然能够进行合并合并操作, 但却无法进行分割无法进行分割操作1.并查集15234a.初始化1.并查集12211b. 合并32456132456样例1样例21.并查集c.查询1324563256的根是的根是141.并查集d.代码实现1.并查集1.并查集1.并查集1.并查集e.问题13256143256141.并查集f.优化11.并查集e.

2、问题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)就称为图G的桥, 又称为割边a. 概念2.割点和桥b. 性质 一个无向连通图,

3、如果没有割点, 那么任意两点之间, 都存在点集互不相交(除了起点与终点外)的两条路径 一个无向连通图, 如果没有桥, 那么任意两点之间, 都存在边集互不相交的两条路径2.割点和桥45613251342图1图22.割点和桥问题问题: 那么我们该如何求解割点(桥)呢？ 尝试删除每个节点(边)，然后用DFS判断连通分量是否增加 深入挖掘DFS的性质，在线性时间(即O(V+E)时间)内求解所有的割点(桥)时间复杂度O(V(V+E)2.割点和桥c. DFS树ACBDFEAEBDFC(1, 12)(2, 11)(3, 10)(4, 7)(5, 6)(8, 9)图 1图 2黑色的边称为树边对图1进行DFS就

4、能得到图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及其后代不能连回f，则删除u之后，f和v不在联通；反之，如果v或者它的某一个后代存在一条反向边连回f，则删除u之后，以v根的整棵子树中的所有结点都可以利用这条反向边与f连通。如果所有子树中的结点都

5、和f连通，根据“连通”关系的传递性，整个图就是连通的。2.割点和桥f. 实现 为了方向起见，preu为u在DFS树的先序遍历的顺序，lowu为结点u及其后代所能连回的最早祖先的pre值。 当节点u存在一个子结点v，使得lowv preu，那么结点u就为割点。另外，不难发现当lowv preu时，那么 e = (u, v)即为桥(割边)。于是我们可以将定理写成：min(lowu,lowv) (min(lowu,lowv) (u,vu,v) )为树边为树边min(lowu,prev) (min(lowu,prev) (u,vu,v) )为返祖边且为返祖边且v v不是不是u u的父节点的父节点2.割

6、点和桥g. 代码(以割点为例)2.割点和桥2.割点和桥3.强连通分量a.概念 一个有向图G = (V, E)被称为强连通图，当且仅当图中任意两点间都存在一条路径。即对于图中任意两点u和v，存在u到v的路径和v到u的路径。强连通分量(Strongly Connected Component, SCC)是指一个有向图G的一个极大强连通子图。b.性质 一个有向环是最简单的强连通图。 如果一个有向图G的所有强连通分量都只有一个点，那么这个图是有向无环图，即存在拓扑序。3.强连通分量c.强连通分量分解 任意的有向图都可以分解成若干不相交的强连通分量，这就是强连通分量分解。把分解之后的强连通分量缩成一个顶

7、点，我们就得到了一个DAG(有向无环图)。1574328612,3,485,6,71574328612,3,485,6,7问题问题：我们应该如果求解有向图的各个强连通分量呢？ 我们再次借助DFS，如图，如果我们从8开始DFS，将得到只包含8的一棵DFS树; 从5出发，得到5, 6, 7; 再从2出发，得到2,3,4; 从1出发，得到1。可以发现我们“轻而易举”的就得到了SCC。细心的同学会发现，这种方式与遍历的顺序有着极大的关系。3.强连通分量Kosaraju算法第二次DFS时，先将所有边反向，然后从标号最大的顶点为起点就行DFS。这样每次DFS所遍历的顶点集合就构成了一个强连通分量。对于其他

8、剩余的未访问的顶点，不断重复以上过程。该算法只进行了两次DFS，故时间复杂度为O(|V|+|E|)我们可以通过两次DFS实现强连通分量分解。 第一次DFS时，选取任意顶点作为起点，遍历所有未访问的顶点，并在回溯前给顶点标号(post order, 后序遍历)。对于其他剩余的未访问的顶点，不断重复以上过程。完成标号后，越接近图的尾部(搜索树的叶子)，顶点的标号越小。3.强连通分量Kosaraju算法879632415121110第一遍DFS进行标号，根据搜索的顺序不同，标号结果也不同8796324151211103.强连通分量Kosaraju算法反向之后的图8,9,1012115,6,72,34

9、1根据反向后的图，确定联通分量3.强连通分量Kosaraju算法的实现3.强连通分量3.强连通分量3.强连通分量Tarjan算法 我们不难发现，Kosaraju算法是借助与遍历顺序来将不同的SCC分离到不同的DFS树中。我们可以考虑连通分量C，设其中第一个被发现的结点为x，则C中其他结点都是x的后代。如果我们在x访问完成时立刻输出C。那么我们就可以在同一颗DFS树中区分开所有的SCC了。因此这时我们将问题转化为，如何判断一个点是否为一个SCC中最先被发现的点。3.强连通分量Tarjan算法?vuw?vuw假设我们正在判断结点u是否为某个SCC第一个发现的结点。如果我们发现从结点u的子结点出发可

10、以到达结点u的祖先w，显然u，v，w在同一个SCC中，因此结点u不是该SCC中第一个被发现的结点(如图1所示)；另一方面，如果从结点v发现最多只能到结点u，那么结点u是该SCC中第一个被发现的结点(如图2所示)。图1图23.强连通分量Tarjan算法代码实现思考题 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ 曹操在长江上建立了一些根据地，根据地之间有一些桥连着。如果这些根据地之间，互相可达，那么曹操就获得战争的胜利。刘备为了防止曹操获胜，就打算去摧毁连接曹操的根据地的桥。但是诸葛亮把所有炸弹都带走了，只留下一枚给刘备。所以刘备只能炸一条桥。问刘备能够阻止曹操吗？思考题在A市中村与村之间的道路全是单行路，随着经济的发展，国家启动了“村村通”工程。工程要求任意两个村之间必须能够互相可达。给定已经存在的道路，问至少需要修多少条路，才能实现“村村通”。思考题 给定一系列网络之间的关系，若1与2连通，2与3连通那么1与3就是连通的，问能否