Graph Traversal

Graph Traversal

給你一張圖,要怎麼讀出它的資訊呢?

用人眼來觀察一張圖,很快的就能看出點和線,一點一點釐清關係。要是一張圖能夠畫得漂亮一點,上個鮮明的顏色,那就更好了。

電腦則不然。要以電腦來讀取一張圖的資訊(這資訊想必會以圖的資料結構來妥善儲存),唯一的方法就是透過程式語言,以及良好的演算法囉!

Traversal中文稱做「遍歷」。圖的遍歷,也就是指通盤地讀取圖的資訊:決定好從哪裡開始讀,依照什麼順序讀,要讀到哪裡為止。詳細地設計好流程,始能通盤地讀取圖的資訊;如果設計得漂亮,在解決圖的問題時,還可以一邊讀取圖的資訊,一邊順手解決問題呢!

經過資訊學家苦心鑽研,最後淬煉出兩種遍歷演算法:Depth-first Search和Breadth-first Search。這兩個演算法充分了利用程式語言的特性,是非常簡約而美麗的演算法。由於它們的簡約與美麗,使得它們能夠適用在許多問題當中、融入到各種概念當中;使得它們除了讀取資訊,還能用以解決難題。因此,Depth-first Search和Breadth-first Search成為資訊領域不可不知的演算法。

Graph Traversal: Depth-first Search

Depth-first Search(DFS)/ Depth-first Traversal

DFS可以遍歷出多棵樹(或只有一棵),稱作DFS trees。DFS也可以用在tree traversal。

演算法

依照編號順序,不斷找出尚未遍歷的點當作起點,進行下述行為:
 甲、把起點放入stack。
 乙、重複下述兩點,直到stack裡面沒有東西為止:
  1. 從stack當中取出一點。
  2. 找出跟此點相鄰的點,並且尚未遍歷的點,依照編號順序通通放入stack。
(註:整個演算法完全不照編號順序,也是可以的。)

演算法展示Java Applet

如果各位找到更好的Applet,歡迎提供。

http://www.lupinho.de/gishur/html/DFSApplet.html

http://merganser.math.gvsu.edu/david/reed03/projects/haithcock/dfs.html

遍歷順序示意圖:以一個點首度被遇見的時刻來排序

功用不大。

遍歷順序示意圖:以一個點從stack取出的時刻來排序

DFS會優先走遍離起點最遠處,優先將樹變得深遠,Depth-first Search因此得名。

遍歷順序示意圖:以一個點進入遞迴和離開遞迴的時刻來排序

請對照後面的「遞迴版本程式碼」小節。進入遞迴的時刻以左上深色數字表示,離開遞迴的時候以右下淺色數字表示。這個順序常被運用於解決一些特別的圖論問題。

邊的分類(從CLRS上摘錄)

使用DFS來歷遍,會遇到圖上所有的邊。CLRS這本書將DFS一張有向圖所遇到的邊分成四類,每一類有自己的特性。供各位參考看看:

Tree Edges:DFS trees的邊。
Back Edges:連向祖先的邊。會形成環。
Forward Edges:連向子孫的邊。
Cross Edges:枝葉之間的邊、樹之間的邊。若配合的好,可能會形成環。

至於DFS一張無向圖所遇到的邊,只有上述四類中的其中兩類。可以想想為什麼。

Tree Edges:DFS trees的邊。
Back Edges:連向祖先的邊。會形成環。

時間複雜度

使用的資料結構為adjacency matrix的話,可以以O(V^2)時間遍歷整張圖;使用adjacency lists的話,可以以O(V+E) 時間遍歷整張圖。V是圖上的點數,E是圖上的邊數。

程式碼(adjacency matrix)

遞迴版本程式碼(adjacency matrix)

程式語言中的遞迴,其實就是利用stack來實做的。由於DFS操作stack的方式,就跟實做遞迴時操作stack的方式相同,所以DFS的程式碼也可以寫成遞迴形式。

這邊有一些利用DFS的遍歷順序,得以順利解決的問題:

UVa 599 676 705 10004 10308 10505 10672 10939

Graph Traversal: Breadth-first Search

Breadth-first Search(BFS)/ Breadth-first Traversal

可參考DFS,把stack改換成queue即可。

遍歷順序示意圖(以從queue取出點的時刻來排序)

BFS會優先走遍離起點最近處,優先將BFS trees變得寬廣,故得名Breadth-first Search。

Traversal v.s. Search

為什麼這兩種Traversal演算法要叫做Search,而不直接叫做Traversal呢?我也不知道。可能是早期沒有Traversal這名詞吧?另外一方面,Traversal可以視作是對一張圖進行Search,所以其演算法才以Search來命名吧。

Weighted Graph Traversal

考慮權重的Graph Traversal

DFS和BFS都是不考慮邊的權重的Graph Traversal的方式。

離第一點最近的點(及邊)先走,可得到Shortest Path Tree。

離目前走過的點最近的點(及邊)先走,可得到Minimum Spanning Tree。

離目前走過的點的距離總和最近的點先走,可得到Minimum Cut。