5 图的走访 - DFS 篇

今天要跟大家分享另一种在图上面遍历所有节点的深度优先搜索 (Depth First Search, DFS)。深度优先搜索与广度优先搜索不同的地方是，在实作方面通常我们会使用递回方法，当遇到一个新节点的时候，直接探索下去。如果一直找得到新节点，那麽就可以走出一条很长很长的路径。

DFS 有非常非常非常多的应用，让我们来看看以下几个有趣的例子：

5.1 多样化的边着色问题

问题是这样的，给你一张至少有两条边的连通图 G。请你将这张图的每一条边指定黑色或白色，请问有没有一种着色方法，可以保证对於每一条边，总是有一条与之相连的不同色的边？

（备注：这题好像只需要生成树就可以了，不太需要用到 DFS 的特性）

5.2 找出图上的关节点 (Articulation Points)

所谓的关节点，就是整张原先连通的图里面，如果拿掉就会断开的节点们。我们可以利用 DFS 树不会有跨越边 (crossing edge) 的特性，来找出关节点们。

5.3 找出欧拉路径 (Eulerian Path)

欧拉路径问题，也就是一笔画问题：给你一张连通的图，请问是否存在一个不重覆经过边（但允许重复踏上同一个点）的情形下，走出一条恰好经过所有边一次的路线？十八世纪的着名瑞士数学家欧拉（对，就是解决七桥问题开辟图论领域的先知）曾经证明过，如果该连通图所有点的度数都是偶数（或是恰好有两个点的度数是奇数），那麽就存在一条这样的一笔画路径。

但，演算法该怎麽设计呢？基本上有两派解法：一种是每一次踏一步，只要保持图没有断开，就可以继续向前走，直到走完整张图。但是检查断开这件事情，要做到有效率其实是稍微复杂些的（这个问题也被称为 Decremental Connectivity Problem，做演算法研究的人们也还在努力把它加速，目前还没有办法把最佳上界和最佳下界的间隙合起来）。这个方法是由法国的一名高中数学老师 Fleury 在 1883 年提出的演算法。

尽管 Fleury 的演算法实作上没有办法做到太快，但它的浅显易懂也成为了理解欧拉路径的第一步。而事实上，若我们将时间回溯到更早以前，德国数学家 Hierholzer 早在西元 1873 年就已经提出了以现在演算法观点中更有效率的演算法：每一次随意走出一条封闭路径，然後将任何两条有重叠点的封闭路径黏接起来，形成更大的封闭路径。重复以上的操作便能够找出一条欧拉路径。

转换成 DFS 的做法就是：一直走一直走，走到不能再走的时候，将刚探索完毕的边放入一个堆叠，最终这个堆叠就能够形成一条欧拉路径了！

参考资料：

https://jlmartin.ku.edu/courses/math105-F11/Lectures/chapter5-part2.pdf
https://hsm.stackexchange.com/questions/12633/who-was-fleury-and-what-was-his-first-name

5.X 冷笑话

在爬世界杯足球赛网站的时候，应该要用 DFS 还是 BFS 呢？当然是 DFS，因为深先世足！