(Day 21) 圖演算法 (Graph Algorithm)

自從我們 Day 10 簡單地說一下圖結構後，就再也沒提到這個詞，我們今天開始就要介紹這個應用非常廣泛的圖 (Graph) 的演算法總覽，後續會接著介紹常見的圖演算法，因為圖是非線性資料結構中最重要的一員，在學術研究與實務應用上都有極高地位，從網路連線、地圖導航、社交網路到金融交易，幾乎都離不開圖的建模與演算法

基本定義

一個圖 (Graph) 由 頂點 (Vertex) 與 邊 (Edge) 所組成。形式化表示為 $G = (V, E)$:

• $V$ 是頂點集合
• $E$ 是邊的集合，每一條邊連接兩個頂點

圖可以依照性質分類:

• 有向圖 (Directed Graph) 與 無向圖 (Undirected Graph)
• 加權圖 (Weighted Graph) 與 非加權圖 (Unweighted Graph)
• 稠密圖 (Dense Graph) 與 稀疏圖 (Sparse Graph)
• 循環圖 (Cyclic Graph) 與 非循環圖 (Acyclic Graph)

圖的表示方法

圖的常見儲存方式主要有兩種:

• 鄰接矩陣 (Adjacency Matrix)
  • 使用一個 $n \times n$ 的矩陣來表示
  • 若頂點 $i$ 與 $j$ 之間有邊，則 $A[i][j] = 1$ (或權重值)
  • 適合稠密圖，但空間複雜度為 $O(n^2)$
• 鄰接串列 (Adjacency List)
  • 對於每個頂點，維護一個相鄰頂點的串列
  • 適合稀疏圖，空間複雜度接近 $O(V + E)$

圖的遍歷演算法

遍歷是理解圖結構的基礎，常見方法有:

• 深度優先搜尋 (DFS)
  • 思想: 沿著一條路徑不斷往下走，直到無法再深入，然後回溯
  • 實作方式: 遞迴或 Stack
  • 時間複雜度: $O(V + E)$
• 廣度優先搜尋 (BFS)
  • 思想: 一層一層展開，先訪問鄰居，再訪問更遠的節點
  • 實作方式: 使用 Queue
  • 時間複雜度: $O(V + E)$

常見圖演算法

• 最短路徑 (Shortest Path)
  • Dijkstra 演算法 (單源最短路徑，權重非負)
  • Bellman-Ford 演算法 (允許負權重)
  • Floyd-Warshall 演算法 (所有點對的最短路徑)
• 最小生成樹 (Minimum Spanning Tree)
  • Kruskal 演算法
  • Prim 演算法
• 拓撲排序 (Topological Sort)
  • 適用於 DAG (Directed Acyclic Graph)，常用於工作排程
• 網路流 (Network Flow)
  • 最大流演算法: Ford-Fulkerson、Edmonds-Karp

圖的應用

• 社交網路分析
  • 節點: 使用者
  • 邊: 好友關係
  • 演算法: 社群偵測、最短關係鏈
• 地圖導航
  • 節點: 城市 / 路口
  • 邊: 道路，邊權重為距離或時間
  • 演算法: Dijkstra、A*
• 金融交易網路
  • 節點: 帳號或公司
  • 邊: 資金流動
  • 演算法: 異常檢測、流量分析

結語

圖 (Graph) 是一種高度抽象且靈活的資料結構，能夠表示複雜的關係網路。掌握圖的基礎表示方法、遍歷演算法，以及常見的圖演算法，能讓我們解決從最短路徑、任務排程到網路流量優化的各種問題

在接下來的篇章中，會針對特定演算法（如 Dijkstra、Kruskal）做更深入的探討，讓大家能在理論與實作上都能熟練掌握

備註

• 同步發表於 iThome 鐵人賽 2025 - 快速掌握資料結構與演算法