圖 (Graph) 基礎教材

 適合初學者的Python 圖 (Graph) 基礎教材，介紹了三種常見的圖表示方式，並提供簡單的程式碼範例。此教材將幫助理解圖結構的基本概念及其應用。

---

圖的表示方式

在電腦科學中，圖是一種由節點 (Node) 和邊 (Edge) 組成的結構，用於描述物件之間的關係，例如網路中的計算機、地圖中的城市等。以下是三種常見的圖表示方式：

1. 鄰接矩陣 (Adjacency Matrix)
2. 鄰接表 (Adjacency List)
3. 邊列表 (Edge List)

---

1. 鄰接矩陣 (Adjacency Matrix)

鄰接矩陣是一個二維矩陣，適合稠密圖的情況。假設有 ( n ) 個節點，則鄰接矩陣是一個 ( n \times n ) 的矩陣，矩陣中的值表示節點之間是否有連接：

• 如果節點 i 和節點 j 之間有邊，則 matrix[i][j] = 1。
• 如果節點 i 和節點 j 之間沒有邊，則 matrix[i][j] = 0。

實作範例

例如，以下圖包含節點 0、1、2 和 3：

    0 -- 1
    |    |
    2 -- 3

使用鄰接矩陣表示該圖如下：

# 使用鄰接矩陣表示圖
graph_matrix = [
    [0, 1, 1, 0],  # 節點 0 的連接情況
    [1, 0, 0, 1],  # 節點 1 的連接情況
    [1, 0, 0, 1],  # 節點 2 的連接情況
    [0, 1, 1, 0]   # 節點 3 的連接情況
]

# 檢查節點 0 是否與節點 1 相連
print("節點 0 與節點 1 相連:", graph_matrix[0][1] == 1)  # 預期輸出: True

---

2. 鄰接表 (Adjacency List)

鄰接表是更常用的圖表示方式，適合稀疏圖（邊數較少）。它使用字典，每個節點對應一個列表，列表中包含與該節點相連的其他節點。這樣能夠更高效地管理節點之間的關係。

實作範例

使用鄰接表來表示上面的圖：

# 使用鄰接表表示無向圖
graph_list = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# 檢查節點 0 是否與節點 1 相連
print("節點 0 與節點 1 相連:", 1 in graph_list[0])  # 預期輸出: True

---

3. 邊列表 (Edge List)

邊列表是一個邊的列表，每一條邊由一對節點來表示。在無向圖中，兩個節點之間的邊可以表示為 (u, v)，而加權圖則使用三元組 (u, v, weight)。這種方式對加權圖（例如距離圖）特別適用。

實作範例

使用邊列表來表示上面的圖：

# 使用邊列表表示無向圖
graph_edges = [
    (0, 1),
    (0, 2),
    (1, 3),
    (2, 3)
]

# 檢查節點 0 是否與節點 1 相連
is_connected = (0, 1) in graph_edges or (1, 0) in graph_edges
print("節點 0 與節點 1 相連:", is_connected)  # 預期輸出: True

---

常見圖演算法

1. 深度優先搜尋 (DFS)

深度優先搜尋 (DFS) 是一種從起始節點開始，沿著一條路徑深入搜尋的演算法。DFS 使用遞迴，並在搜尋過程中標記已訪問的節點。

實作範例 (使用鄰接表)

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

# 測試 DFS
visited = set()
print("DFS 遍歷順序:", end=" ")
dfs(graph_list, 0, visited)  # 預期輸出: 0 1 3 2

---

2. 廣度優先搜尋 (BFS)

廣度優先搜尋 (BFS) 是一種逐層搜尋的演算法，適合找到最短路徑。BFS 使用佇列 (Queue)，每次將當前節點的所有鄰居加入佇列中，依次處理。

實作範例 (使用鄰接表)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(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
print("\nBFS 遍歷順序:", end=" ")
bfs(graph_list, 0)  # 預期輸出: 0 1 2 3

---

3. Dijkstra 最短路徑演算法

Dijkstra 演算法用於計算加權圖中從起點到其他節點的最短路徑。該演算法適用於非負權重的圖。

加權圖的鄰接表表示

加權圖可以使用鄰接表表示，其中每個節點對應的列表包含 (鄰居, 權重)。

weighted_graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}

Dijkstra 演算法實作

以下為 Dijkstra 演算法的簡單實作：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

# 測試 Dijkstra
print("\nDijkstra 最短路徑:", dijkstra(weighted_graph, 0))  # 預期輸出: {0: 0, 1: 3, 2: 1, 3: 4}

---

總結

• 鄰接矩陣：適合稠密圖，使用二維矩陣來存儲。
• 鄰接表：適合稀疏圖，使用字典和列表表示每個節點的鄰居。
• 邊列表：適合加權圖，特別是在需要排序或過濾邊時。

學習圖的表示方法和常見演算法，對理解圖論非常重要。這些範例展示了如何表示圖結構及進行遍歷，為進一步研究提供基礎。