dfnlow算法.doc

总结DFN-LOW算法在图论中的应用 北京大学? 许若辰?? 长沙市雅礼中学 屈运华 摘要： 在一个连通图[1]G中，有些点一旦被去除就会导致图不连通，同样的，有些边一旦被去除也会导致图G失去连通性，那么如何求出这些点和边就是一个需要被解决的问题。为此，有一种算法通过标记每个点按照遍历顺序得到的序号和查看该点通过边可以到达的点的最小序号来进行判定，解决了这个问题。此算法简单而容易理解，简称为DFN-LOW算法。 ?? 关键字：有向图? 无向图? 强连通分量? 桥? 割顶 ?? 一、?????? 引言 有关图论的几个问题，如求无向图[2]的桥[3]、求无向图的割顶[4]、求有向图[5]的强连通分量[6]等，都能够被几种不同的算法解决。其中有一种算法，找到了这几个问题的共性，通过记录每个点的DFN值和LOW值，用大同小异的判定方式简洁的解决了这几个问题，思路巧妙具有针对性，把握住了问题的关键，值得借鉴。本篇论文将回顾DFN-LOW算法在图论中的应用及解决相关问题时的思路。 ? 二、?????? 通过无向图桥的性质引出DFN-LOW算法对图进行遍历的方式 要了解图的一些性质，必然要对图进行遍历。对图进行遍历的方式主要有两种，一种是宽度优先，一种是深度优先。 它们的本质区别在于宽度优先是按照每个点到源点的距离，一层一层的整体进行遍历。对于每层点，每次将和它们相连且尚未被遍历的点放入下一层。而深度优先则是每次从当前点遍历到一个与它相连且尚未被遍历的点，并由新的被遍历的点继续往下遍历，如果没有则回到上一个点重复上述操作。由此可以看出，宽度优先遍历往往容易得到图的整体性质，深度优先遍历往往容易得到图的局部性质。 如右图，根据桥的定义可以知道，虽然去除连通图中被称作桥的边e3,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进行遍历并传递相应的值 ??