图论算法漫谈之连通性(零):强连通分量的Kosaraju算法

March 31, 2016 at 9:56 pm

这篇文章是图论算法漫谈系列的正篇的第一篇,不出意外地以图的连通性开题。之所以称为“零”而不是“一”,一方面是本篇介绍的算法较为简单,另一方面是接下来连通性相关的算法内容大多都和Tarjan大神相关,算法之间有较大的关联性,而本篇相对独立。 关于强连通分量的基本概念这里就不再多说了,也可以看看n年前写的东西里相关的基础概念。SSC-Tarjan算法正确性证明。 Kosaraju算法归纳起来一共就只有三步: 1. 使用DFS计算图中节点后序遍历的序号,并记录每个序号相应的节点 2. 构造图的转置图,所谓的转置,即将G中所有边的起点终点交换,变成 3. 在上不断地对未被访问到的节点中最大序号的节点进行DFS,每一次遍历能访问到的全部节点构成一个强连通分量。直至遍历完所有点。 由于算法步骤少,容易记忆和回想,Kosaraju算法是强连通分量算法入门最合适的算法,而且容易知道使用邻接表实现的复杂度是线性的,在渐近意义上已经是最优了。 Kosaraju算法的正确性也很容易验证。我们只做简单的讨论: 我们首先证明如果属于同一个强连通分量,那么它们必定在Kosaraju算法第三步构造的DFS搜索树中。为了说明这点,我们不妨设w节点首先被访问。由强连通分量的定义,容易知道在中存在从w到v的路径,所以在这棵搜索树中总会访问到v。 接着我们证明在同一棵搜索树上的任意两点都属于同一个强连通分量。我们记这棵搜索树的根为x,我们有x通过搜索树到达v的路径,说明原图中有v到达x的路径。由于算法选择的是原图中后序遍历序号中最大的点,x的序号总是比v大。这有两种可能。一种是原图的搜索树中x是v的祖先,那么先访问了v再访问了x;另一种可能是v和x在不同的子树上,v所在的子树先遍历,x所在的子树后遍历。但是后面这种情况是不可能出现的,因为v有到达x的路径,所以如果是后种情况,通过v能够访问到x,此时在搜索树中x将变成v的子孙节点,x的序号小于v,这是矛盾的。所以原图的搜索树中x是v的祖先,于是存在一条从x到v的路径。由此可知,x和v属于同一个强连通分量。w和x也是一样。由于强连通是等价关系,所以w和x也属于同一个强连通分量。 下面附上一个写得不怎么好的示例代码,提供了一个简单的测试实例,觉得应该还是能无脑看懂的,就不再多说了。 #include <stdio.h> #include <string.h> int ne; […]

图论算法漫谈开篇

March 31, 2016 at 9:12 pm

接下来的一个月时间里,我会陆陆续续对之前学习过的图论及相关的算法进行整理,总结,并以博客的形式放到这上面来,主要目的是自我学习总结。实际上的计划是更大的一个坑,不过在能填一点图论的坑之前,就不再多想了。如果一切正常,这里将会介绍图论中的一些常用的基础算法,以及可以用来理解、学习算法的一些OJ上的题目的链接。按照顺序,会先讨论有关图的连通性的内容,接着是最短路径相关的内容,然后是匹配,以及网络流,最后再讨论一些其它边边角角的内容。 这一系列的文章中不会对图论中基础的数据结构,如邻接矩阵、邻接表作过多的讨论,同时也略过最基础的图论算法bfs和dfs。文章中大部分的代码都使用邻接表来实现,而这里的邻接表实现一般被称为“前向星(forward star)”(https://github.com/zhengyidong/algo_tpl/blob/master/main/adjacency_list.cpp),网上关于这个数据结构有很多的介绍,这里不再多说(注:严格来说邻接表和前向星是两个不同的数据结构,在本系列内容的实现中,所有使用前向星的实现均可以简单地使用邻接表替代,所以以后不再区分这两个结构)。 开篇似乎就这样结束了,但是这样就显得太过苍白了,这里还是以一个很经典的问题做个收尾: (摘自Introduction to Algorithms 3rd Edition 22.1-6)大多数使用邻接矩阵的图论算法都需要的时间,但也有例外。给出一个算法,给定一个有向图的邻接矩阵表示,用的时间判断是否存在一个universal sink(可以翻译成全局汇点?),这是指一个入度为,出度为0的点。 限定了时间复杂度实际上也就限定了解法,所以这道题目的解法也并不难想。对于个点,如果点1是全局汇点,那么对于任意的i,有 ,为了验证这一点,我们必须得遍历,那么算法也就是得从遍历开始。只影响点1一个点,我们随时都可以看,所以先跳过;对于其它的,事实上,表明了点i不满足条件,此时我们一路遍历下去,如果到底都是0,那么实际上我们排除了除了点1以外的所有点,此时再回过头来,如果,那么我们只需验证所有的,有是否满足就可以了。 如果并不是一路到底的0,不妨设,那么此时由于出现了不为0的项,1自己也被排除了,所以我们已经排除了点。为了验证第k项是不是,我们直接跳到,并沿着第k行继续遍历,此时就回到算法最初的样子了,如果走到底均为0,那么只需检查点k,否则遇到第一个1,再跳到那行去。 总结起来,我们每次要么向前走,要么跳几行再向前走,走到底在检查一下,这三个操作一共需要至多,由此得到了的算法。 好了讲完了开篇也就结束了,如果你觉着后续类似这样的文章有兴趣读下去,就尽请期待正篇吧;如果你觉着写的太烂,也期待一下正篇会写的好点吧~