企业官网建设流程全解析

先简单叙述一下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已弹出，此时如A==C，则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时，若dfsA==lowA则该节点必为通过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的简单路径S，S不经过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，令C=A，M=L，则可见不变式对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’中，从而在不变式中令C=D,M=M’,M1=M1’,M2=M2’即可知不变式对C=D成立，即不变式对S上C的后继节点D仍然成立

如果(C,D)为树边或前进边，由于树边或前进边都由DFS树上的祖先指向子孙，故D仍然在以C为根的子树中，这样不难验证D和B的LCA就是C和B的LCA=M，又由不变式,M1在M2左侧，C在M1中，D在以C为根的子树中，从而D在M1中，又B在M2中，且 DFS树上从根节点到M的路径上的所有节点(包括M)都是A和B的公共祖先，故不变式对C=D仍然成立、

如果(C,D)为后退边，D当然为C在DFS树上的祖先，但路径S上根本没有A,B的任意公共祖先，因此D不是A，B的公共祖先，故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中，从而可知不变式对C=D依然成立

于是当沿路径S讨论到B时，不变式对C=B仍然成立，这是不可能的，因为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节点属于强连通分量L，A!=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树中的层数低于B，u在DFS树中的层数大于等于B，当该边为后退边时,同样有v在DFS树中的层数低于B，u在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树中的层数低于B，u在DFS树中的层数大于等于B，当该边为后退边时,同样有v在DFS树中的层数低于B，u在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,M1，M2—中的每一条路径都是其前一路径的后缀，故这样的重复讨论不可能无限进行下去,故若讨论没有中途终止，我们最后必然会由在对节点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-2，h在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,pv+1—ps均为vn-1的祖先节点，而前面已经证明vn-1的任意以A为根的子树中非A的祖先节点p的low值low[p]<dfs[p]，故low[pi]<dis[pi]i=v,v+1,—,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(i=1,2,–,v-1)的low值均满足low[pi]<=dfs[vn-1]<dfs[pi](最后一个不等式成立是因为pi在vn-1右侧),这样我们有low[pi]<dfs[pi]i=1,2,—,s

如果vn-1在ps的左侧,则dfs[vn-1]<dfs[pi]i=1,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]i=1,2,—,s

于是我们证明了low[pi]<dfs[pi]i=1,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]i=1,2,—,s，故low[pi]<dfs[pi]i=1,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]i=1,2,—,s low[vn-2]<dfs[vn-2]

总之我们有low[pi]<dfs[pi]i=1,2,—,s low[vn-2]<dfs[vn-2]

随后我们回溯至之前对vn-3的讨论，根据low[pi]<dfs[pi]i=1,2,—,s low[vn-2]<dfs[vn-2],采用和上文类似的证明过程又可证得low[p2i]<dfs[p2i]i=1,2,—,s low[vn-3]<dfs[vn-3]，这样持续向前回溯，最终我们得到

low[pn-1i]<dfs[pn-1i]i=1,2,—,s low[B]<dfs[B] 其中pn-1i i=1,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到qn=r的路径，同时存在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到qn=A的路径和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 1<=i<=n中

证明;n==1时显然成立，现设n>=2,若不然,假设G的所有顶点分别位于Ti1,Ti2,---Tim中2<=m<=n,

1<=i1<i2<---<im<=n 取G在Ti1中的任意一个顶点u和G在Tim中的任意一个顶点v,于是有向图中存在u到v中的一条路径L,显然L中所有的顶点不可能全部位于Ti1中，所以从u出发沿着L向前走,直到遇到第一个不在Ti1中的顶点y,设L上y的2前驱顶点为w，w位于Ti1中,而y位于Ti2,---,Tim中的某一棵DFS树Tiq中，由引理五，不存在Ti1中的顶点指向Tiq中的顶点的有向边,而(w,y)显然为这样一条有向边矛盾，证毕

引理七 如果对有向图在Ti 1<=i<=n的根节点上调用Tarjan算法前栈为空，则调用结束后栈仍然为空

证明：由于调用前栈为空，所以调用一开始把Ti根节点R入栈后R位于栈底,由定理一之前说明的事实，当Tarjan算法回溯到R后R仍然未出栈(当然R仍然位于栈底),在随后的出栈判断测试中由于low[R] == dfs[R]所以栈底R和栈中R以上顶点全部出栈，故调用结束后栈为空

引理八 对有向图在Ti 1<=i<=n的根节点上调用Tarjan算法前栈为空

证明：i == 1时显然成立,现设n >= 2,i >= 2

由于 i == 1时引理八成立，故由引理七 i==2时引理八成立，再由引理七，i==3时引理八成立-----以此类推，直到i==n引理八仍然成立，证毕

现在我们考察Ti 1<=i<=n

若 i> 1,则有T1,---,Ti-1,若i<n,则有Ti+1,---,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被直接忽略,不会对算法运行产生任何影响,而若i<n,由引理五如果存在连接Ti中顶点和Ti+1,--Tn中顶点的边,那这样的边只能是由Ti+1,---,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(1<=i<=n),由引理六,U的所有顶点一定位于某个Gi中(1<=i<=n),从而U为Gi的强连通子图,如果U不是Gi的强连通分量，则存在Gi的强连通子图Y以U为真子图，而Y在有向图中是强连通的，这和U是有向图的强连通分量矛盾，这就证明了U一定是Gi的强连通分量Ciq。

现在不难看出所有的Ci1,---,Cimi(1<=i<=n)的顶点两两不相交,且所有这些顶点构成了有向图的全部顶点，Ci1,---,Cimi(1<=i<=n)中任意一个Ciq是有向图的强连通分量且有向图的任意一个强连通分量U一定是某个Ciq,故所有的Ci1,---,Cimi(1<=i<=n)就是有向图的所有强连通分量，由之前证明的结论Ci1,---,Cimi(1<=i<=n)就是对有向图在Ti的根节点上调用Tarjan算法的输出结果，这就证明了Tarjan算法的正确性，证毕