這是資料結構的最後一篇，明天開始進入本系列的重點驗算法，前面幾天，我們介紹了各種樹結構 Binary Tree、Balanced Tree，以及其他衍生樹。而樹是一種特殊的圖結構，今天我們正式進入 Graph 的世界。

圖是比樹更一般化的資料結構，能表示任何實體之間的關係，例如:

• 社群網路 (人與人之間的連結)
• 地圖 (城市與道路)
• 網頁 (網頁與超連結)
• 電腦網路 (節點與連線)

理解圖結構，幾乎等於打開了資料結構與演算法的第二扇大門。

基本定義

圖 (Graph) 由以下兩個元素組成:

• V (Vertices): 頂點 (節點, nodes)
• E (Edges): 邊 (連線, edges)，用來表示兩個頂點之間的關係

數學上通常記為:

$$
G = (V, E)
$$

圖的分類

• 有向圖 (Directed Graph) vs 無向圖 (Undirected Graph)
  • 有向圖的邊有方向，例如 Twitter 的「追蹤關係」。
  • 無向圖的邊無方向，例如 Facebook 的「好友關係」。
• 加權圖 (Weighted Graph) vs 無權圖 (Unweighted Graph)
  • 加權圖的邊帶有權重 (weight)，例如道路距離或網路傳輸延遲。
  • 無權圖則所有邊的權重相同。
• 稠密圖 (Dense Graph) vs 稀疏圖 (Sparse Graph)
  • 若邊的數量接近 $|V|^2$，稱為稠密圖。
  • 若邊的數量遠小於 $|V|^2$，稱為稀疏圖。
• 循環圖 (Cyclic Graph) vs 非循環圖 (Acyclic Graph)
  • 有迴路的圖稱為循環圖。
  • 無迴路的圖則是非循環圖 (例如樹)。

圖的表示方式

鄰接矩陣 (Adjacency Matrix)

使用二維陣列 $A[i][j]$ 表示是否存在一條從節點 i 到節點 j 的邊。

• 優點: 判斷兩點是否相連 $O(1)$。
• 缺點: 空間複雜度高，對於稀疏圖浪費記憶體。

建立一個「無向圖 (undirected graph) 的鄰接矩陣 (adjacency matrix)」表示法:

# 範例: 無向圖 0-1, 0-2, 1-2, 2-3
n = 4
adj_matrix = [[0]*n for _ in range(n)]
edges = [(0,1),(0,2),(1,2),(2,3)]
for u,v in edges:
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1  # 無向圖

print("Adjacency Matrix:")
for row in adj_matrix:
    print(row)

鄰接串列 (Adjacency List)

使用 list 或 dict 紀錄每個節點相鄰的節點。

• 優點：空間效率高，適合稀疏圖。
• 缺點：判斷是否相連需。

建立一個「無向圖 (undirected graph) 的鄰接串列 (Adjacency List)」表示法:

from collections import defaultdict

n = 4
adj_list = defaultdict(list)
edges = [(0,1),(0,2),(1,2),(2,3)]
for u,v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u)  # 無向圖

print("Adjacency List:")
for k,v in adj_list.items():
    print(k, ":", v)

基本操作

• 新增頂點
• 新增邊
• 刪除頂點
• 刪除邊
• 查詢兩節點是否相連
• 圖的遍歷 (Traversal)

圖的遍歷

圖的遍歷是所有圖演算法的基礎。

深度優先搜尋 (DFS)

使用遞迴或 Stack，先往一條路走到底再回頭。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

dfs(adj_list, 0)  # 輸出: 0 1 2 3

廣度優先搜尋 (BFS)

使用 Queue，從起點開始一層一層向外擴展。

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

bfs(adj_list, 0)  # 輸出: 0 1 2 3

圖的應用

• 最短路徑: Dijkstra、Bellman-Ford、Floyd-Warshall
• 最小生成樹: Prim、Kruskal
• 網路流: 最大流問題 (Ford-Fulkerson)
• 拓樸排序: DAG 中的任務排程
• 社群網路分析: PageRank、Centrality
• 搜尋引擎: Web Page Ranking
• AI / 遊戲: 狀態空間搜尋 (A*)

結語

今天我們進入了圖結構 (Graph)，它比前面的線性結構與樹結構更通用，能夠描述任意的關聯關係。從 鄰接矩陣到鄰接串列，再到 DFS 與 BFS，這些都是後續更複雜圖演算法的基礎。

圖結構的強大之處，在於它幾乎無所不在:

• 當你使用地圖導航，背後就是最短路徑演算法。
• 當你搜尋網頁，背後是圖排名演算法。
• 當你研究社群網路，背後是圖分析模型。

理解圖結構，能讓我們從資料結構的「儲存與操作」進一步走向「建模與分析」。