Python 應用鄰接表實作圖的簡易教材

 

Python 應用鄰接表實作圖的簡易教材

---

目標

1. 了解圖的基本概念與應用場景。
2. 使用鄰接表表示圖的結構。
3. 學習圖的基本操作（如遍歷、最短路徑等）。

---

1. 圖的基本概念

什麼是圖？

• 圖是由節點（Node）和邊（Edge）組成的數據結構。
  • 節點：用來表示物體。
  • 邊：用來表示節點之間的關係。

圖的類型：

1. 無向圖：節點間的邊沒有方向，如好友關係。
2. 有向圖：節點間的邊有方向，如追隨關係。
3. 加權圖：邊有數值權重，如距離或成本。

---

2. 使用鄰接表表示圖

鄰接表是用字典表示圖的方法，節點的鄰居存儲在列表中。

無向圖：

# 用字典表示圖
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2]
}

# 範例：節點 1 連接節點 2 和節點 3
print(graph)

輸入建構無向圖：

from collections import defaultdict

graph = defaultdict(list)
n = int(input("輸入節點數量: "))
for _ in range(n - 1):
    a, b = map(int, input("輸入一條邊: ").split())
    graph[a].append(b)
    graph[b].append(a)

print("鄰接表：", dict(graph))

---

3. 圖的基本操作

操作 1：深度優先搜尋（DFS）

DFS 是什麼？

• 深度優先搜尋是沿著一條路徑一直走到底，然後回頭找其他路徑。

DFS 實作：

def dfs(node, graph, visited):
    print(node, end=" ")  # 訪問節點
    visited.add(node)  # 標記為已訪問
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)

# 測試
visited = set()
dfs(1, graph, visited)  # 從節點 1 開始

範例輸入：

4
1 2
1 3
2 4

範例輸出：

1 2 4 3

---

操作 2：廣度優先搜尋（BFS）

BFS 是什麼？

• 廣度優先搜尋是先訪問所有相鄰節點，再逐層深入。

BFS 實作：

from collections import deque

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

# 測試
bfs(1, graph)

範例輸出：

1 2 3 4

---

操作 3：判斷是否連通

問題描述：

• 圖是否為連通圖（所有節點是否都能到達）？

解法：使用 DFS：

def is_connected(graph, n):
    visited = set()
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(1)  # 從任意節點開始
    return len(visited) == n  # 是否訪問了所有節點

# 測試
print("圖是否連通：", is_connected(graph, n))

範例輸出：

圖是否連通： True

---

操作 4：尋找最短路徑

無權圖中的最短路徑：

• 使用 BFS 找到從起點到終點的最短路徑長度。

實作：

def shortest_path(graph, start, end):
    from collections import deque
    q = deque([(start, 0)])  # (節點, 路徑長度)
    visited = set()
    visited.add(start)

    while q:
        node, dist = q.popleft()
        if node == end:
            return dist  # 找到目標
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append((neighbor, dist + 1))
    return -1  # 無法到達

# 測試
print("最短路徑長度：", shortest_path(graph, 1, 4))

範例輸出：

最短路徑長度： 2

---

4. 綜合應用：圖的問題解決

應用 1：找到所有連通分量

連通分量是互相連通的一組節點。

實作：

def connected_components(graph, n):
    visited = set()
    components = []

    def dfs(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, component)

    for node in range(1, n + 1):
        if node not in visited:
            component = []
            dfs(node, component)
            components.append(component)
    return components

# 測試
print("圖的連通分量：", connected_components(graph, n))

範例輸出：

圖的連通分量： [[1, 2, 4, 3]]

---

總結

1. 使用鄰接表表示圖：節省空間，結構清晰。
2. 掌握遍歷方法：DFS 和 BFS 是解決圖問題的基礎。
3. 圖的基本操作：
   • 判斷連通性。
   • 找最短路徑。
   • 計算連通分量。
4. 實用性強：這些操作能解決地圖導航、社交網絡等實際問題。