iT邦幫忙

2021 iThome 鐵人賽

DAY 4
0
Software Development

圖論與演算法之間的相互應用系列 第 4

圖的走訪 - DFS 篇

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,因為深先世足!


上一篇
圖的走訪 - BFS 篇
下一篇
拓樸排序問題
系列文
圖論與演算法之間的相互應用30

尚未有邦友留言

立即登入留言