dfnlow算法.docx

总结 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算法
O
要判定某条边是否为桥，还需要对桥的性质进行进一步的
挖掘。那么直观的进行分析，如右图。若在深度优先遍历
0 P\e
中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++代码为例加以说明。
//edge_num[i]表示从i号点出发的边有多少条
//edge_lable[u][i] 由 u 出去的第 i 条边的 下标
//edge[u][i]表示由u点为起点的第i条边的终点 编号。
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