图的连通性问题

图的连通性问题内容概要•并查集•割点和桥•强连通分量•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.问题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.性质•一个无向连通图,如果没有割点,那么任意两点之间,都存在点集互不相交(除了起点与终点外)的两条路径•一个无向连通图,如果没有桥,那么任意两点之间,都存在边集互不相交的两条路径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就能得到图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连通。如果所有子树中的结点都和f连通，根据“连通”关系的传递性，整个图就是连通的。2.割点和桥f.实现为了方向起见，pre[u]为u在DFS树的先序遍历的顺序，low[u]为结点u及其后代所能连回的最早祖先的pre值。当节点u存在一个子结点v，使得low[v]≥pre[u]，那么结点u就为割点。另外，不难发现当low[v]pre[u]时，那么e=(u,v)即为桥(割边)。于是我们可以将定理写成：其中，{min(low[u],low[v])(u,v)为树边min(low[u],pre[v])(u,v)为返祖边且v不是u的父节点𝐥𝐨𝐰[u]=2.割点和桥g.代码(以割点为例)2.割点和桥2.割点和桥3.强连通分量a.概念一个有向图G=(V,E)被称为强连通图，当且仅当图中任意两点间都存在一条路径。即对于图中任意两点u和v，存在u到v的路径和v到u的路径。强连通分量(StronglyConnectedComponent,SCC)是指一个有向图G的一个极大强连通子图。b.性质•一个有向环是最简单的强连通图。•如果一个有向图G的所有强连通分量都只有一个点，那么这个图是有向无环图，即存在拓扑序。3.强连通分量c.强连通分量分解任意的有向图都可以分解成若干不相交的强连通分量，这就是强连通分量分解。把分解之后的强连通分量缩成一个顶点，我们就得到了一个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所遍历的顶点集合就构成了一个强连通分量。对于其他剩余的未访问的顶点，不断重复以上过程。该算法只进行了两次DFS，故时间复杂度为O(|V|+|E|)我们可以通过两次DFS实现强连通分量分解。第一次DFS时，选取任意顶点作为起点，遍历所有未访问的顶点，并在回溯前给顶点标号(postorder,后序遍历)。对于其他剩余的未访问的顶点，不断重复以上过程。完成标号后，越接近图的尾部(搜索树的叶子)，顶点的标号越小。3.强连通分量Kosaraju算法879632415121110第一遍DFS进行标号，根据搜索的顺序不同，标号结果也不同8796324151211103.强连通分量Kosaraju算法反向之后的图8,9,1012115,6,72,341根据反向后的图，确定联通分量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的子结点出发可以到达结点u的祖先w，显然u，v，w在同一个SCC中，因此结点u不是该SCC中第一个被发现的结点(如图1所示)；另一方面，如果从结点v发现最多只能到结点u，那么结点u是该SCC中第一个被发现的结点(如图2所示)。图1图23.强连通分量Tarjan算法代码实现思考题某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？曹操在长江上建立了一些根据地，根据地之间有一些桥连着。如果这些根据地之间，互相可达，那么曹操就获得战争的胜利。刘备为了防止曹操获胜，就打算去摧毁连接曹操的根据地的桥。但是诸葛亮把所有炸弹都带走了，只留下一枚给刘备。所以刘备只能炸一条桥。问刘备能够阻止曹操吗？思考题在A市中村与村之间的道路全是单行路，随着经济的发展，国家启动了“村村通”工程。工程要求任意两个村之间必须能够互相可达。给定已经存在的道路，问至少需要修多少条路，才能实现“村村通”。思考题给定一系列网络之间的关系，若1与2连通，2与3连通那么1与3就是连通的，问能否找到一个节点使它故障后导致整个网络都崩溃，输出找到的点以及故障后禅僧的连通的子网络数。思考题一国有n个党派，每个党派在议会中都有2个代表，现要组建和平委员会，要从每个党派在议会的代表中选出1人，一共n人组成和平委员会。已知有一些代表之间存在仇恨，也就是说他们不能同时被选为和平委员会的成员，现要你判断满足要求的和平委员会能否创立？思考题