月归档:十二月 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制作]

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

再谈桌面操作系统

本文地址:http://sokoban.ws/blog/?p=984 在 上篇博文谈了以Ubuntu作为常用操作系统三年的体会。还不到半年,现在又变成使用Mac OS X和Windows 7更多了。 主要原因是过去三个月,软硬件使用有下面改变: 一、以前在Ubuntu上为佳能喷墨打印机安装驱动一直未成功。在Mac OS X上系统轻松自动安装驱动。 二、重拾慢跑习惯,买了新GPS手表Nike+ Sportwatch GPS记录跑步路径、步伐和心率等。而这手表只提供Mac和Win下的软件上传手表数据至Nike+网站社区。其它如Garmin 610等手表官方均只提供Mac和Win下管理软件。 据说有第三方程序可在Linux下提取手表数据。 三、买了计步腕带Fitbit Flex,和GPS手表的目的一样,是为了提醒自己少坐多动。据其统计数字,一般15分钟内步行1300步,慢跑则2500步。这玩意同样只提供了Mac和Win的数据上传软件。 四、买了个TomTom便携式导航仪,可每季度免费升级地图,但依然只提供Mac和Win的升级管理程序。 五、买星特朗天文望远镜送TheSkyX天文软件,可在Mac或Win下安装。当然 Linux下亦有功能相仿的自由软件。 六、虽LibreOffice可满足我几乎所有工作上的文档处理需求,但为方便和同事协同工作,还是买了微软的Office 365,可安装到5台Mac或Win电脑上。

发表在 见闻, 计算机 | 留下评论