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，因為深先世足！