鄰接表 (Adjacency List)

 鄰接表 (Adjacency List)，這是一種常用的圖數據結構，適合表示節點數不多、邊數稀疏的圖。以下是詳細解釋：

---

鄰接表的結構

1. 定義：

   • 使用字典來表示圖，每個鍵是圖中的節點，每個值是一個子字典，表示從該節點出發的所有邊及其對應的權重。

2. 圖的類型：

   • 該鄰接表描述了一個有向圖，因為邊是有方向的（例如 A -> B 和 A -> C）。
   • 每條邊有一個非負權重（如 A -> B 的權重為 1）。

---

該圖的含義

1. 節點與邊：

   • 節點：A, B, C, D
   • 邊與權重：
     • A -> B，權重為 1
     • A -> C，權重為 4
     • B -> D，權重為 2
     • C -> D，權重為 3

2. 視覺化圖表：

    (A)---1--->(B)
     |           |
     4           2
     v           v
    (C)---3--->(D)

• 节點之间的箭头表示方向，边上的数字表示权重。

---

優點與特性

1. 存儲效率高：

   • 只記錄存在的邊，不記錄不存在的邊，節省存儲空間。
   • 適合稀疏圖（邊數遠小於節點數平方）。

2. 訪問效率：

   • 查找某節點的所有鄰居非常快速，時間複雜度為 (O(k))，其中 (k) 是該節點的邊數。

3. 可擴展性：

   • 添加新節點：只需在字典中新增一個鍵，初始化為空子字典。
   • 添加新邊：只需在相應的子字典中新增鍵值對。

---

每個元素的含義

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'D': 2},
    'C': {'D': 3},
    'D': {}
}

• 'A': {'B': 1, 'C': 4}：

  • 節點 A 連接到 B，權重為 1；
  • 節點 A 連接到 C，權重為 4。

• 'B': {'D': 2}：

  • 節點 B 連接到 D，權重為 2。

• 'C': {'D': 3}：

  • 節點 C 連接到 D，權重為 3。

• 'D': {}：

  • 節點 D 沒有任何出邊（終點節點）。

---

適用場景

1. 加權有向圖：

   • 該表示法特別適合處理加權有向圖，例如最短路徑問題（如 Dijkstra 演算法）。

2. 查詢節點的鄰居：

   • 很容易快速找到某個節點的所有鄰居和相應的權重，例如查詢 A 的鄰居時返回 {'B': 1, 'C': 4}。

3. 動態更新：

   • 動態添加節點或邊非常方便。

---

總結

這種鄰接表表示法：

• 是圖的一種緊湊、靈活的數據結構。
• 適合處理稀疏圖和加權圖。
• 使用 Python 字典作為基礎結構，簡單直觀，適合教學和基礎算法的實現。

這張圖的邏輯非常清晰且適合用於 Dijkstra 等演算法。