总结DFN-LOW算法在图论中的应用

总结算法在图论中应用北京大学许辰长市雅礼学屈运华摘：在一连通图[1]G，有些点一旦被去除就会导致图不连通，同样的，有些边一旦被去除也会导致图G失连通性，那么如何求出这些点和边就是一个需要被解决的问题。为此一种算法通过标记每个按照遍历顺序得到的序号和查看该点通过边可以到达的点的最小序号来进行判定，解决了这个问题。此算法简单而容易理解，简称为D法。关字有向图无向图强通分量桥割一

引有关图论的几个问题，如求无向[2]的[、无向图的割[4]、有向[5]强连通分量[等，都能够被几种不同的算法解决。其中有种算法，找到了这几个问题的共性，通过记录每个点的DFN值和LOW，用大同小异的判定方式简洁的解决了这几个问题，思路巧妙具有针对性，把握住了问题的关键，值得借鉴。本篇论文将回顾D算法在图论中的应用及解决相关问题时的思路。二

通无图的质出DFN-LOW算法图行历方要了解图的一些性质必然要对进行遍历对图进行遍历的方式主要有两种一种是宽度优先，一种是深度优先。它们的本质区别在于宽度优先是按照每个点到源点的距离一层的整体进行遍历于每层点次和它们相连且尚被遍历的点放入下一层深度优先则是每次从当前点遍历到一个与它相连且尚未被遍历的点由新的被遍历的点继续往下遍历果有则回到上一个点重复上述操作由可看出宽优先遍历往往容易得到图的整体性质深度优先遍历往往容易得到图的局部性质。如右图，根据桥的定义可以知道，虽然去除连通图中被称作桥的边e<3,4>后会导致原图被分割成两个连通图，整个原图连通性丧失，但其本质只是导致了e的两个端点、4以通过3连通的点对间的连通性丧失，即法通过除了以的边集到达4，这相对而言属于局部性质，所以用深度优先进行图的遍历更加容易分析桥和图的连通性之间的关系。此外不是何种遍历在遍历程中每个点都可能会被多次访问到但是由于每个点都只会被遍历一次，所以由图中所有点和遍历[7]成的图G`必然是一棵树（以下图中用三角形表示子树），其中遍历边被称作树边（以下图中用实线表示），而原图中的非遍历边被称作非树边（以下图中用虚线表示）。三

通求向的引法要判定某条边是否为桥还要桥的性质进行进一步的挖掘那么直观的进行分析如右图在深度优先遍历中点通过了某条树边e遍到了点接着以2号为根遍历出了一棵子树，设子树中任意一点。如果边桥，则等价于删除了之后1号和

点会不连通2号无法通过访到号或者比1号更早被遍历到的点，e是为桥便可以由点的性质来进行判定。得到上述结论，便大致了解了DFN-LOW算判定桥的思想，接下来对算法进行具体讲述。在判定过程中，主要有两个量是判定的关键，因此定义、low两一维数组。用dfn[i]记录编号为i的的遍历序号，即第几个被遍历到的，用low[i]记录编号为i点在接下来的遍历中可以访问到的最小序号。那么由分析得知，对于通过树边e遍出的点，如果在接下来的遍历中u无法访问到序号比u更的点，即dfn[u]于low[u]，么e就桥。而根据low值定义又可以知道的low值以由与u有边相连的点的low值算出来。根据这个思路，便可以写出整个算法的流程，下面以c++代码为例加以说明。voide)通过树边e历到了当前点{tot++;//累加遍历序号dfn[u]=low[u]=tot;//初的dfn和low值为遍历序号for访问每个与u相的点vif不直接通过无向边e从u访问回序号小的点，否则算法失去意义{if如v尚被遍历（设序号从开标记）{bridge(v,edge_lable[u][i]);//么对进行遍历并传递相应的值if能问到的点然也能访问到，所以用low[v]更low[u]}if(dfn[v]<low[u])//果v已被遍历么能访问到用dfn[v]新low[u]}if(low[u]==dfn[u])//如果遍历完以u为的树后low[u]仍等于则明e为printf("%ldn",e);//输出

}四

求向的顶通过求无向图的桥算法的判定思路已经展示的非常清晰而同时根据顶的定义可以发现桥的两个端点必然割顶删了割顶等价于删除了桥这说明了割顶和桥在性质上是非常类似的在无向图的割顶的时候可按照求桥时的思路进行判定，但是由于点和边的结构不同，所以一些细节也是必须要考虑的。那么直观的分析一下割顶的特点，如右图1号通过树边遍历到了2号点，然后以号点为根遍历出了一个子树，设u为树的任意一点。如果1点是割顶，则等价于删除了1号点后点将与1号以及比点更早被遍历到的点不连通2号无通过访问到比1号序号更小的。所以便可以得到结论v为u的一个儿子[8]的low值不小于的dfn值u为的割顶。关于这个结论，有三个细节需要注意。第一点，在结论中v的low值于u的dfn值结论也成立，这个很显然，看图分析即可得到。第二点，如果为深度优先遍历的根节点，那么只当它有至少2个子v1、同时满足它们的low值小于的dfn时结论才成立。如右图，若子不存在，那么删除仅只是删除了图的一端点，剩下v1仍是连通的。所以判定根节点是否为割顶时要特殊考虑。第三点，在第二点中v1、v2必是u的儿子，即必须是由u过树边遍历出的点。如右图v2和边相连但不是的子v2必在以v1为根的子树中u是图“缘上的一个点，删除u后、v2仍连，在图的连通性方面、v2也等价的，所以应不对v2进考虑。根据以上讨论，便可以写出整个算法的流程，下面以c++代码为例加以说明。voidcutpoint(longe)通过树边e历到了当前点u{i,v,sum;tot++;//累加遍历序号dfn[u]=low[u]=tot;//初的dfn和low值为遍历序号sum=0;//初始化满足条件的儿子个数for访问每个与u相的点vif不直接通过无向边e从u访问回序号小的点，否则算法失去意义{

}五

if(dfn[u]如v尚被遍历（设遍历序号从开始）{那对v行遍历并传递相应的值if能问到的点u必也能访问到以low[v]更low[u]if(low[v]>=dfn[u])//果儿子不能访问到比u序更小的点sum++;//累加满条件的儿子个数}if(dfn[v]<low[u])//如v已被遍历u只访问到dfn[v]更}if((sum>=2)||//如果u为根且有满足条件的儿子或者为且有不少于2个足条件的儿则为割顶printf("%ldn",u);//输出求向的连分DFN-LOW法在无向图中的应用是非常简捷的因为无向图具有非常好的性质所有边都是无向边，因此有边相连的点集必然会形成一个连通。而有向图则不然，即使一个连通图在边被定向之后也未必强连通以对于有向图来说桥和割顶难以成为重心相对的有图中才有定义的强连分量则成为了有向图中的重心文讨论的强连通分量均默认为极大强连通分[。根据强连通分量的定义可以发现不同于桥或者割顶只是单个点或者边是点和边的集合，这就说明了求强连通分量会更加的复杂和烦琐。但是即便如此，仔细观察可以得知，它和桥或者割顶却有着极其类似的性质，如右图1号由树边遍历到了2号，并以2号点为根遍历出一棵子树果棵树成为了一个强连通分量等于2号点无法和1号或者比点更早被遍历到的点强连否该强连分量不极大即号点无法通过有向边经过访问到号点或者比点序号更小的点。这个结论和对桥进行判定时的结论简直如出一辙全可以用同样的思路来求强连通分量。为了方便强通分量的过中只记录每个强连通分量的点一个强连通分量之中，点之间的有向边即为强连通分量的边。所以在深度优先遍历的过程中次新遍历到一个点就该点压入栈中当某点u为的子树遍历完之后，low值等于dfn值则说明找到了一个新的强连通分量，此

时因为强连通分量中的点均在以根的子树中，即应当在栈之中，所以从栈尾点一直这一段点就是组成当前强连通分量的点集。关于上述算法有个细节需要意因有向图的边有向所以点的连通性有称性，如果用完全一样的方式计算low值能会出现错误，如右图然分别成为了三个强连通分量。但是深度优先遍历按照234567的序遍历时5会为有边指向并接着访问到了致5的low值于的dfn值而4dfn值是显然比的dfn值的，因此这样便无法在遍历完以5为的子树后判断出这个强连通分量，相反的会把1567判定为一个强连通分量。细观此过程可以发现对进行遍历时其实234已被作为一个强连通分量剔除了再将对图的其他部分进行影响在更新low值时候不应该考虑已经被划分到某强连通分量中的点，即只考虑仍在栈中的点。同时考虑到如果按照1564237的序进行遍历遍完4为根的子树时就会判断出强连通分量234并其从栈中删除在历完以为的子树并判断出强连分量时栈中只会剩下567，不会出现把234567判定为一个强连通分量的情况，算法是正确的。根据以上讨论，便可以写出整个算法的流程，下面以c++代码为例加以说明。voidgroup(long//过有向边遍历到了当前点{tot++;//累加遍历序号dfn[u]=low[u]=tot;//初的dfn和low值为遍历序号累加栈中点数量stack[s_num]=u;//将压栈尾in_stack[u]=true;//记栈中for访问每个与u相的点v{if(dfn[v]==0)//如果尚未被遍历（设序号从1开始标记）{group(v);//么对进行遍历if能问到的点必然也能访问到，所以用更新low[u]}

if(dfn[v]<low[u])//如v已被遍历，那么能访问到vif(in_stack[v])//如v在中会影响到点，用更low[u]}if(low[u]==dfn[u])//如果遍历完以为的树low[u]=dfn[u]则明找到一个新的强连通分量从尾到u这段点为一个强连分量，依次退栈{标记该点与u属同一个强连通分in_stack[stack[s_num]]=false;//取在栈中的标记s_num--;}}六

算实中注事及间杂分至此DFN-LOW算在图论中的应用基本讲述完毕，但是在整个实现过程中有几个要点仍然是需要被强调的。．．在利用DFN-LOW算解决有关无向图的问题时，原图很可能本身就是不连通的，这时候任何一个点都将成为割顶何一条边都会成为桥过更多的情况是要求对原图中的每个连通块进行单独处理。所以要考虑原图的连通性。类上述情况有图一般情况下原图就是非强连通的所以求强连通分量时每次必须找一个未被遍历过的点并以它为根进行深度优先遍历求强连通分量所点都被遍历后才能结束。1因为无向边的无向性导致一条边可能被访问两次以求无向图的桥时需要规定不能直接由原树边访问回去并更新low值则法将严出错为整个判定过程包括计算low值都是假定相应的点、边已经被删除后的状态。对于有向图则不需要这个多余规定，因为在对有向图进行遍历的过程中一条边只可能被访问一次。．．在求无向图的桥时可能出现重[，以上述规定能简单的描述每个点不能通过边直接访问其父亲节”，因为某点可能通过重边访问到它的父亲节点，同时显然重边是不可能成为桥的。．在求有向图的强连通分量时，不能错将遍历序号用深度优先遍历中的深度代替。为有向图中边是单向的以遍历序号小的点不一定比遍历序号大的点深度小果进行上述替换，必然会使得求强连通分量时出现错误，如右图。显然全部点构成一个强连通分量按照的序深度优先遍历3号的深度会大于号点的深度，所以4号的low值不会被更新，这样算法便会将单判定成一个强连通分量而出错。．在求无向图的割顶时，对于u由树边访问到的已经遍历过的点v，不能错用v的low值更新的low值因为可能就是割顶，一旦v被除u就无法通过v访问到low比v

的dfn值低的点，所以只能用v的来更新u的low值否则，如右图号点显然是图中的一个割顶按照的顺序深度优先遍历且在遍历到以3号为根的子树时先通过非树边访问了点并由号点的low值新号点的low么在接下来在遍历中3号的low值通过非树边更新号点的low值5号的low值会通过树边更新点的low值最后导致4号点的low值号的dfn值，判定3不是割顶，出错。．根据性质，第二条不会影响算法对无向图割顶的判定；第三条不会影响算法对无图桥和割顶的判定第条不会影响法对无向图桥向图强连通分量的判定但是为了养成良好的习惯，减少出错概率，建议在实现算法时对上述几条均予以考虑。DFN-LOW法在对图进行深度优先遍历时每个点只会被扩展一次每条最多也只会被访问两次，所以时间复杂度是ON+M），和输入时间复杂度是同一个级别，已经达到下限同虽然示例程序中是用接表的方式存储边是如果用链表结构来存储边算法的空间复杂度也将降低至ON+M。可见算是非常优秀的。七

结从整体的角度来观察整个算法度先遍历时的树边就如同图的骨架得中任意两点间有且只有一条树边路径12]，而非树边则是将两点