图论算法漫谈之网络流(二):Edmonds-Karp算法和Dinic算法

April 12, 2016 at 11:47 pm

本篇接着第一篇的内容,介绍如何使用增广路径的方法来求最大流。Ford-Fulkerson方法没有给出具体求增广路径的方式,如果增广路径的找法不好,甚至不能保证算法是多项式时间的。Edmonds-Karp算法和Dinic算法的出发点都是通过找“好”的增广路径,来降低时间的复杂度。其中Edmonds-Karp算法较为简单,但是算法的复杂度为,不适合实际使用;Dinic算法和Edmonds-Karp的算法非常类似,复杂度为,实际使用时还是较快的(通常在OJ等题目上都是够用的)。在实际应用中采用的大多是预流推进相关的算法,它们有更低的复杂度,我们在下一篇再介绍。 Edmonds-Karp算法 本来打算跳过这个并不实用的算法,不过考虑到它更加简单,使用它来解释一些概念会更加通俗易懂一些,所以这里还是先介绍它。 算法的思想很简单:我们每次都是在残量网络中找一条从s到t的最短路径作为增广路径,这里的最短路径是指无权图的最短路径,即仅仅取决于s到t所经过的边的数量。 算法的过程非常简单,唯一需要研究的是算法如何保证时间复杂度。我们知道无权图的最短路径可以通过BFS+队列在的时间内求得,我们只要证明我们一共只需要求次增广路径就行了。在此之前我们先证明一个引理: 引理 1: 记为残量网络中u到v的最短路径。在算法不断迭代求增广路径的过程中,源点s到任意点v的最短路径单调不减。 证明: 我们使用反证法。我们记第一次出现这样的顶点之前的残量网络为,我们找到一条最短路径作为最短路径,并取流,形成新的残量网络,导致了源点s到某些顶点的最短路径减小,我们记其中s到它的路径值最小的顶点为v,有 我们记s到v的最短路径中刚刚到达v之前的一个节点为u,即s到v的路径表示为,那么有 由于我们取的v是路径值最小的顶点,所以s到u的最短路径必然没有减少: 如果中存在边,那么 和假设不符,所以中不存在边;而中存在边,而我们只在最短路径上更新边,所以边在中s到u的最短路径上。那么 同样和原假设矛盾,所以原假设不成立,引理成立。 我们利用引理1来说明Edmonds-Karp算法的复杂度: 定理 1: Edmonds-Karp算法只需要求次增广路径。 证明: […]

图论算法漫谈之网络流(一):求最大流的Ford-Fulkerson方法

April 11, 2016 at 11:36 pm

效率上还是有些低下啊,原定于昨天完成的网络流的开篇最终还是拖到了今天。不出意外的话网络流的部分暂时打算分成四个部分,第一部分讨论网络流的基本概念,包括网络流、网络流的割、残量网络、增广路径和最大流最小割定理,最后给出Ford-Fulkerson方法;第二部分介绍常用的最大流算法,包括Edmonds-Karp算法、Dinic算法;第三部分介绍预流推进相关的最大流算法;第四部分介绍最小费用最大流相关的算法。二分图匹配的问题应该会以番外篇的形式给出。不出意外的话最近持续更新的都是这部分的内容。 本篇是第一篇,主要的目的就是引入网络流、最大流的概念,并最终证明最大流最小割定理。最大流这块比较烦的就是一开始引入了一些概念,要把这些概念理清楚得稍微费些力气。Introduction to Algorithms花了好几页来理清这些基本概念和相关的性质,实在是有点太过冗长了,而tarjan的书仅仅用了一页来说明最大流最小割定理,省去了很多tarjan大神觉得过于trivial的地方,所以本文打算在精简的基础上,给出自己认为需要指出才不至于理不清的部分,以便于日后的再复习。好了废话不再多说。 网络流与最大流 网络流可以对应于现实中水流、电流、车运货物等内容,这里还是以车运货物为例。我们有一个源点s,一个汇点t,我们要从s运送一批货物到t,s的货物是无穷尽的,我们希望每天运送到t的货物越多越好。我们雇佣了一批车子来运送这些货物,存在的一个问题是任何一个从点u到点v的有向路段(u,v)都有容量限制,表明了这一天至多只能有c(u,v)吨的货物经过这个路段,在这种情况下,我们希望知道一天能运送的最多的货物。 我们将问题抽象成网络流的模型。设是一个有向图,存在一个源点s和一个汇点t,每一条边(u,v)都有非负的容量(capacity),记为,如果图上的两点(x,y)没有边,那么定义,我们把G称为一个流网络。流网络G的一个流(flow)是定义在G中所有点对上的一个实值函数,满足以下3个性质: 1. 对于所有 (容量限制,capacity constraint) 2. 对于所有, (流守恒性,flow conservation) 3. 对于所有 (反对称性,skew symmetry) 性质1就是对容量限制的抽象,它也可以对应于水流问题中水管的大小、电流问题中导线所能承受的最大电流。 […]

图论算法漫谈之杂谈:最小生成树及相关算法(一)

April 10, 2016 at 5:55 pm

由于正好最近接触到了一些生成树相关的题目,所以稍微偏离一下原定的计划,讨论一下最小生成树(Minimum Spanning Tree,MST)以及相关的算法。本来打算汇聚到一篇里面,但是仔细整理一下发现内容还是比较多,而且寄希望于以后还能有所扩展,所以加上了个“一”,目前实际的内容一共只有两部分,之后的故事之后再说了。不出意外的话今天晚些时候还是会按照原计划介绍网络流的开篇。话不多说了。 最小生成树算法的基本思想 通常的MST问题是针对于无向图说的(有向图的MST会在下一篇中提到),指的是无向图G的一个连通、无环的子图(树)T,使得边权的和最小。举个简单的例子的话,就是几个网络节点之间要连通,那么希望总共花的网线长度最少。 MST问题是网络相关问题中比较简单的一类问题,也可能是最早被研究的问题,简单的一个原因是,解决MST问题的百分十九十以上的高效算法都是基于贪心思想的(似乎目前时间复杂度最优的算法并不是基于贪心的,但这有点远离实际应用了),MST问题能用贪心思想解决的原因和拟阵(matroid)模型有关,这部分的内容这里就不说了(Introduction to Algorithms 里有关于拟阵的一些简单的讨论,等有空再去研究这种偏数学的东西吧)。无论如何,不和拟阵打交道也可以理解MST问题及其算法。 MST问题可以使用贪心算法解决,所有基于贪心的MST算法的核心框架如下: 1. 初始时边集A是一个空集; 2. 我们不断地向A添加安全边(safe edge),所谓安全边是指如果在添加这条边之前A是某个MST边集的子集,那么添加之后A仍然存在某个MST,使得A是它的子集 3. 显然我们添加n-1条边之后算法结束,我们得到了MST 注意空集是任何边集的子集,所以一开始条件2是成立的。问题的核心当然是如何寻找安全边。我们已经说过不讨论其背后的本质,所以我们这里直接“突然”地给出定理(tarjan的书中给出的定理似乎比这个更加general一些,但是tarjan的数学太好,Introduction to Algorithms里的这个定理更加浅显易懂。以后有时间再仔细研究吧)。在这之前稍微介绍一下割(cut)的概念,这个概念在网络流中也扮演了相当重要的地位。图G的一个割是指图G顶点集V的一个划分(S, […]

图论算法漫谈之连通性(三):tarjan求双连通分量

April 7, 2016 at 1:24 pm

有了前两节的基础之后,我们回到无向图中,讨论有关双连通分量的问题。通常来讲,双连通分量分为两类,点双连通分量(也即一般意义上的biconnected component)和边双连通分量(也称为桥双连通分量)。我们先介绍点双连通分量,再介绍边双连通分量。 点双连通分量 我们定义一个无向图是点双连通的,如果这个图不存在割点;我们称图的一个极大的点双连通子图为点双连通分量。下图中,边(1,3)(1,4)(3,4)及相应顶点构成一个点双连通分量,边(2,3)(2,5)(3,5)及相应顶点构成另一个点双连通分量。 可以看到,多个点双连通分量之间可能共用一个顶点,而这个点是一个割点,这其实也是显然的,因为点双连通分量不能包含割点,所以每次遇到割点,必须把割点切开,相当于两边都带有一个割点。由于点可能带有重复,我们要使用边集(及相关的点)来表示一个点双连通分量,为此,我们定义等价关系e,表示两条边属于同一个简单圈(不带重复边不带重复点的封闭路径),容易验证等价关系e对应的每个等价类正好可以表示一个点双连通分量:首先,在同一个简单圈中不会因为移除任意一个顶点而变得不连通;两个共用一条边的简单圈实际上构成了一个更大的简单圈。 至此,类似于tarjan强连通分量算法需要求解属于同一个强连通分量的点,这里我们要求解属于同一个点双连通分量的边。和SCC类似,我们维护一个栈,并把边不断地压入栈中(需要注意的是无向图中一条边如果不在树上,那么它既可以是前向边,又可以是后向边,我们总是在它是后向边时已经把它压栈,所以注意不要把再前向边压栈从而造成重复,可以参看下面附上的例程),与此同时也计算low[]和dfn[]。一旦我们发现节点v的一个孩子满足,我们便发现了一个割点(若v是根,那么若v不是割点,那么图中没有割点,整个图是一个点双连通分量),那么显然要进行切割,我们把栈中直到(v, w)的边全部取出来,这些边便构成了一个点双连通分量。算法结束时,我们得到了所有点双连通分量。 下面我们证明算法的正确性,同样使用数学归纳法,我们以边的数量进行迭代。 如果边的数量为0,那么要么是空图,要么仅含有1个顶点,此时算法不输出任何点双连通分量。是正确的。(注意我们按照边来划分点双连通分量,如果没有边,则不构成点双连通分量)。 假设边数在小于等于e-1时均成立,我们要证明边数等于e时仍然成立。 我们先讨论最终算法得出的点双连通分量多于1个的情况,并记第一个从中剥离出来的点双连通分量为。按照算法流程,有一个对应的割点v(v不是根,否则算法只会得出一个点双连通分量),该点落于上。如果我们对图以v为根执行算法,根据算法的DFS流程,这个在原图上算法执行至v时的步骤是一样的,而根据假设,算法在边数小于e的图上执行是正确的,所以确实是一个点双连通分量。剩下来的图同样是边数小于e的图,而同样执行流程一样,所以算法必定可以正确执行。 我们接着需要讨论算法最终得出的点双连通分量只有1个的情况。如果算法出错,那么由定义可知结果图中存在割点。但这是不可能的,因为一旦发现割点,我们总是进行切割,那么必然不可能只有一个点双连通分量。 至此我们证明了算法的正确性。 下面附上一个示例程序: struct edge{ int x, y; }; […]

图论算法漫谈之连通性-番外篇(一):求解2SAT问题

April 5, 2016 at 7:02 pm

      本篇是关于图论连通性内容的一个番外篇,暂时不讨论有关连通性的其它性质和算法,而是介绍一个看起来和连通性并没有什么关系的问题,2SAT问题。尽管问题本身看似和连通性无关,但是接下来将会看到,使用SCC算法可以在线性时间内非常有效地求解2SAT问题,而且大多数SCC算法在产生强连通分量时同时提供了拓扑顺序这样的便利性,使得求解2sat问题几乎只需要调用一下SCC算法就可以了。 使用SCC算法求解2SAT问题       这里还是简单地介绍一下2SAT问题,对于SAT问题的更多内容可以参考wiki。我们首先有一个布尔变量及它们的非构成的集合,考虑一个例子,合取范式,若每一个合取范式中每一个析取项总是由两个元素(或是变量本身、或是它的非)组成,那么求解是否存在一组变量的取值,使得该合取范式为真,这样的问题即称为2适定性(2-satifiability, 2SAT)问题。从上面的例子可以看出,如果一个析取式只有一个元素,可以通过和自身进行析取转变为两个元素。       为了将问题转化为连通性问题,我们首先构造问题所对应的蕴含图,为此,我们以集合B中的每个元素(即n个变量以及它们的非)为顶点,对每个析取项,以和它等价的两条蕴含式在蕴含图中增加边。由于我们每次成对地增加边,所以建立的蕴含图有对偶性:改变所有边的方向,并改变所有顶点的标记,每一个顶点都改为,那么改变后的图和原图同构。       我们对建立的蕴含图求强连通分量,容易验证每一个强连通分量内部的点都必须有相同的真值。基于这个事实,我们证明2SAT问题有解当且仅当它的蕴含图中不存在一个变量,使得它和它的非处于同一个强连通分量。       必要性是非常好证的,这里略去,为了证明充分性,我们给出一个算法,在这种情况下给出一个可行解。我们首先求出蕴含图的强连通分量,然后进行缩点(condensation),使每个强连通分量用一个点表示,从而得到一个有向无环图(DAG)。我们首先对这些点进行拓扑排序,幸运的是,tarjan算法和Kosaraju算法生成SCC的时候已经给出了拓扑排序(Kosaraju算法按照拓扑顺序输出SCC,而tarjan算法则按照反向拓扑排序输出SCC),这个性质也比较好证明,这里也暂时略去。我们按照拓扑顺序遍历强连通分量,由于对偶性,每个强连通分量S都有对应的强连通分量,如果在S中,那么在中。遍历时,如果S未被标记,我们给S(即在S内的所有顶点)标记为TRUE,标记为FALSE,直至所有的节点被标记,从而得到一个解。 我们使用数学归纳法证明上述方式给出了2SAT问题的一个解。 初始情况下S是逆拓扑排序的第一点,所以它没有出度,将它标记为TRUE局部不会产生矛盾,同样也不会产生矛盾。 如果前面没有产生过矛盾,考虑当前强连通分量S,如果S已被标记,那么跳过即可,仍然不产生新矛盾;否则,将它标记为TRUE,按照顺序,所有指向它的节点都还没被遍历,可能导致的局部矛盾是它指向的已经被标记为FALSE的节点;但是反过来按照对偶性,所有标记为FALSE的节点向外指向的边均未被标记,所以这样的节点并不存在,所以仍然局部正确。 至此证明了该性质。 如果使用tarjan算法来求解2SAT问题,那么基本上不需要额外的步骤,这里就不附代码了。下面给出一些可以用来演练的习题,需要注意如何构建2SAT模型,以及如果将条件转化为合取范式(可以参考离散数学中一阶逻辑演算的相关内容)。 1. poj 3207 求解2SAT的特殊解 tarjan算法给出了求解2SAT问题的线性时间算法,唯一的缺陷是求法限定了解的给出方式,使得不容易应付一些简单的变形。举例来说,我们可能要求一类最优解,比如字典序解,即如果存在使取真的解,那么让它取真;否则如果能取真,则取真,以此类推。使用tarjan算法很难保证这一点。为此,这里再介绍一下一个比较简单通用,但是最坏时间复杂度为的算法。这里以求解字典序解为例,下面给出一个实际例子: 我们的策略很直观,我们取,看看是否能找到解,如果找到,就是我们要的解;如果不能,则取看看能不能找到;如果都找不到,那么2SAT问题无解。如果不对上式产生影响,那么只要有解,那么总是可行的,所以我们可以接着考虑的可能性了;当然对于例子不是这种情况,那么由于设定了,上式发生了更新: 注意由于所以1式可以直接忽略,并且由于,导致了第三项的必须为TRUE,所以我们仍然必须更新上式: 此时不存在单项,上式无法再更新。我们把设定一个变量的真值,然后根据这些单一的项不断更新,直至所有析取项都是两项的过程称为一次清除(purge)。具体实现上我们可以维护一个队列来保存这些更新过程中出现的单一项。 […]

图论算法漫谈之连通性(二):tarjan求强连通分量

April 1, 2016 at 9:53 pm

进行了简单的插曲之后,这一节我们回到有向图强连通分量的讨论中来,介绍使用tarjan算法来求有向的强连通分量,事实上这才是真正的正篇~ 很久之前写过一篇关于SCC tarjan算法正确性的文章,但仔细校验之后发现了不少错误,所以如果发现了错误,以本篇为准。 为了使行文流畅,这里还是和之前的文章一样,复习一下dfs搜索树中的一些基本的概念。我们仍然以下面的这张图为例: 下图描述了一个有向图,每一条边(包括实线边和虚线边)都对应了图中的一条边,每个节点中的数字代表了DFS访问的顺序,也即上一篇文章中提到的。这里使用不同的颜色标记了不同性质的边: 1. 图中蓝色的边是DFS搜索树上的边,称为树上边(tree edge),我们用表示一个树上边。 2. 图中红色的边是DFS搜索树上由祖先节点指向其子孙节点的边,称为前向边,容易知道移除前向边不会改变图的连通性,所以本文中我们基本可以忽略它。 3. 图中绿色的边是DFS搜索树上有子孙节点指向其祖先节点的边,称为后向边(frond),我们用表示一条后向边。 4. 图中橙色的边是DFS搜索树上由一棵子树指向另一棵子树上节点的边,称为交叉边(vine, cross link),我们用表示一条交叉边。 5. 图中黑色的边实际上是一棵搜索树上的节点到另一棵搜索树上的节点的边,称为跨树边,我们将会看到,跨树边在这里也发挥不了大的作用。 我们需要知道,不论是后向边还是交叉边,都满足。 tarjan算法也可以用简单的两个步骤来表示: […]

图论算法漫谈之连通性(一):tarjan求无向图割点

April 1, 2016 at 11:55 am

本文是图论连通性的第二篇文章,本来应该接着上一篇的思路,介绍tarjan求强连通分量,但是考虑到内容还是由浅入深比较合适,这里还是先介绍tarjan的一系列DFS算法中较为简单的一个,求割点,并由此介绍tarjan算法中常用的概念。 所谓无向图的割点(cut vertex),是指移除之后会使得的连通分量数量增加的点,对于一个连通图,就是移除之后,会导致剩下来的图变得不连通的点。这样的节点通常在网络通信模型中较为重要。 tarjan求解割点的算法步骤也非常简单: 1. 对于每个节点,使用dfs求low[v], dfn[v] 2. 每一个连通分量的dfs搜索树中,根节点是割点当且仅当有多于一个孩子;其它节点v是割点当且仅当至少有一个孩子w满足 这里还是重新介绍一下和的含义。即为节点前序遍历的序号。 指的是节点不通过其搜索树上的父节点在图中行走,直到遇到一个dfn不比它大的节点就停下来,这样子它能停下来的所有点中dfn的最小值。从递归的角度讲,low[v]取决于以下三种情况的最小值: 1. dfn[v](可以在自身处停下来) 2. dfn[u] for an edge (v, u) […]

图论算法漫谈之连通性(零):强连通分量的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,再跳到那行去。 总结起来,我们每次要么向前走,要么跳几行再向前走,走到底在检查一下,这三个操作一共需要至多,由此得到了的算法。 好了讲完了开篇也就结束了,如果你觉着后续类似这样的文章有兴趣读下去,就尽请期待正篇吧;如果你觉着写的太烂,也期待一下正篇会写的好点吧~

SCC-Tarjan算法正确性证明

July 1, 2014 at 11:44 pm

注:这篇文章由于存在不少错误而暂时(可能永久)地被废弃,相关的内容请转至图论算法漫谈之连通性(二):tarjan求强连通分量 Tarjan算法应该是求有向图强连通分量的最常用的算法,而且本身也非常的高效。网上关于Tarjan算法的介绍、模板都非常多,这里炒冷饭的目的是打算证明一下Tarjan算法的正确性,在网上找了好久,都没能找到一个我这种水平也能看得懂的证明,所以打算自己写一个。证明的主要参考来自Tarjan大神的论文。 强连通分量的概念 设G是一个有向图。如果对于G中的每个点v, w,都存在一条v到w的路径和w到v的路径(下文对于v到w的边表示为v=>w,v到w的路径表示为v==>w),那么称G是强连通的(strongly connected)。 对于G中的点v, w,如果存在v==>w和w==>v,那么称v和w是强连通的。为了引出强连通分量的概念,这里证明在G的点上的强连通关系是个等价关系。其中对称性、自反性是显然的,简单说明一下传递性。如果v和w强连通,而w和y强连通,v==>w,w==>y,v==>y,反之亦然,所以这显然是个等价关系。由于点的强连通性是一个等价关系,图G中的点就被划分成若干个等价类,而每个等价类中的点和它们在原G中的边显然构成一个强连通子图。于是图G就分解成若干个强连通子图(以及可能存在的连接这些子图的边),每一个子图就成为G的一个强连通分量(strongly connected component, SCC)。 DFS搜索树 Tarjan算法主要使用了DFS,并充分利用了DFS过程的特性。为了阐述的方便,下面以一个实际的图为例,介绍在DFS搜索中的一些概念。 上图给出了一个有向图,包括它的的所有顶点和所有边(包括所有虚线边)。 图中的编号对应了DFS遍历的顺序,在tarjan算法中,每个顶点的遍历序号通常记为DFN(v),也称为时间戳(从1开始)。 图中所有蓝色的边及相应顶点构成了一次DFS的搜索树,这些蓝色的边是树上的边,我们记树上的边(v, w)为       […]