Python算法之图的遍历

本节主要介绍图的遍历算法BFS和DFS，以及寻找图的(强)连通分量的算法

Traversal就是遍历，主要是对图的遍历，也就是遍历图中的每个节点。对一个节点的遍历有两个阶段，首先是发现(discover)，然后是访问(visit)。遍历的重要性自然不必说，图中有几个算法和遍历没有关系？！

[算法导论对于发现和访问区别的非常明显，对图的算法讲解地特别好，在遍历节点的时候给节点标注它的发现节点时间d[v]和结束访问时间f[v]，然后由这些时间的一些规律得到了不少实用的定理，本节后面介绍了部分内容，感兴趣不妨阅读下算法导论原书]

图的连通分量是图的一个最大子图，在这个子图中任何两个节点之间都是相互可达的(忽略边的方向)。我们本节的重点就是想想怎么找到一个图的连通分量呢？

一个很明显的想法是，我们从一个顶点出发，沿着边一直走，慢慢地扩大子图，直到子图不能再扩大了停止，我们就得到了一个连通分量对吧，我们怎么确定我们真的是找到了一个完整的连通分量呢？可以看下作者给出的解释，类似上节的Induction，我们思考从i-1到i的过程，只要我们保证增加了这个节点后子图仍然是连通的就对了。

Let'slookatthefollowingrelatedproblem.Showthatyoucanorderthenodesinaconnectedgraph,V1,V2,…Vn,sothatforanyi=1…n,thesubgraphoverV1,…,Viisconnected.Ifwecanshowthisandwecanfigureouthowtodotheordering,wecangothroughallthenodesinaconnectedcomponentandknowwhenthey'reallusedup.

Howdowedothis?Thinkinginductively,weneedtogetfromi-1toi.Weknowthatthesubgraphoverthei-1firstnodesisconnected.Whatnext?Well,becausetherearepathsbetweenanypairofnodes,consideranodeuinthefirsti-1nodesandanodevintheremainder.Onthepathfromutov,considerthelastnodethatisinthecomponentwe'vebuiltsofar,aswellasthefirstnodeoutsideit.Let'scallthemxandy.Clearlytheremustbeanedgebetweenthem,soaddingytothenodesofourgrowingcomponentkeepsitconnected,andwe'veshownwhatwesetouttoshow.

经过上面的一番思考，我们就知道了如何找连通分量：从一个顶点开始，沿着它的边找到其他的节点(或者说站在这个节点上看，看能够发现哪些节点)，然后就是不断地向已有的连通分量中添加节点，使得连通分量内部依然满足连通性质。如果我们按照上面的思路一直做下去，我们就得到了一棵树，一棵遍历树，它也是我们遍历的分量的一棵生成树。在具体实现这个算法时，我们要记录“边缘节点”，也就是那些和已得到的连通分量中的节点相连的节点，它们就像是一个个待办事项(to-dolist)一样，而前面加入的节点就是标记为已完成的(checkedoff)待办事项。

这里作者举了一个很有意思的例子，一个角色扮演的游戏，如下图所示，我们可以将房间看作是节点，将房间的门看作是节点之间的边，走过的轨迹就是遍历树。这么看的话，房间就分成了三种：(1)我们已经经过的房间；(2)我们已经经过的房间附近的房间，也就是马上可以进入的房间；(3)“黑屋”，我们甚至都不知道它们是否存在，存在的话也不知道在哪里。