先简单叙述一下tarjan算法的执行过程(其他诸如伪代码之类的相关细节可以自己网上搜索这里就不重复贴出了)用到两类数组dfs[]:DFS过程中给定节点的深度优先数即该节点在DFS中被访问的次序low[]从给定节点回溯时节点的low值为从节点在DFS树中的子树中的节点以及该节点通过后退边或横叉边可以回溯到的栈中DFS值最小的节点的dfs值一个数据结构栈用于确定强连通分量定义横叉边一条有向边(u,v)为横叉边当且仅当(1)u,v之间没有祖先后代关系(2)(1)满足的条件下设u,v的最近公共祖先为L,u在以L子女节点k1为根的子树T1中,v在以L子女节点k2为根的子树T2中,则T1在T2右侧前进边弧尾为祖先节点弧头为子孙节点的有向边后退边弧尾为子孙节点弧头为祖先节点的有向边树边对有向图进行深度优先搜索形成的DFS生成树上的有向边该有向边始终由父节点指向子女节点**执行过程对有向图进行深度优先搜索每抵达一个新节点A就把该节点A入栈并初始化dfs[A],然后将low[A]初始化为dfs[A],随后考察该节点A通过边可达的所有节点。若其中一个节点未访问则对其递归DFS遍历结束从该节点退出回溯至A时用该节点low值(已确定不会再改变)更新A的low值(low[A]min(low[A],low[该节点]))**若其中一个节点已访问当该节点的dfs值小于dfs[A]且该节点在栈中时用该节点dfs值更新A节点low值(low[A]min(low[A],dfs[该节点]))否则跳过什么也不做。当通过边与A相连的所有节点都考察完毕了A的low值就最终确定了,不会再变此时在从A回溯至DFS中A的前驱节点前检查low[A]是否等于dfs[A]若是不断弹栈直到把A弹出为止弹出的节点组成一个强连通分量若不是什么都不做回溯至前驱节点。伪代码Tarjan(v){stack.push(v);dfs[v]new_dfs();low[v]dfs[v];visited[v] true;for(v通过有向边弧头指向的每一个顶点n){if(!visited[n]){Tarjan(n);low[v]min{low[v],low[n]};}else{if (dfs[n]dfs[v] stack.contain(n)){low[v]min{low[v],dfs[n]};}}}if(low[v]dfs[v]){连续从栈中弹出节点直到v被弹出为止被弹出的节点组成一个强连通分量}}要注意的是算法执行过程中按DFS遍历次序入栈退栈不影响栈中各节点的DFS访问顺序和它们在栈中位置关系的逻辑关系所以任何时刻,若栈中B在栈中A之上则dfs[B]dfs[A]反之也真。还有就是从tarjan算法伪代码不难看出当从节点A回溯时必有dfs[A]low[A].并且算法中给定节点仅入栈一次出栈一次访问一次回溯过给定节点就不会再次回溯回溯至给定节点时节点的low值就已确定直至算法结束都不会改变算法中若一个节点已经入栈则只有当回溯到该节点或该节点的祖先节点时该节点才可能出栈而且在回溯到DFS树根节点时该节点之前未出栈而此时必然会出栈即对于DFS树根节点root有low[root]dfs[root]结合这几件简单事实可以证明下面七个命题学习tarjan算法的关键就是理解回溯到给定节点A时对条件dfs[A]low[A]的测试的含义以及测试成功后所执行的一系列弹栈操作以下七个命题有助于理解定理1在tarjan算法中回溯到一给定节点A时若A节点为通过DFS所到达的深度优先树中A节点所在的强连通分量中的第一个被访问的节点(根节点)则栈中A节点之上的所有节点(包括A节点)必为A节点所在强连通分量的所有节点证明事实上取栈中A之上的某节点B,若节点B不属于A所在强连通分量则B必然属于另外一个不同的强连通分量L该强连通分量有根节点B’B’不可能是从未被访问的节点否则由B’为不同的强连通分量的根节点知B尚未被访问故而不会被压入栈中矛盾。B’也不可能是已被访问压入栈中但随后又被弹出的节点若不然当压入B’后必然会回溯至B’此时检测到dfs[B’]low[B’]于是从栈中弹出B’和B’以上全部节点由B’为不同强连通分量根节点知B要么等于B’要么在B’后压栈故前述弹栈操作结束后无论如何B不会在栈中而针对B’的弹栈操作在回溯至A节点之前发生(证明:由于B在A之后压栈故dfs[B]dfs[A].B不可能尚未回溯完毕否则B正在被访问,这样B只能是A的子孙而不可能在A的右侧(否则回溯到A时B尚未访问矛盾)故此时还没有回溯到A矛盾。从而回溯到A时B已经回溯完成故B是A的子孙。显然B’不为B(否则回溯到A时B’B已经回溯完成,B已经被弹出栈矛盾)故B’只能为B的祖先,B’当然不能为A(因为B’所在强连通分量和A所在强连通分量不同)也不能为A的祖先否则存在路径B’-A-B-B’,故A,B’相互可达,B’属于A所在强连通分量,矛盾,从而B’为A的子孙B的祖先证毕),故回溯至A节点时B节点已不存在于栈中矛盾。这样B’必然已被访问且在栈中由前述证明B’不为A**B’也不可能在栈中A的位置之下这是因为前述证明指出B’为A的子孙,故B’必在A压栈后压栈于是我们证明了B’必然位于栈中A之上这样当回溯至B’时由于dfs[B’]lowB’,B’及B’之上的所有节点都会被弹出而B必然在B’后压栈这样前述弹栈操作结束后B已不在栈中此后我们才回溯至A此时B已不在栈中矛盾。这样就证明了回溯到A时栈中A之上的任一节点必属于A所在强连通分量。此外当回溯到A时之前入栈并已被弹出的任一节点C不可能属于A所在强连通分量若不然考虑C入栈后回溯到C的时刻此时由于C属于A所在强连通分量所以存在A到C的路径又由于A为A所在强连通分量的根节点且A和C并非同一节点(注意算法中tarjan算法中一个给定节点仅入栈一次出栈一次而回溯到A时C已弹出此时如AC则C在弹出后又入栈回到栈中矛盾)所以C必为A的子孙即C必在A被访问后访问(即dfs[C]dfs[A])即必在A被压栈之后压栈这样当回溯到C时A必在栈中且位于C之下且由于C属于A所在强连通分量所以存在C到A的路径。当回溯到C时可以断言必有dfs[C]!low[C],若不然C成为强连通分量M的根节点我们有A为A所在强连通分量根节点而A不等于C,C是A的子孙,M中所有节点均为C或C的子孙从而A不等于M中任意节点注意到C属于A所在强连通分量A和C相互可达,A可以和M合并组合成一个更大的强连通分支这和M为极大强连通子图矛盾所以就证明了必有dfs[C]!low[C]。于是当回溯至C时不会对C执行弹出C及栈中其上节点的弹栈操作。然后可以断言在回溯至C后和回溯至A前不可能有针对栈中C和A之间不包括A和C的节点的弹栈操作若不然取这些弹栈操作中最早发生的一次此时将会回溯至栈中C和A之间的节点D且此时C及其上节点都在栈中且应有dfs[D]low[D]故应对D执行该弹栈操作。注意到D在栈中位于A之上dfs[D]dfs[A],D比A后访问这样D必位于DFS树中节点A的子树中(D比A后访问,D不可能在A的右侧否则回溯至C后和回溯至A前D根本没有被访问故不在栈中矛盾)于是D位于DFS树中节点A的子树中此外C位于DFS树中节点D的子树中**,(证明D在栈中位于C之下C后访问dfs[D]dfs[C]若C不在D的子树中则C在D的右侧这样回溯至D时C尚未访问而不在栈中矛盾。这样D的子树中的节点C有一条指向D的祖先节点A的路径且存在A到C的路径 故A和D相互可达,从而D属于A节点所在的强连通分量, 另外显然D不为A故由引理三回溯至D时low[D]!dfs[D]这和dfs[D]low[D]矛盾这样就证明了在回溯至C后和回溯至A前不可能有针对栈中C和A之间不包括A和C的节点的弹栈操作。这样回溯至C之后回溯至A之前C不可能被弹出故回溯至A时C仍在栈中这和回溯至A时C已被弹出的假设矛盾这就证明了回溯到A时之前入栈并已被弹出的任一节点C不可能属于A所在强连通分量。另外回溯到A时从未被访问的节点也不可能属于A所在强连通分量若不然由于回溯到A时这些节点尚未被访问根据DFS搜索顺序这些节点不可能是A的子孙节点(如果是这些节点就访问过了)也不可能是A的祖先节点(如果是它们就正在被访问)这样这些节点和A没有祖先后代关系于是这些节点要么位于A左侧要么位于A右侧但显然不能位于A的左侧否则对这些节点的访问已经完成即这些节点已经回溯完毕于是这些节点只能位于A右侧而由定理三中的证明A所在的强连通的分量除A以外的所有节点一定都位于A的子树中这和这些节点位于A的右侧矛盾。这样就证明了A所在的强连通分量中所有节点都位于栈内下面可以断言栈中位于A之下的所有节点不可能属于A所在的强连通分量证明很简单若不然存在A之下的某节点E属于A所在的强连通分量注意dfs[E]dfs[A]这样E比A先访问而E属于A所在的强连通分量故A不可能是DFS中A所在的强连通分量被访问的第一个节点矛盾。这样就证明了栈中A及A之上的所有节点构成了A所在的强连通分量的全部节点证明完毕。定理2: 在tarjan算法中回溯到一给定节点A时若dfsAlowA则该节点必为通过DFS所到达的深度优先树中该节点所在的强连通分量中的第一个被访问的节点(根节点)证明使用反证法,若A节点不为通过DFS所到达的深度优先树中该节点所在的强连通分量L中的第一个被访问的节点(根节点),设L在深度优先树中的根节点为B,A!B,且A属于L由引理三回溯至A节点时必有low[A]!dfs[A],这和已知条件矛盾证毕定理3在tarjan算法中回溯到一给定节点A时若A是它所在的强连通分量M在深度优先树中被第一个访问的节点则必有dfs[A]low[A]证明首先回溯至节点A时由于A为它所在强连通分量的根节点而A所在的强连通的分量除A以外的所有节点一定都位于A的子树中(假若有节点B(A不等于B)位于A所在的强连通分量,而节点B不在A的子树中则A不是B的祖先。另外B也不是A的祖先否则B会比A先访问而A是它所在的强连通分量在深度优先树中被第一个访问的节点矛盾。故设A,B的LCA为M,A在以M的某一个子女节点L1为根的子树中,B在以M的某一个子女节点L2为根的子树中如果L1在L2的左侧注意存在从A到B的简单路径Q由引理一Q必然经过A和B的某一个公共祖先U,这样存在从U到B的路径又因为存在从A到U和从B到A的路径故存在从B到U的路径从而B和U相互可达进而U和A所在的强连通分量中任意节点相互可达从将U和A所在强连通分量合并能够得到真包含A所在强连通分量的强连通子图这和A所在强连通分量是极大强连通子图矛盾L1在L2右侧的讨论是类似的)所以A的子树中有一个属于A所在强连通分量的节点存在该节点到A的一条路径显然回溯至A时low[A]dfs[A].我们来证明回溯至A时必有dfs[A]low[A]如若不然回溯至A时有low[A]dfs[A]此时栈中A之上的所有节点C均满足low[C]dfsC且根据DFS访问顺序栈中A之上的所有节点C都已经被回溯过了(而且已经回溯过的节点不会再次被访问和回溯)回溯至A时low[A]dfs[A]这样不会针对A执行弹栈操作于是对A的回溯结束后栈中A及A之上的所有节点都会保留。另外由于根据反证法假设回溯至A时low[A]low[A],所以此时A不为DFS树根节点根节点必然在栈中A之下即栈中A之下必有节点那么栈中A之下必然存在节点D使得当回溯至D时有low[D]dfs[D],如若不然当回溯至栈底节点F(栈中DFS值最小节点)时,仍有low[F]dfs[F],从而栈中F之下存在某个节点该节点dfs值比dfs[F]还小这是不可能的,因为F为根节点DFS值最小且栈中F之下根本没有任何节点矛盾。于是我们知道对A的回溯结束后必然会回溯到栈中A之下的某节点该节点low值dfs值我们取最早回溯到的这样的节点E最早性质当回溯到E时,回溯到A时栈中A及A之上的节点仍然位于栈中(这是因为对A的回溯结束后栈中A及A之上节点仍在栈中此后由于这些节点不会被再次回溯到所以只有第一次对栈中A之下的节点执行弹栈操作时这些节点才会被弹出在此之前结束对A的回溯之后这些节点都会被保留)而回溯到E时有low[E]dfs[E]根据之前证明的定理二,E为通过DFS所到达的深度优先树中E所在的强连通分量L中的第一个被访问的节点(根节点)然后回溯到E时栈中A及A之上的节点仍然位于栈中在栈中E位于A之下这样栈中E节点之上所有节点包括了栈中A及A节点之上所有节点由于A压栈在E之后,dfs[A]dfs[E],又对E的回溯在A之后因此A必为DFS树中E的子孙节点。这里由假设回溯至A时dfs[A]!low[A]且由E的最早性质知DFS树中E至A的路径上除E和A的任意节点p均满足low[p]!dfs[p],故由引理四,A属于L,从而A和E相互可达A显然不为E,所以将E和M组合得到一个真包含M的强连通分支这和M为极大强连通子图矛盾,故必有dfs[A]low[A]证完引理一对有向图的DFS生成树中的节点A和节点B若存在节点L使得A在以L的某一个子女节点L1为根的子树中B在以L的某一个子女节点L2为根的子树中且子树L1在子树L2的左侧L是A和B的最近公共祖先则有向图中从A到B的任意一条简单路径必然经过A和B的某一个公共祖先证明假若有向图中存在一条A到B的简单路径SS不经过A和B的任意一个公共祖先(包括最近公共祖先)。则从S上的节点A出发我们尝试维持以下的不变式对路径S上的当前节点C存在节点M使得C在以M的某一个子女节点M1为根的子树中B在以M的某一个子女节点M2为根的子树中且子树M1在子树M2的左侧M是C和B的最近公共祖先,且DFS树上从根节点到M的路径上的所有节点(包括M)都是A和B的公共祖先.事实上对S上的节点A令CAML则可见不变式对A成立现假设不变式对S上的当前节点C成立,考虑S上由C指向C在S上的后继D的有向边(C, D),则(C, D)可以是前进边树边后退边横叉边。当(C, D)为横叉边时由引理二C不能在D的左边故必有D在C的左边此时设C,D的LCA(最近公共祖先)为Q显然若Q在DFS生成树中M到C的路径上(当然不包括C本身)则D和B的LCA就是M若Q在DFS生成树中DFS生成树根节点到M的路径上(不包括M),则D和B的LCA即为Q即D和B的LCA M’就在DFS生成树从根节点到M的路径上(包括M)。又由不变式知DFS树上从根节点到M的路径上的所有节点(包括M)都是A和B的公共祖先故从DFS树根节点到M’的路径上所有节点(包括M’)都是A和B的公共祖先。 同时由本轮不变式知C在B的左侧又因为D在C的左侧故D在B的左侧,从而DFS生成树中存在M’的子女节点M1’和M2’,使得子树M1’在子树M2’左侧且D在子树M1’中,B在子树M2’中从而在不变式中令CD,MM’,M1M1’,M2M2’即可知不变式对CD成立即不变式对S上C的后继节点D仍然成立如果(C,D)为树边或前进边由于树边或前进边都由DFS树上的祖先指向子孙故D仍然在以C为根的子树中这样不难验证D和B的LCA就是C和B的LCAM又由不变式,M1在M2左侧C在M1中D在以C为根的子树中从而D在M1中又B在M2中且 DFS树上从根节点到M的路径上的所有节点(包括M)都是A和B的公共祖先故不变式对CD仍然成立、如果(C,D)为后退边D当然为C在DFS树上的祖先但路径S上根本没有A,B的任意公共祖先因此D不是AB的公共祖先故D必然为M的子孙否则D在DFS树中根节点到M的路径上从而由不变式D是A和B的公共祖先矛盾。从而D在DFS树上从M到C的路径上(在M和C之间)所以由不变式D和B的LCA为M同时D就在DFS树上M1到C的路径上(不包括C)故D就在子树M1中从而可知不变式对CD依然成立于是当沿路径S讨论到B时不变式对CB仍然成立这是不可能的因为B不可能在B的左侧这就证明了从A到B的任意一条简单路径必然经过A和B的某一个公共祖先证毕引理二对有向图的DFS生成树中的节点A和节点B若存在节点L使得A在以L的某一个子女节点L1为根的子树中B在以L的某一个子女节点L2为根的子树中且子树L1在子树L2的左侧L是A和B的最近公共祖先则一定不存在从A出发指向B的有向边证明假若存在从A出发指向B的有向边(A,B)由前提条件知DFS过程中A一定比B先访问且第一次抵达A时B必然没有被访问这样在第一次抵达A后从A出发访问有向边(A,B)的另一端节点B时,B必然没有被访问(这是因为B要么是从A出发沿以A为弧尾的有向边访问的第一个节点要么不是第一个节点如果是前者那么从A出发访问B时B当然没有被访问如果是后者第一次抵达A后从A出发沿有向边访问B前访问的都是DFS树中以A的某个子女节点为根的子树这些子树都在子树L1中而B在子树L2中所以访问这些子树时根本不可能访问B)这样B在DFS中就会被访问因此B必然在以A为根的子树中故在L1中这和B在L2中矛盾这就证明了不可能存在从A出发指向B的有向边证毕引理三在Tarjan算法中若A节点为通过DFS所到达的深度优先树中A节点所在的强连通分量L中的第一个被访问的节点(根节点),且B节点属于强连通分量LA!B,则回溯到B时必有low[B]!dfs[B]证明由定理三开头的证明知L中节点除A外必定全部位于以A为根的DFS树的子树中,而A!B,A属于L故B必定在以A为根的子树中即A为B的祖先。而存在由B通向A的简单路径S,该路径S上所有节点均可属于L从而均属于以A为根的子树。我们断言S上至少有一条由前驱节点指向后继节点的有向边(u,v)该有向边要么为横叉边要么为后退边当该有向边为横叉边时,u在v的右侧(由引理二u不可能在v的左侧)并且v在DFS树中的层数低于Bu在DFS树中的层数大于等于B当该边为后退边时,同样有v在DFS树中的层数低于Bu在DFS树中的层数大于等于B。假若不是这样对S上任意一条有向边(u,v)它是前进边或者是树边或者是横叉边或后退边当它为横叉边时,u,v在DFS树中的层数要么均大于等于B要么均小于B,要么u的层数小于B,v的层数大于等于B当它为后退边时,要么u的层数低于B要么v的层数大于等于B故如果u的层数大于等于B,则必有v的层数大于等于B,而路径S的起始点B的层数大于等于B,故利用前述结论沿S向前递推可得S的终点A的层数大于等于B而A是B的祖先应有A的层数小于B矛盾这就证明了之前的断言S上至少有一条由前驱节点指向后继节点的有向边(u,v)该有向边要么为横叉边要么为后退边当该有向边为横叉边时,u在v的右侧(由引理二u不可能在v的左侧)并且v在DFS树中的层数低于Bu在DFS树中的层数大于等于B当该边为后退边时,同样有v在DFS树中的层数低于Bu在DFS树中的层数大于等于B。我们称以B为出发点的路径S上的有向边(u,v)满足性质A当且仅当(u,v)是横叉边且当u是B的子孙时v也是B的子孙现在我们考虑路径S上从B出发第一条满足断言性质的有向边(u,v),如果S上从B到u的路径上不存在不满足性质A的横叉边,注意到B到u的路径上任意一条有向边均不满足断言中规定的性质所以根据上述证明断言的过程以及B的层数大于等于B可知u的层数大于等于B又因为B到u的路径上不存在不满足性质A的横叉边所以u为B或B的子孙若(u,v)不是横叉边,即(u,v)是后退边,从而v是u的祖先假设v!A,这样v要么等于B要么和B是祖先后代关系而v的层数低于B故v必然是B的祖先。这样当在算法中第一次访问u后从u访问v时,由于v是u的祖先,所以v必然正在访问且尚未回溯到v故v必在栈中又对u的访问后于v,dfs[u]dfs[v],从而u在v压栈后压栈即栈中v在u的下方这样从u访问v时v正在被访问,v在栈中且dfs[u]dfs[v]从而算法中会执行low[u]min(dfs[v], low[u]),这样当回溯到u时必有low[u]dfs[v]dfs[B],注意B是u的祖先从而回溯到B时low[B]low[u]dfs[v]dfs[B],即low[B]dfs[v],low[B]!dfs[B]。因为v!A,且显然v属于S属于L,,这样对v而言本引理的条件得到满足,所以对v我们可以重复本证明的所有讨论,重复讨论的过程由下文所述。若(u,v)是横叉边注意B为u的祖先,A为B的祖先故v!A(否则(u,v会成为后退边)),而v属于L由于(u,v)为横叉边所以v在u的左侧,这样对v而言本引理的条件得到满足,所以对v我们可以重复本证明的所有讨论在讨论中我们令v到A的路径S为本次讨论中B到A的路径S上从v到A的路径M,在讨论中我们引出了路径M上新的点v2,v2!v,v2!A,v2属于M属于本讨论中路径S属于L,于是v2满足本引理的条件故再对v2重复本证明中的讨论,在讨论中令v2到A的路径S为上一次讨论中v到A的路径M上从v2到A的路径M2在对v2的讨论中我们引出了路径上新的点v3—— 按照这一步骤反复讨论下去由于本次讨论中路径S长度有限,而S,M,M2.M3—的长度逐步递减M,M1M2—中的每一条路径都是其前一路径的后缀故这样的重复讨论不可能无限进行下去,故若讨论没有中途终止我们最后必然会由在对节点vn-1的讨论中引出了路径Mn-1上新的点vn,Mn-1上以vn为弧头的有向边为(h,vn),h为弧尾,有向边(h,vn)是Mn-1上从vn-1出发的第一条也是最后一条满足红字部分断言性质的有向边断言中B为vn-1,S为Mn-1,vn恰好为节点A,即vn是路径Mn-1终点,同时Mn-1上vn-1到h的路径上的所有有向边中不存在任何不满足性质A的横叉边并且有向边(h,vn)(h,A)显然为后退边不为横叉边(Mn-1是简单路径且为本次讨论中路径S的后缀,故h!A,h属于L属于以A为根的子树从而h为A的后代即(h,A)(h,vn为后退边))。所以我们对有向边(h,vn)重复上文**红字斜体部分**的证明,即可推出算法中回溯到vn-1时low[vn-1]low[h]dfs[vn]dfs[A],即low[vn-1]dfs[A]dfs[vn-1],从而可知vn-1的任意以A为根的子树中非A的祖先节点p的low值low[p]low[vn-1]dfs[A]dfs[p]这说明不仅当回溯到vn-1时栈中的vn-1不会出栈且回溯到vn-1的在以A为根的子树中的祖先节点(不包括A)时都不会执行出栈操作从而栈中vn-1不会出栈_故DFS过程中回溯至vn-1后回溯到A之前vn-1都在栈中不会出栈。结论一_如果S上从B到u的路径上存在不满足性质A的横叉边,设这些横叉边中第一条为(q, r),则S上B到q的路径上不存在不满足性质A的横叉边且任意一条有向边均不满足红字部分断言规定的性质,所以由**红字斜体部分开头的内容**知必有q为B或B的子孙,注意B为q或q的祖先,A为B的祖先故r!A(否则(q,r)会成为后退边),而r属于L,这样对r而言本引理的条件得到满足,所以对r我们可以重复本证明的所有讨论,重复讨论的过程如上文所述下面我们沿着递推链反向回溯,如果在上述反复讨论中我们最终抵达了节点vn-1并对vn-1展开讨论,对vn-1的讨论结束后我们回溯至之前对vn-2的讨论,在对vn-2的讨论中我们引出了路径Mn-2上的有向边(h, vn-1),这里若设(h,vn-1)为横叉边。如果(h,vn-1)为满足红字部分断言性质的横叉边,则vn-1在DFS树中的层数低于vn-2h在DFS树中的层数大于等于vn-2,且Mn-2上从vn-2到h的路径上所有有向边中没有任何不满足性质A的横叉边,这些有向边均不满足红字部分断言的性质。注意low[vn-1]dfs[vn]dfs[A],h在vn-1的右边这样DFS中当我从h访问vn-1时,注意h!A,h属于路径S属于L,h为A的子孙,于是访问h时尚未回溯到A且在回溯至vn-1之后由结论一,vn-1仍在栈中而且由dfs[h]dfs[vn-1]知栈中vn-1在h之下,这样从h访问vn-1时由于vn-1已经被访问故算法中会执行low[h]min(low[h], dfs[vn-1]),于是必有low[h]dfs[vn-1].由于Mn-2上vn-2到h的路径上的有向边中没有任何不满足性质A的横叉边且这些有向边均不满足红字部分断言的性质再由vn-2在DFS树中的层数大于等于vn-2以及斜体红字部分开头的叙述知必有h为vn-2或vn-2的子孙而low[h]dfs[vn-1],故low[vn-2]low[h]dfs[vn-1],又vn-1在h的左侧vn-1不为vn-2的子孙(这是因为vn-1在DFS树中测层数低于vn-2),故vn-1在vn-2的左侧因此dfs[vn-1]dfs[vn-2],故low[vn-2]dfs[vn-2]然后设DFS树中节点A至节点vn-2的路径上除A和vn-2以外的所有节点从下至上为p1,p2—ps.由于vn-1在vn-2的左侧所以vn-1要么是p1,p2—ps中某一个节点pv的子孙节点(此时vn-1所在的以pv的子女节点为根子树一定在vn-2的以pv的子女节点pv-1为根的子树的左侧),要么在节点ps的左侧,vn-1不可能恰为p1,p2—ps中的某一个节点否则由于h为hn-2的子孙,(h, vn-1)将成为一条返祖边这和其为横叉边矛盾.如果vn-1是pv的子孙节点,则pv,pv1—ps均为vn-1的祖先节点而前面已经证明vn-1的任意以A为根的子树中非A的祖先节点p的low值low[p]dfs[p]故low[pi]dis[pi]iv,v1,—,s.此外,pv-1,pv-2,—p1均在vn-1的右侧而且由结论一回溯至vn-1后回溯至pv之前vn-1都在栈中不会出栈这意味着在pv的子树第一次访问vn-2后从vn-2子孙节点h访问vn-1时vn-1仍在栈中,显然dfs[h]dfs[vn-2]dfs[vn-1]且栈中vn-1在h之下vn-1已被访问过于是算法中会执行low[h]min{low[h],dfs[vn-1]},从而low[h]dfs[vn-1],故h的祖先节点pi(i1,2,–,v-1)的low值均满足low[pi]dfs[vn-1]dfs[pi](最后一个不等式成立是因为pi在vn-1右侧),这样我们有low[pi]dfs[pi]i1,2,—,s如果vn-1在ps的左侧,则dfs[vn-1]dfs[pi]i1,2,—,s,同样由结论一,当从h访问vn-1时vn-1仍在栈中,dfs[h]dfs[vn-1]且栈中vn-1在h之下,vn-1已被访问过,故算法中会执行low[h]min{low[h],dfs[vn-1]}从而low[h]dfs[vn-1]故h的祖先节点p1,p2,—,ps满足low[pi]low[h]dfs[vn-1]dfs[pi]i1,2,—,s于是我们证明了low[pi]dfs[pi]i1,2,—,s low[vn-2]dfs[vn-2]如果(h,vn-1)不为满足红字部分断言性质的横叉边,则(h,vn-1)必然为不满足性质A的横叉边且Mn-2上从vn-2到h的路径上所有有向边中没有任何不满足性质A的横叉边,这些有向边均不满足红字部分断言的性质。使用和上文类似的推理知low[vn-2]low[h]dfs[vn-1],h为vn-2子孙.vn-1在h左侧,(h,vn-1)不满足性质A即h是vn-2子孙但vn-1不是从而vn-1在vn-2左侧,因此dfs[vn-1]dfs[vn-2],故low[vn-2]dfs[vn-2].然后然后设DFS树中节点A至节点vn-2的路径上除A和vn-2以外的所有节点从下至上为p1,p2—ps仿上文证明同样可证low[pi]low[h]dfs[vn-1]dfs[pi]i1,2,—,s故low[pi]dfs[pi]i1,2,—,s low[vn-2]dfs[vn-2]如果(h,vn-1)为后退边, 则Mn-2上从vn-2到h的路径上不存在不满足性质A的横叉边,且vn-2到h的路径上任意一条有向边均不满足断言中规定的性质,但(h,vn-1)满足红字部分断言性质。注意我们在红字斜体部分已经证明了vn-1是vn-2的祖先,low[vn-2]!dfs[vn-2],low[vn-2]dfs[vn-1],另外已经证明了vn-1的任意以A为根的子树中非A的祖先节点p的low值low[p]dfs[p]以及low[vn-1]dfs[vn-1].于是对任意vn-2的祖先节点vn-1的子孙节点p有low[p]low[vn-2]dfs[vn-1]dfs[p],设DFS树中节点A至节点vn-2的路径上除A和vn-2以外的所有节点从下至上为p1,p2—ps我们就得到low[pi]dfs[pi]i1,2,—,s low[vn-2]dfs[vn-2]总之我们有low[pi]dfs[pi]i1,2,—,s low[vn-2]dfs[vn-2]随后我们回溯至之前对vn-3的讨论根据low[pi]dfs[pi]i1,2,—,s low[vn-2]dfs[vn-2],采用和上文类似的证明过程又可证得low[p2i]dfs[p2i]i1,2,—,s low[vn-3]dfs[vn-3]这样持续向前回溯最终我们得到low[pn-1i]dfs[pn-1i]i1,2,—,s low[B]dfs[B] 其中pn-1i i1,2,—,s为DFS树中节点A至节点B的路径上除A和B以外的所有节点,故当回溯至B时必然有low[B]!dfs[B]证完引理四:在Tarjan算法中,如果若A节点为通过DFS所到达的深度优先树中A节点所在的强连通分量L中的第一个被访问的节点(根节点),且B节点是A的子孙节点(B!A),DFS树中从A到B的路径上任意节点p(不包括A)均满足low[p]!dfs[p],则B节点必属于L证明只需证明存在B到A的一条路径即可。由于low[B]dfs[B],根据low的定义,存在B或B的子孙节点中一个节点p1,满足存在从p1出发的一条有向边(p1, q1),使得(p1,q1)为横叉边,dfs[q1]low[B]dfs[B],q1在B的左侧(因为dfs[q1]dfs[B]故q1要么为B的祖先要么在B的左侧,若q1为B的祖先,则(p1,q1)为后退边矛盾故q1在B的左侧)low[q1]!dfsq1 或者使得(p1,q1)为后退边,dfs[q1]low[B]dfs[B],q1为B的祖先节点,这里先假设low[q1]!dfs[q1],于是我们得到路径B-S1-p1-q1,其中S1为由以B为根的子树中树边构成的路径下面考察节点q1,由于low[q1]dfs[q1],根据low的定义仿照上述讨论可知存在q1或q1的子孙节点中一个节点p2,满足存在从p2出发的一条有向边(p2, q2),使得(p2,q2)为横叉边,dfs[q2]low[q1]dfs[q1],q2在q1的左侧,low[q2]!dfs[q2]或者使得(p2,q2)为后退边,dfs[q2]low[q1]dfs[q1],q2为q1的祖先节点,这里假设low[q2]!dfs[q2],于是我们得到路径B-S1-p1-q1-S2-p2-q2,其中S2为由以q1为根的子树中树边构成的路径按照这一步骤反复讨论下去得到路径B-S2-p1-q1-S2-p2-q2-S3-p3-q3—— 其中dfs[B]dfs[q1]dfs[q2]dfs[q3]—— 注意DFS树中各节点的深度优先数dfs存在最小值(根节点的dfs值)故前述步骤不可能无限进行下去所以最终必然会到达节点qn-1,low[qn-1]dfs[qn-1],在考察qn-1时发现存在qn-1或qn-1的子孙节点中一个节点pn,满足存在从pn出发的一条有向边(pn, qn),使得(pn,qn)为后退边(pn,qn不可能为横叉边否则按照上文讨论最后必有low[qn]!dfs[qn]这样讨论还会从qn继续进行下去,这和设讨论终止于qn-1矛盾),dfs[qn]low[qn-1]dfs[qn-1],qn为qn-1的祖先节点,同时我们有low[qn]dfsqn,于是最终有路径B-S2-p1-q1-S2-p2-q2-S3-p3-q3—— -qn-1-Sn-pn-qn,其中Sn为由以qn-1为根的子树中树边构成的路径,dfs[B]dfs[q1]dfs[q2]dfs[q3]—dfs[qn-1]dfs[qn]现在考察qn,设以qn为根的子树为C,由于qn为qn-1的祖先故qn-1在子树C中若(pn-1,qn-1)为后退边则由上文讨论知,qn-1为qn-2的祖先节点故qn-2在子树C中若(pn-1,qn-1)为横叉边则由上文讨论知qn-1在qn-2的左侧,若qn-2不在子树C中,则qn-2在qn的右侧从而为qn-2或为qn-2的子孙节点的pn-1也在qn的右侧,这样当从pn-1访问qn-1时qn-1之前已经在回溯到qn时被弹出栈(qn-1在子树C中且low[qn]dfs[qn])故不在栈中,而这是不可能的因为根据对qn-2的讨论和low的定义,当在dfs过程中从pn-1访问qn-1时,qn-1必然在栈中且在pn-1之下矛盾.故qn-2一定在子树C中按照以上步骤循路径B-S2-p1-q1-S2-p2-q2-S3-p3-q3—— -qn-1-Sn-pn-qn不断向前回溯可得qn-1,qn-2,—,q1,B均在子树C中结论一现在注意dfs[qn]dfs[B],所以qn要么为B的祖先节点要么在以B的某个祖先节点D的子女E为根的子树T中,这里E一定在为D的子女同时为B或B的祖先的节点F的左侧。如果是后者,由结论一知B在以B的某个祖先节点D的子女E为根的子树T中,E一定在为D的子女同时为B或B的祖先的节点F的左侧这当然是不可能的如果是前者,由low[qn]dfs[qn]以及**DFS树中从A到B的路径上任意节点p(不包括A,B)均满足low[p]!dfs[p]知qn不可能为DFS树中从A到B的路径上任意节点(不包括A,B)此外qn也不可能是A节点的任意祖先节点r,否则注意到存在B到qnr的路径同时存在r到A以及A到B的路径故r和A相互可达。又low[qn]low[r]dfs[qn]dfs[r],所以由定理二,r必为通过DFS所到达的深度优先树中该节点所在的强连通分量L2中的第一个被访问的节点(根节点),而r和A相互可达,从而强连通分量L完全真包含于强连通分量L2这和L为极大强连通子图矛盾。综上qn只能为A节点本身**因此我们有low[A]low[qn]dfs[qn]dfs[A],且由于存在从B到qnA的路径和A到B的路径所以A和B相互可达从而B属于L证毕定理四:Tarjan算法的正确性Tarjan算法运行结束时每次从栈中弹出的所有节点的集合的集合构成了有向图的所有强连通分量证明首先由于每个节点仅访问一次入栈一次出栈一次故每次出栈的节点都是不同的节点即每次出栈时弹出的所有节点两两不同且任意两次出栈弹出的节点集合交集为空其次算法中当回溯至v并检测到low[v]dfs[v]时由定理二v是dfs树中v所在的强连通分量L被第一个访问的节点(根节点)再由定理一此时栈中v及v之上的所有节点构成L的所有节点它们会被依次出栈这样出栈的所有节点即为L构成有向图的一个强连通分量再者对于有向图的任意一个强连通分量L,设它在DFS树中的根节点为R(根据深度优先搜索的白色路径定理,R必定存在)由定理三Tarjan算法中回溯至R时有low[R]dfs[R],再由定理一,此时栈中R及R之上的所有节点构成L的所有节点它们会被依次出栈出栈的所有节点即为该强连通分量L最后有向图中任意节点都必然会出栈从而会归入某次出栈时出栈的节点组成的集合中综上定理四证完PS:博主水平有限如果以上证明存在疏漏或错误恳请指正谢谢.Tarjan算法简单易实现但是原理还是比较复杂的不容易理解不得不说Tarjan太强啦PS:之前完成过错误的证明写的时候信马由缰过于匆忙写完又没有仔细检查结果隔了一段时间再细细检查发现漏洞百出连循环论证这种低级错误都出现无奈只能全部推翻重来经过仔细思考才得到以上证明该证明不全面原因是 该证明假定从有向图的一个顶点出发只需调用一次Tarjan算法就可以发现有向图的所有顶点从而得到有向图的一个深度优先生成树而并非所有有向图都具有该特性。事实上我们只能假定对有向图调用Tarjan算法能够得到有向图的深度优先森林T我们把T中各DFS树按发现顺序从前到后排列为T1,T2,T3,---,Tn先来证明若干引理引理五 对Ti,Tj 1 i j n,如果有向图中存在连接Ti中顶点和Tj中顶点的有向边则有向图中只存在从Tj中的顶点指向Ti中顶点的有向边而不存在Ti中顶点指向Tj中顶点的有向边证明只需证不存在Ti中顶点指向Tj中顶点的有向边若存在Ti中顶点指向Tj中顶点的有向边设该有向边为(u,v),若我们考虑Ti中的根R在Tarjan算法DFS中被发现的时刻显然此时有向图存在从R到u全部由白色节点组成的路径实际上就是Ti中R到u路径L,注意此时Tj尚未被发现,故v是白色的这样L加上(u,v)恰好是R被发现的时刻R到v全部由白色节点组成的路径从而根据白色路径定理v为R在DFS树中的后代这和v在Tj而不在Ti中从而不是R的后代矛盾证毕.引理六 有向图的任意强连通子图G的所有顶点位于且仅位于T1,---,Tn中的一棵DFS树Ti 1in中证明;n1时显然成立现设n2,若不然,假设G的所有顶点分别位于Ti1,Ti2,---Tim中2mn,1i1i2---imn 取G在Ti1中的任意一个顶点u和G在Tim中的任意一个顶点v,于是有向图中存在u到v中的一条路径L,显然L中所有的顶点不可能全部位于Ti1中所以从u出发沿着L向前走,直到遇到第一个不在Ti1中的顶点y,设L上y的2前驱顶点为ww位于Ti1中,而y位于Ti2,---,Tim中的某一棵DFS树Tiq中由引理五不存在Ti1中的顶点指向Tiq中的顶点的有向边,而(w,y)显然为这样一条有向边矛盾证毕引理七 如果对有向图在Ti 1in的根节点上调用Tarjan算法前栈为空则调用结束后栈仍然为空证明由于调用前栈为空所以调用一开始把Ti根节点R入栈后R位于栈底,由定理一之前说明的事实当Tarjan算法回溯到R后R仍然未出栈(当然R仍然位于栈底),在随后的出栈判断测试中由于low[R] dfs[R]所以栈底R和栈中R以上顶点全部出栈故调用结束后栈为空引理八 对有向图在Ti 1in的根节点上调用Tarjan算法前栈为空证明i 1时显然成立,现设n 2,i 2由于 i 1时引理八成立故由引理七 i2时引理八成立再由引理七i3时引理八成立-----以此类推直到in引理八仍然成立证毕现在我们考察Ti 1in若 i 1,则有T1,---,Ti-1,若in,则有Ti1,---,Tn,根据引理八对有向图在Ti的根节点上调用Tarjan算法前栈为空故若i 1此时栈中不包含T1,---,Ti-1中任意顶点而对有向图在Ti的根节点上调用算法过程中只会入栈Ti中的顶点故过程中栈中仍然不包含T1,---,Ti-1中任意顶点由引理五可能存在由Ti中顶点指向T1,--Ti-1中顶点的边,设这些边中任意一个为(u,v)在对有向图在Ti的根节点上调用算法过程中由u检查v时显然v已被访问且dfs[v]dfs[u],且由上文所述v不在栈中这样算法中v被直接忽略,不会对算法运行产生任何影响,而若in,由引理五如果存在连接Ti中顶点和Ti1,--Tn中顶点的边,那这样的边只能是由Ti1,---,Tn中顶点指向Ti中顶点的有向边,这样的边在对有向图在Ti的根节点上调用算法过程中根本不会被检查故不会对算法的运行产生任何影响因此我们得到以下结论对有向图在Ti的根节点上调用Tarjan算法的输出结果和对Ti中所有顶点在有向图中的导出子图Gi在Ti的根节点上调用Tarjan算法的输出结果完全一致设对Ti中所有顶点在有向图中的导出子图Gi在Ti的根节点上调用Tarjan算法的输出的强连通分量为Ci1,---,Cimi,由之前不完整的证明(即引理五之前的证明过程)这些强连通分量构成了Gi的所有强连通分量.我们断言其中任意一个Ciq必然是有向图的强连通分量,如若不然首先Ciq在有向图中一定是强连通的而又存在有向图的强连通子图N以Ciq为真子图,由引理六N的所有顶点全部位于Ti中从而N必为Gi的一个强连通子图,这和Ciq是Gi的一个强连通分量矛盾故Ciq必然是有向图的强连通分量另外有向图的任意一个强连通分量U一定是某个Gi的强连通分量Ciq(1in),由引理六,U的所有顶点一定位于某个Gi中(1in),从而U为Gi的强连通子图,如果U不是Gi的强连通分量则存在Gi的强连通子图Y以U为真子图而Y在有向图中是强连通的这和U是有向图的强连通分量矛盾这就证明了U一定是Gi的强连通分量Ciq。现在不难看出所有的Ci1,---,Cimi(1in)的顶点两两不相交,且所有这些顶点构成了有向图的全部顶点Ci1,---,Cimi(1in)中任意一个Ciq是有向图的强连通分量且有向图的任意一个强连通分量U一定是某个Ciq,故所有的Ci1,---,Cimi(1in)就是有向图的所有强连通分量由之前证明的结论Ci1,---,Cimi(1in)就是对有向图在Ti的根节点上调用Tarjan算法的输出结果这就证明了Tarjan算法的正确性证毕
