書籍資訊

  • 書名：《圖解演算法：使用 C#》
  • 類型：圖論基礎與路徑演算法整理

這篇在講什麼

這一篇從圖的表示方式開始，往下整理到：

  • DFS / BFS
  • 生成樹
  • 最小生成樹
  • 最短路徑

它算是把圖論裡最常見的一批入門主題串在一起。

圖怎麼表示

圖由兩部分組成：

  • 頂點 Vertex
  • 邊 Edge

常見表示法有幾種。

鄰接矩陣

鄰接矩陣適合：

  • 節點數固定
  • 圖比較密
  • 想快速查兩點是否直接相連

特點是：

  • 查連線很直接
  • 空間成本通常是 O(n^2)

鄰接串列

鄰接串列適合：

  • 圖比較稀疏
  • 想節省空間
  • 需要遍歷某個節點的所有鄰居

它在實作 DFS / BFS 時很常見。

DFS 與 BFS

DFS

深度優先搜尋 DFS 的思路是：

  • 先一路往深處走
  • 走不下去再回頭

它通常搭配：

  • 遞迴
  • Stack

常見用途：

  • 連通分量
  • 拓撲相關搜尋
  • 回溯問題

BFS

廣度優先搜尋 BFS 的思路是：

  • 先把同一層走完
  • 再往下一層推進

它通常搭配 Queue。
如果圖是無權圖，BFS 還能拿來找最少邊數的最短路徑。

public static void BFS(List<int>[] graph, int start)
{
    bool[] visited = new bool[graph.Length];
    Queue<int> queue = new Queue<int>();

    visited[start] = true;
    queue.Enqueue(start);

    while (queue.Count > 0)
    {
        int current = queue.Dequeue();
        Console.WriteLine(current);

        foreach (int next in graph[current])
        {
            if (visited[next])
            {
                continue;
            }

            visited[next] = true;
            queue.Enqueue(next);
        }
    }
}

生成樹

當圖是連通的時候，可以從原圖抽出一棵覆蓋所有頂點、但不形成環的樹，這就是生成樹 Spanning Tree。

它的重點是：

  • 包含所有頂點
  • 邊數剛好夠連起來
  • 不多出環

DFS 與 BFS 都可以生成各自風格的生成樹。

最小生成樹

如果每條邊都有權重，就可以問：

有沒有一棵生成樹，總權重最小？

這就是最小生成樹 Minimum Spanning Tree。

兩個經典方法是：

  • Prim
  • Kruskal

可以這樣直覺記：

  • Prim：從某個點往外擴
  • Kruskal：從最便宜的邊開始挑

共同目標都是：

  • 把所有點連起來
  • 同時避免成環
  • 讓總成本最小

最短路徑

Dijkstra

Dijkstra 適合：

  • 邊權重非負
  • 想求單源最短路徑

它的思路是每次確認一個目前距離最短的節點，再用它去更新別人。

A*

A* 可以看成 Dijkstra 的強化版。
它除了已知成本，還會加上對終點的估計成本，也就是 heuristic。

它常見於：

  • 地圖尋路
  • 遊戲 AI 導航

Floyd-Warshall

Floyd 比較像全域型方法，重點不是從單一來源出發，而是一次求出任意兩點之間的最短路徑。

它適合：

  • 節點數不大
  • 需要全點對最短路徑

我自己的整理

圖論常讓人覺得名詞很多，但如果先抓住層次，會清楚很多：

  • 表示法：資料怎麼存
  • DFS / BFS：圖怎麼走
  • 生成樹：怎麼連全部節點但不成環
  • 最小生成樹：怎麼用最低成本連起來
  • 最短路徑：怎麼找從 A 到 B 最省的走法

其實每一層都是在回答不同問題，而不是同一題的不同寫法。

先記住的重點

  • 稀疏圖常用鄰接串列，稠密圖較常用鄰接矩陣
  • DFS 偏向往深處探索，BFS 偏向逐層擴張
  • 生成樹要求連通且不能有環
  • 最小生成樹重點是總成本最小
  • Dijkstra、A*、Floyd 解的是不同型態的最短路徑問題