月归档：十二月 2013

本文地址：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制作］