爱华网总结DFN-LOW算法在图论中的应用
北京大学许若辰 长沙市雅礼中学 屈运华
摘要： 在一个连通图[1]G中，有些点一旦被去除就会导致图不连通，同样的，有些边一旦被去除也会导致图G失去连通性，那么如何求出这些点和边就是一个需要被解决的问题。为此，有一种算法通过标记每个点按照遍历顺序得到的序号和查看该点通过边可以到达的点的最小序号来进行判定，解决了这个问题。此算法简单而容易理解，简称为DFN-LOW算法。
关键字：有向图 无向图强连通分量 桥 割顶
一、引言
有关图论的几个问题，如求无向图[2]的桥[3]、求无向图的割顶[4]、求有向图[5]的强连通分量[6]等，都能够被几种不同的算法解决。其中有一种算法，找到了这几个问题的共性，通过记录每个点的DFN值和LOW值，用大同小异的判定方式简洁的解决了这几个问题，思路巧妙具有针对性，把握住了问题的关键，值得借鉴。本篇论文将回顾DFN-LOW算法在图论中的应用及解决相关问题时的思路。
二、通过无向图桥的性质引出DFN-LOW算法对图进行遍历的方式
要了解图的一些性质，必然要对图进行遍历。对图进行遍历的方式主要有两种，一种是宽度优先，一种是深度优先。
它们的本质区别在于宽度优先是按照每个点到源点的距离，一层一层的整体进行遍历。对于每层点，每次将和它们相连且尚未被遍历的点放入下一层。而深度优先则是每次从当前点遍历到一个与它相连且尚未被遍历的点，并由新的被遍历的点继续往下遍历，如果没有则回到上一个点重复上述操作。由此可以看出，宽度优先遍历往往容易得到图的整体性质，深度优先遍历往往容易得到图的局部性质。
如右图，根据桥的定义可以知道，虽然去除连通图中被称作桥的边e<3,4>后会导致原图被分割成两个连通图，整个原图连通性丧失，但其本质只是导致了e的两个端点3、4以及通过3、4而连通的点对间的连通性丧失，即3无法通过除了e以外的边集到达4，这相对而言属于局部性质，所以用深度优先进行图的遍历更加容易分析桥和图的连通性之间的关系。
此外，不管是何种遍历，在遍历过程中每个点都可能会被多次访问到，但是由于每个点都只会被遍历一次，所以由图中所有点和遍历边[7]组成的图G`必然是一棵树（以下图中用三角形表示子树），其中遍历边被称作树边（以下图中用实线表示），而原图中的非遍历边被称作非树边（以下图中用虚线表示）。
三、通过求无向图的桥引入DFN-LOW算法
要判定某条边是否为桥，还需要对桥的性质进行进一步的挖掘。那么直观的进行分析，如右图。若在深度优先遍历中1号点通过了某条树边e遍历到了2号点，并接着以2号点为根遍历出了一棵子树，设u为子树中任意一点。如果边e是桥，则等价于删除了e之后1号点和2号点会不连通，即2号点无法通过u访问到1号点或者比1号点更早被遍历到的点。此时，e是否为桥便可以由2号点的性质来进行判定。
得到上述结论，便大致了解了DFN-LOW算法判定桥的思想，接下来对算法进行具体讲述。
在判定过程中，主要有两个量是判定的关键，因此定义dfn、low两个一维数组。用dfn[i]记录编号为i的点的遍历序号，即第几个被遍历到的，用low[i]记录编号为i的点在接下来的遍历中可以访问到的最小序号。那么由分析得知，对于通过树边e遍历出的点u，如果在接下来的遍历中u无法访问到序号比u更小的点，即dfn[u]等于low[u]，那么e就为桥。而根据low值的定义又可以知道u的low值可以由与u有边相连的点的low值计算出来。
根据这个思路，便可以写出整个算法的流程，下面以c++代码为例加以说明。
void bridge(long u,long e) //通过树边e遍历到了当前点u
{
long i,v;
tot++;//累加遍历序号
dfn[u]=low[u]=tot;//初始u点的dfn和low值都为遍历序号
for (i=1;i<=edge_num[u];i++)//访问每个与u相连的点v
if (edge_lable[u][i]!=e)//不能直接通过无向边e从u访问回序号小的点，否则算法失去意义
{
v=edge[u][i];
if (dfn[v]==0)//如果v尚未被遍历（设序号从1开始标记）
{
bridge(v,edge_lable[u][i]);//那么对v进行遍历并传递相应的值
if(low[v]<low[u])//v能访问到的点，u必然也能访问到，所以用low[v]更新low[u]
low[u]=low[v];
}
else
if(dfn[v]<low[u])//如果v已经被遍历，那么u只能访问到v，用dfn[v]更新low[u]
low[u]=dfn[v];
}
if (low[u]==dfn[u])//如果遍历完以u为根的子树后low[u]仍然等于dfn[u]则说明e为桥
printf("%ldn",e);//输出e
}
四、求无向图的割顶
通过求无向图的桥，DFN-LOW算法的判定思路已经展示的非常清晰。而同时根据割顶的定义可以发现，桥的两个端点必然是割顶，删除了割顶等价于删除了桥，这说明了割顶和桥在性质上是非常类似的。因此在求无向图的割顶的时候，依旧可以按照求桥时的思路进行判定，但是由于点和边的结构不同，所以一些细节也是必须要考虑的。
那么直观的分析一下割顶的特点，如右图。1号点通过树边遍历到了2号点，然后以2号点为根遍历出了一个子树，设u为子树中的任意一点。如果1号点是割顶，则等价于删除了1号点后2号点将与1号点以及比1号点更早被遍历到的点不连通，即2号点无法通过u访问到比1号点序号更小的点。
所以便可以得到结论，若v为u的一个儿子[8]且v的low值不小于u的dfn值，则u为图的割顶。
关于这个结论，有三个细节需要注意。
第一点，在结论中v的low值等于u的dfn值时结论也成立，这个很显然，看图分析即可得到。
第二点，如果u为深度优先遍历的根节点，那么只有当它有至少2个儿子v1、v2同时满足它们的low值不小于u的dfn值时结论才成立。如右图，若v2子树不存在，那么删除u仅仅只是删除了图的一个“端点”，剩下的v1仍然是连通的。所以判定根节点是否为割顶时要特殊考虑。
第三点，在第二点中，v1、v2必须是u的儿子，即必须是由u通过树边遍历出的点。如右图，若v2和u有边相连但不是u的儿子，则v2必然在以v1为根的子树中，此时u只是图“边缘”上的一个点，删除u后v1、v2仍然连通，在图的连通性方面v1、v2也是等价的，所以应不对v2进行考虑。
根据以上讨论，便可以写出整个算法的流程，下面以c++代码为例加以说明。
void cutpoint(long u, long e) //通过树边e遍历到了当前点u
{
long i,v,sum;
tot++;//累加遍历序号
dfn[u]=low[u]=tot;//初始u点的dfn和low值都为遍历序号
sum=0;//初始化满足条件的儿子个数
for (i=1;i<=edge_num[u];i++)//访问每个与u相连的点v
if (edge_lable[u][i]!=e)//不能直接通过无向边e从u访问回序号小的点，否则算法失去意义
{
v=edge[u][i];
if (dfn[u][g1]==0)//如果v尚未被遍历（设遍历序号从1开始）
{
cutpoint(v,u);//那么对v进行遍历并传递相应的值
if(low[v]<low[u])//v能访问到的点u必然也能访问到，所以用low[v]更新low[u]
low[u]=low[v];
if (low[v]>=dfn[u])//如果儿子v不能访问到比u序号更小的点
sum++;//累加满足条件的儿子个数
}
else
if(dfn[v]<low[u])//如果v已经被遍历，那么u只能访问到v，用dfn[v]更新low[u]
low[u]=dfn[v];
}
if ((sum>=2)||//如果u不为根且有满足条件的儿子或者
(sum==1)&&(u!=root))//u为根且有不少于2个满足条件的儿子则u为割顶
printf("%ldn",u);//输出u
}
五、求有向图的强连通分量
DFN-LOW算法在无向图中的应用是非常简捷的，因为无向图具有非常好的性质，即所有边都是无向边，因此有边相连的点集必然会形成一个连通块[9]。而有向图则不然，即使一个连通图在边被定向之后也未必强连通，所以对于有向图来说，桥和割顶难以成为重心，相对的，在有向图中才有定义的强连通分量则成为了有向图中的重心。本文讨论的强连通分量均默认为极大强连通分量[10]。
根据强连通分量的定义可以发现，它不同于桥或者割顶只是单个点或者边，而是点和边的集合，这就说明了求强连通分量会更加的复杂和烦琐。但是即便如此，仔细观察可以得知，它和桥或者割顶却有着极其类似的性质，如右图。1号点由树边遍历到了2号点，并以2号点为根遍历出一棵子树。如果这棵子树成为了一个强连通分量，则等价于2号点无法和1号点或者比1号点更早被遍历到的点强连通（否则该强连通分量不极大），即2号点无法通过有向边经过u访问到1号点或者比1号点序号更小的点。
这个结论和对桥进行判定时的结论简直如出一辙，因此完全可以用同样的思路来求强连通分量。
为了方便，在求强连通分量的过程中只记录每个强连通分量的点，在同一个强连通分量之中，点之间的有向边即为强连通分量的边。
所以在深度优先遍历的过程中，每次新遍历到一个点，就将该点压入栈中。当以某点u为根的子树遍历完之后，u的low值仍等于u的dfn值，则说明找到了一个新的强连通分量，此时因为强连通分量中的点均在以u为根的子树中，即应当在栈之中，所以从栈尾点一直到u这一段点就是组成当前强连通分量的点集。
关于上述算法，有一个细节需要注意。因为有向图的边有向，所以点的连通性没有对称性，如果用完全一样的方式计算low值可能会出现错误，如右图。显然1、234、567分别成为了三个强连通分量。但是深度优先遍历按照1234567的顺序遍历时，5会因为有边指向6并接着访问到了4导致5的low值等于4的dfn值，而4的dfn值是显然比5的dfn值小的，因此这样便无法在遍历完以5为根的子树后判断出567这个强连通分量，相反的会把1567判定为一个强连通分量。
细观此过程可以发现，在对567进行遍历时其实234已经被作为一个强连通分量剔除了，不再将对图的其他部分进行影响，所以在更新low值的时候不应该考虑已经被划分到某强连通分量中的点，即只考虑仍在栈中的点。
同时，考虑到如果按照1564237的顺序进行遍历，在遍历完以4为根的子树时就会判断出强连通分量234并将其从栈中删除，所以在遍历完以5为根的子树并判断出强连通分量时栈中只会剩下567，不会出现把234567判定为同一个强连通分量的情况，算法是正确的。
根据以上讨论，便可以写出整个算法的流程，下面以c++代码为例加以说明。
void group(long u) //通过有向边遍历到了当前点u
{
long i,v;
tot++;//累加遍历序号
dfn[u]=low[u]=tot;//初始u点的dfn和low值都为遍历序号
s_num++;//累加栈中点数量
stack[s_num]=u;//将u压入栈尾
in_stack[u]=true;//标记u在栈中
for (i=1;i<=edge_num[u];i++)//访问每个与u相连的点v
{
v=edge[u][i];
if (dfn[v]==0)//如果v尚未被遍历（设序号从1开始标记）
{
group(v);//那么对v进行遍历
if(low[v]<low[u])//v能访问到的点，u必然也能访问到，所以用low[v]更新low[u]
![[转载]总结DFN-LOW算法在图论中的应用 tarjan dfn和low](http://img.aihuau.com/images/30101030/30100933t01e54011286e319dc5.jpg)
low[u]=low[v];
}
else
if (dfn[v]<low[u])//如果v已经被遍历，那么u只能访问到v
if (in_stack[v])//如果v在栈中才会影响到u点，用dfn[v]更新low[u]
low[u]=dfn[v];
}
if (low[u]==dfn[u])//如果遍历完以u为根的子树后low[u]=dfn[u]则说明找到一个新的强连通分量
while (stack[s_num+1]!=u)//从栈尾到u这一段点为一个强连通分量，依次退栈
{
belong[stack[s_num]]=u;//标记该点与u属于同一个强连通分量
in_stack[stack[s_num]]=false;//取消在栈中的标记
s_num--;
}
}
六、算法实现中的注意事项及时间复杂度分析
至此DFN-LOW算法在图论中的应用基本讲述完毕，但是在整个实现过程中有几个要点仍然是需要被强调的。
1．1．在利用DFN-LOW算法解决有关无向图的问题时，原图很可能本身就是不连通的，这时候任何一个点都将成为割顶，任何一条边都会成为桥。不过更多的情况是要求对原图中的每个连通块进行单独处理。所以要考虑原图的连通性。
1．2．类似上述情况，有向图一般情况下原图就是非强连通的，所以求强连通分量时每次必须找一个未被遍历过的点并以它为根进行深度优先遍历求强连通分量，直到所有点都被遍历后才能结束。
2．1．因为无向边的无向性导致一条边可能会被访问两次，所以求无向图的桥时需要规定不能直接由原树边访问回去并更新low值，否则算法将严重出错。因为整个判定过程包括计算low值时都是假定相应的点、边已经被删除后的状态。对于有向图则不需要这个多余规定，因为在对有向图进行遍历的过程中一条边只可能被访问一次。
2．2．在求无向图的桥时可能出现重边[11]，所以上述规定不能简单的描述成“每个点不能通过边直接访问其父亲节点”，因为某个点可能通过重边访问到它的父亲节点，同时显然重边是不可能成为桥的。
3．在求有向图的强连通分量时，不能错将遍历序号用深度优先遍历中的深度代替。因为有向图中边是单向的，所以遍历序号小的点不一定比遍历序号大的点深度小，如果进行上述替换，必然会使得求强连通分量时出现错误，如右图。显然全部点构成一个强连通分量，如果按照123456的顺序深度优先遍历，3号点的深度会大于4号点的深度，所以4号点的low值不会被更新，这样算法便会将456单独判定成一个强连通分量而出错。
4．在求无向图的割顶时，对于u由非树边访问到的已经遍历过的点v，不能错用v的low值更新u的low值，因为可能v就是割顶，一旦v被删除u就无法通过v访问到low值比v的dfn值更低的点，所以只能用v的dfn值来更新u的low值。否则，如右图，3号点显然是图中的一个割顶。如果按照12345的顺序深度优先遍历且在遍历到以3号点为根的子树时先通过非树边访问了1号点，并由1号点的low值更新3号点的low值。那么在接下来在遍历中3号点的low值会通过非树边更新5号点的low值，5号点的low值又会通过树边更新4号点的low值，最后导致4号点的low值比3号点的dfn值小，判定3不是割顶，出错。
5．根据性质，第二条不会影响算法对无向图割顶的判定；第三条不会影响算法对无向图桥和割顶的判定；第四条不会影响算法对无向图桥，有向图强连通分量的判定。但是为了养成良好的习惯，减少出错概率，建议在实现算法时对上述几条均予以考虑。
DFN-LOW算法在对图进行深度优先遍历时，每个点只会被扩展一次，每条边最多也只会被访问两次，所以时间复杂度是O（N+M）的，和输入时间复杂度是同一个级别，已经达到下限。同时虽然示例程序中是用临接表的方式存储边，但是如果用链表结构来存储边，算法的空间复杂度也将降低至O（N+M）。可见DFN-LOW算法是非常优秀的。
七、结语
从整体的角度来观察整个算法，深度优先遍历时的树边就如同图的骨架，使得图中任意两点间有且只有一条树边路径[12]，而非树边则是将两点用另外一种方式相连，使得这两点和连接它们的路径上的点构成一个环，在很多问题中环上的每个点都是等价的，所以可以化成一个点，这个过程便被称作缩环[13]。缩环的必然结果便是强连通分量最后变成了一个点，剩下的边便是桥，这使得DFN-LOW算法在应用时是显得非常直观的。但只有从整体上加以理解，在局部处加以分析，才能理解算法的本质及其思路的精妙。
希望DFN-LOW算法会在今后会被不断的更新和完善，能够更广泛的被应用。
[1] 连通图：图中任意一点u可以通过无向边到达任意一点v的无向图。
[2]无向图：每条边<u,v>都为无向边的图，即既可以从u到v，也可以从v到u。
[3] 桥：删除后会导致无向图不连通的边。
[4] 割顶：删除后会导致无向图不连通的点。
[5]有向图：每条边<u,v>都为有向边的图，即只能从u到v。
[6]强连通分量：由有向图中部分边及相关点构成的子图，子图中任意一点u可以通过有向边到达任意一点v。
[7]遍历边：访问到一个未被访问过的点时所经历的边。同时这个访问过程称作遍历该点或者该点被遍历到。
[8]儿子：若u通过树边遍历到了v，则u为v的父亲，v为u的儿子。
[9] 连通块：由与某点u直接或者间接相连的点和连接他们所涉及的边组成的子图。
[10] 极大强连通分量：不成为任意一个强连通分量的子图的强连通分量。
[11] 重边：不止一条连接无向图中同样一对点u、v的边。
[12] 路径：一连串首尾依次相接的边。
[13]缩环：把一个环上的点替换成一个新的点，除了环上点之间的边外，涉及到环上点的边均与新点相连。
[g1]是v?
