2.3 圖論中的P問題#

概念說明#

圖（graph）由頂點與邊組成，是描述關係結構最通用的數學模型：社群網路、道路系統、電路、任務依賴關係。圖論提供了大量屬於 P 類的問題，這些問題正是整套 NP 理論的「比較基準」，因為即使在同一張圖上，也會同時存在輕鬆可解的問題與（已知）指數時間才可解的問題。

本章介紹三個經典的 P 類圖問題：

最短路徑：給定帶權圖，求兩頂點之間總權重最小的路徑。Dijkstra 演算法 O((V+E) log V) 可解（權重非負），Bellman–Ford O(VE) 可處理負權。
最小生成樹（MST）：用 V−1 條邊把所有頂點連起來，且總權重最小。Kruskal 與 Prim 演算法都能在 O(E log V) 內解決。
拓撲排序：對有向無環圖（DAG）排出頂點順序，使每條邊都從前面指到後面。O(V+E) 可解，常用於課程先修、建置依賴。

有趣的是，同樣材料的「鏡像問題」卻非常困難：最短路徑好解，但「最長簡單路徑」是 NP-hard；兩點之間最短路徑好解，但「拜訪所有頂點一次的最短路徑（TSP）」是 NP-hard；生成樹好解，但「每頂點度數恰好為 2 的最小生成子圖」也是 NP-hard。這種對照貫穿全書。

演算法步驟#

Dijkstra 演算法#

起點 s 的距離設 0，其餘設 ∞，所有頂點進入「未確定集合」。
每次從未確定集合取出距離最小的頂點 u，標記為已確定。
對 u 的每個鄰居 v，若 dist[u] + w(u,v) < dist[v]，更新 dist[v] 並記錄前驅。
重複 2–3 直到目標頂點確定或所有頂點確定。
由前驅鏈回溯還原路徑。

Kruskal 最小生成樹#

將所有邊按權重遞增排序。
依序取邊，若該邊兩端點目前不在同一連通分量（用並查集判斷），加入生成樹。
集滿 V−1 條邊即完成。

拓撲排序（Kahn 演算法）#

統計每個頂點的入度，把入度為 0 的頂點放入佇列。
取出一個入度 0 的頂點，放入輸出序列。
刪除其所有出邊（也就是把鄰居入度減 1），入度變 0 的鄰居進佇列。
重複直到佇列空；若輸出數量 < V，代表圖中有環，無法拓撲排序。

Python 程式碼範例#

import heapq

def dijkstra(graph, start):
    """graph: {u: [(v, w), ...]}"""
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    pq = [(0, start)]
    parent = {start: None}
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue          # 過期項，略過
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                parent[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, parent

def kruskal(n, edges):
    """edges: (w, u, v)"""
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total

def topo_sort(graph):
    indeg = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    queue = [v for v in graph if indeg[v] == 0]
    order = []
    while queue:
        u = queue.pop()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None

# 範例：活動之間的依賴 DAG
dag = {
    '起床': ['刷牙', '早餐'], '刷牙': ['上班'],
    '早餐': ['上班'], '上班': [], '穿衣服': ['刷牙']
}
print("拓撲順序:", topo_sort(dag))

g = {0: [(1, 4), (2, 1)], 1: [(3, 1)],
     2: [(1, 2), (3, 5)], 3: []}
dist, parent = dijkstra(g, 0)
print("最短距離:", dist)

edges = [(4, 0, 1), (1, 0, 2), (2, 1, 2), (5, 2, 3), (1, 1, 3)]
print("MST:", kruskal(4, edges))

複雜度分析#

Dijkstra（二叉堆）：每個頂點、邊各操作一次堆，O((V+E) log V)；空間 O(V+E)。
Kruskal：排序 O(E log E) 主導，並查集近 O(1)（帶路徑壓縮與按秩合併），總計 O(E log V)；空間 O(V)。
拓撲排序：每個頂點與邊各掃一次，O(V+E)；空間 O(V)。
三者都是多項式時間，且排放序、生成樹的解甚至可直接構造，無需倚賴指數級搜尋。

練習#

將 Dijkstra 改為「走到每個頂點就停止」的版本，找出範例圖中 0 到 3 的實際路徑（用 parent 回溯），並驗證總權重為 4。
遺失某條邊後 battery 站點仍需連通：給定 n 個節點與邊列表，寫程式判斷「哪些邊屬於所有 MST」（最小瓶頸性質，可用 Kruskal 過程驗證）。
對照思考：給定無向圖，求「最長簡單路徑」。請寫一個暴力指數搜尋程式，並在 10 個頂點的隨機圖上實測耗時，體會為何它與 O(V+E) 的最短路徑有本質差異。