月归档:十二月 2013

用深度优先搜索(DFS)确定图的割点

本文地址:http://sokoban.ws/blog/?p=1000 之前的博文《推箱子游戏的一个箱子推动路径搜索算法 (二)》介绍了图论中寻找割点的算法在推箱子路径搜索中的应用。但是对用DFS寻找割点的原理说得不够清楚明白,本文的目的是试图进一步阐明这个算法,并把示意图画的更漂亮一些。 用DFS遍历一个图的所有顶点时,按访问顺序依次标号为1到n,称之为DFS数。顶点v的DFS数记作D(v)。并得到一棵DFS树(黑色边),称DFS树的边为树边(tree edge),其余的边(红色边)称为回头边(back edge)。如下图,图的边都按搜索过程中向外的方向定向,得到一个有向图。树边都是从DFS数小的顶点指向大的,回头边都是从DFS数大的顶点指向小的。   根据上面由深度优先搜索得到的有向图中,可定义每个顶点的低位数(lowpoint):从该顶点出发,只用最多一条回头边,沿有向边能走到的顶点中DFS数最小值。顶点v的低位数记为L(v)。 低位数取值有两种情况:一是没用上回头边,则能走到的DFS数最小的的顶点就是该点自身,对应的路是一个顶点构成的平凡的路。此时L(v)=D(v)。二是用了回头边,则一定是最后一条边是回头边,走到一个DFS数更小的顶点。此时L(v)<=D(v)。 所以,一般地,总有L(v)<=D(v)。 有了这两个参数,就可以确定割点了:对根节点,即DFS数为1的顶点,其为割点当且仅当在DFS树中有两个或以上子节点;其余所有非根节点v是割点的充分必要条件是:v存在一个子节点u(在DFS树中的子节点)满足u的低位数大于等于v的DFS数,即L(u)>=D(v)。 下图标出的顶点的低位数(圈外数字,没标圈外数字的顶点低位数和DFS数相等),绿色顶点为割点。 注:若用 DFS的深度(depth)来替代上面算法中的DFS数,并用深度来计算低位数,则算法一样能有效地找出割点。 [参考文献] 1. Shimon Even, Graph Algorithms (2nd Edition). Cambridge University Press. 2012. p52-54 [文中的图使用http://draw.io制作]

发表在 数学, 算法 | 留下评论