Tarjan算法中的数组dfn[],即为图中各顶点的深度优先数即各顶点在DFS过程中被访问的次序low[]数组图中顶点v的low[v]应理解为dfn[v],v通过回边(DFS树中由后代节点指向祖先节点的非树边)所能到达的DFS树中v的祖先的深度优先数以及DFS树中v的后代节点通过回边所能到达的DFS树中它们的祖先的深度优先数中的最小值另外DFS中如果现在访问顶点V,接着我们访问DFS树中V的各个子女节点如果我现在试图访问与V邻接的顶点U但是发现U已经被访问过了那么对U而言有如下三种情形(1)我们正在访问U并没有访问完U在DFS树中所有子女节点并回溯到U结束对U的访问。根据图的深度优先遍历的特点由于我现在结束对DFS树中V在U之前的某个未被访问子女节点的访问(注意由于U已经被访问故U并非DFS树中V的子女节点)并回溯到V或对V在U之前的所有邻接顶点的访问都失败了(它们都已经被访问) ,然后再访问U那么毫无疑问的V在DFS树上所有的祖先节点就是当前除V以外正在被访问的所有节点但U和V显然不是同一个顶点故U就是V在DFS树上的祖先(2)之前在DFS的过程中已经回溯到U,并结束对U的访问但当我回溯到U时顶点V尚未被访问。根据深度优先遍历的访问次序此时若U是V的祖先当我回溯到U时V显然已经被访问过了矛盾。若V是U的祖先当我回溯到U时顶点V正在被访问当然访问过了同样矛盾。故UV之间不可能是祖先后代关系。于是设UV在DFS树中的最近公共祖先(LCA)为L,U在DFS树中以L的子女节点M1为根的子树T1中V在DFS树中以L的子女节点M2为根的子树T2中若T1在T2右侧则根据DFS遍历顺序回溯至U时V显然已被访问矛盾。于是T1只能在T2左侧。当然此时无向边(u,v)不可能是回边(3)之前在DFS的过程中已经回溯到U,并结束对U的访问,但当我回溯到U时顶点V已经被访问注意我们当前正在访问在DFS树中深度最深的顶点V并试图访问顶点U也就是说回溯到U的时间点必然在此之前但回溯到U时V已经被访问故回溯到U的时间点必然在V被首次访问之后这意味着当回溯到U时V一定正在被访问事实上我们正在访问以DFS树中V的某个子女节点为根的V的子树T而U就在T中于是显然的DFS树中V是U的祖先对V而言无向边(V,U)不是回边综上DFS中当首次访问一个节点V时把V入栈回溯至节点V并结束对V的访问时出栈那么如果正在访问V并即将尝试访问与V邻接的下一个顶点U而尝试访问U时U已经被访问由情形(1)U是V在DFS树中的祖先,而U正在被访问尚未回溯到U并退出由前述入栈出栈方法U一定在栈中而未出栈故U在栈中。由情形(2)U已被出栈故U不在栈中由情形(3)V是U的祖先而回溯至U的时间点必然在从顶点V尝试访问邻接顶点U之前故U必定已经出栈因而不在栈中所以尝试访问U时若U不在栈中则对V而言(V,U)不是回边,若U在栈中则U是V在DFS树上的祖先此时对V而言(V,U)可能是回边也可能不是回边注意此时V在栈顶如果栈顶之下的第一个节点就是U则(V,U)为DFS树上的一条边不是回边否则(V,U)必然是一条回边由此再根据low数组的定义总结出Tarjan算法中求low[] dfn[]数组的算法如下从无向连通图G的某一顶点出发深度优先遍历首次访问顶点V时将V的visited修改为TRUE(表示已访问),并将V入栈,为V分配dfn[V]值置low[V]dfn[V]然后依次访问V的各个邻接顶点U对每一个邻接顶点U若U尚未被访问则对U递归DFS(这一步相当于递归地求DFS树上子女节点的low值)从U退出后更新low[V]min(low[V],low[U]),若U已被访问检查U是否在栈中若U不在栈中什么都不做继续访问下一个邻接顶点否则检查栈中的V的下方第一个节点是否是U若是什么都不做继续访问下一个邻接顶点否则更新low[V] min(low[V],dfn[U])所有的邻接顶点都访问完后出栈当回溯至 遍历的开始顶点并结束对该顶点的访问时DFS结束算法同样结束
