跳轉到

7.2 圖的表示法#

概念說明#

圖（graph） G = (V, E) 由頂點集合 V 與邊集合 E 構成。邊可以有方向（有向圖，如「A 關注 B」）或無方向（無向圖，如「A 和 B 是朋友」）；邊可以帶權重（如道路的距離）。樹是「無環連通圖」的特例，圖是比樹更一般的結構。

兩大表示法：

  1. 相鄰矩陣（adjacency matrix）：n×n 布林（或權重）矩陣，M[i][j] = 1 表示 i 到 j 有邊。查「i、j 相鄰嗎」是 O(1)；但空間 O(n²)，走訪鄰居要掃整列 O(n)。適合稠密圖。
  2. 相鄰串列（adjacency list）：每個頂點掛一個鄰居串列。空間 O(n + m)（m 為邊數）；查相鄰是 O(deg(v))，走訪 v 的所有鄰居只花與鄰居數成正比的時間。適合稀疏圖（大多數現實圖都是稀疏的，如社群網路每人只連少數人）。
  3. 邊串列（edge list）：把所有邊存成 (u, v, w) 的串列。最省事，適合 Kruskal 這種「按邊權排序」的演算法。

Python 實作#

class Graph:
    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.adj = [[] for _ in range(n)]      # 相鄰串列
        self.matrix = [[0] * n for _ in range(n)]  # 相鄰矩陣
        self.edges = []                        # 邊串列

    def add_edge(self, u, v, w=1):
        self.adj[u].append((v, w))
        self.matrix[u][v] = w
        self.edges.append((u, v, w))
        if not self.directed:                  # 無向圖：兩邊都要加
            self.adj[v].append((u, w))
            self.matrix[v][u] = w

    def neighbors(self, v):
        return self.adj[v]

    def is_adjacent(self, u, v):
        return self.matrix[u][v] != 0

    def show(self):
        for v in range(self.n):
            links = ", ".join(f"{nb}({w})" for nb, w in self.adj[v])
            print(f"{v} -> {links}")

# 建一張無向加權圖：
#     0 --2-- 1
#     |      / \
#     4     3  5
#     |    /    \
#     2 --1------ 3
g = Graph(4)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 5)
g.add_edge(2, 3, 1)
g.show()
print("0 與 2 相鄰？", g.is_adjacent(0, 2))    # True
print("頂點 2 的度數：", len(g.adj[2]))        # 3

取捨對照#

操作 相鄰矩陣 相鄰串列
空間 O(n²) O(n + m)
查 (u,v) 是否相鄰 O(1) O(deg(u))
走訪 v 的鄰居 O(n) O(deg(v))
BFS/DFS 全圖 O(n²) O(n + m)
加一條邊 O(1) O(1)

粗略判斷法：若 m 接近 n²（每個人幾乎認識所有人），用矩陣；若 m 與 n 同級（大多數真實網路），用串列。字典版相鄰串列（鍵為任意標籤而非整數索引）在原型開發時也很方便：

adj = {"台北": {"台中": 160, "花蓮": 130}, "台中": {"台北": 160, "高雄": 200}}

複雜度分析#

建立圖需 O(n + m)（相鄰串列）。後續章節的圖演算法複雜度都以表示法為前提：DFS/BFS 在相鄰串列上為 O(n + m)，在矩陣上為 O(n²)；Dijkstra 搭配堆積與相鄰串列為 O((n + m) log n)。選錯表示法，演算法效率可能無謂地差一個數量級。

練習#

  1. 實作 degree(v)（無向圖的度、有向圖分入度與出度），並寫函式驗證「所有度數總和 = 2×邊數」。
  2. 把相鄰串列改成字典版 adj[u][v] = w，實作 remove_edge(u, v)，分析其複雜度。
  3. 構造 n=1000、m=3000 的稀疏圖，分別用矩陣與串列表示，比較記憶體占用（用 sys.getsizeof 估算）與「走訪所有頂點鄰居」的總時間。