這是「Practical Computer Science」系列的下一篇，你將學習如何應用經典電腦科學概念用 Ruby 解決真實問題。
今天我們要談 Graph Theory（圖論）。
你可能聽過 binary trees，長這樣：
重點是 binary tree 只是 graph 的特化版本，這應該讓你對 graph 的普及程度有概念。
讓我們從圖論基礎概覽開始，然後看實際用途和如何在 Ruby 實作！
圖論基礎
一個圖由兩個元素組成：
- Nodes（節點，或稱 vertices）
- Edges（邊）
一個節點代表圖中的一個元素，像城市或街道，在地圖圖中。而邊代表節點間的連接。
如果你看電腦科學或數學書，會看到圖用這公式定義：G(V, E)。
G 是 Graph，V 是 vertices 集合，E 是 edges 集合。
圖可以是 directed（有向）或 undirected（無向）。意思是你只能單向（有向圖）或雙向（無向圖）。
最熱門的圖類型是 Directed Acyclic Graph (DAG)。Acyclic 意思是沒有迴路，無法回溯。
圖的用途
看完基礎概覽，來看圖的常見用途。
用圖你可以做：
- 找兩地間最短（或最長）路徑
- 檢查兩件事是否相關
- 建立推薦引擎
- 分析依賴關係
另一個例子是找到目的地的最佳路徑（想像 GPS 裝置）。
如何實作與使用圖
你可以自己寫圖實作，但這篇我們用 RGL gem，它已經實作好了。
用 RGL 建立基本圖：
require 'rgl/adjacency' graph = RGL::DirectedAdjacencyGraph.new graph.add_edge 1,2 graph.add_edge 3,4 graph.add_edge 1,4 graph.add_edge 4,3
這段代碼產生以下圖：
你可以這樣取得圖的圖形表示：
require 'rgl/dot' graph.print_dotted_on
然後把那個方法的輸出複製到能處理 dot 語言的網站。像這個。
或者，你可以在機器上安裝 Graphviz 在本地產生圖片。
現在我們有圖了，可能想遍歷它來找資訊。
搜尋圖的兩個基本演算法：
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
BFS 先取得最近的節點，DFS 則對每個節點盡可能深入。這些演算法可用 stack 資料結構實作。
RGL gem 已經幫你實作了那些演算法：
require 'rgl/traversal' graph.bfs_iterator.to_a # [1, 2, 4, 3] graph.dfs_iterator.to_a # [1, 4, 3, 2]
再看一次圖，用眼睛（或手指）跟著這些演算法的路徑。這會幫助你理解發生了什麼。
加權圖 (Weighted Graphs)
我們可以用權重給圖加更多資訊，使它更有用。
權重給邊，也就是 兩個節點間的路徑（也稱「vertices」）。這些權重代表從一點到另一點的成本。
例如，如果我們有國家地圖形式的圖，想用最短時間到達目的地，權重代表兩城市間的距離。
或者如果我們有電腦網路，權重可能代表到達某網路需要多少 hops。
「在電腦網路中，hop 是來源和目的地之間路徑的一部分。資料封包在來源和目的地之間傳遞時會經過橋接器、路由器和閘道。每次封包傳遞給下一個網路裝置，就發生一個 hop。」 — Wikipedia
這裡有加權圖的程式碼範例：
graph = RGL::DirectedAdjacencyGraph.new graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle" edge_weights = { ["New York", "Los Angeles"] => 2445, ["Los Angeles", "Chicago"] => 2015, ["Los Angeles", "Houston"] => 1547, ["Chicago", "Houston"] => 939, ["Seattle", "Los Angeles"] => 1548 } edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) } 我們現在可以搜尋從一點到另一點的最短路徑。這正是下一節的主題！
尋找最短路徑
在圖中尋找最短路徑的熱門演算法是「Dijkstra's Shortest Path」演算法。
給定加權圖，我們可以用 Dijkstra 演算法解決這問題：
「從點 A 到點 B 最快的路是什麼？」
這裡有用 RGL gem 的程式碼範例：
p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston") # ["New York", "Los Angeles", "Houston"]
這告訴我們從紐約到休士頓的最短路徑，用圖中可用的資訊。
總結
你學到了什麼是圖資料結構 以及如何用 RGL gem 使用它。
也學到了處理圖的常見演算法，像 DFS, BFS 和 Dijkstra's。
如果覺得有用別忘了分享這篇文章 讓更多人享受 🙂
