D1: 冥王星星際網絡：圖論與搜索演算法
任務背景
恭喜！你已經抵達太陽系的邊界——冥王星區域。這裡有複雜的星際航道網絡，連接著各個太空站和小行星帶。要在這個網絡中找到最佳路徑，你需要掌握「圖論」——電腦科學中最強大的工具之一。
圖可以表示任何「物件之間的關係」：- 太空站之間的航道
- 社交網絡中的朋友關係
- 網頁之間的超連結
- 城市之間的道路
知識點說明
什麼是圖（Graph）？
圖由兩部分組成：- 頂點（Vertices/Nodes）：物件本身
- 邊（Edges）：物件之間的連接
A --- B
| |
C --- D
圖的類型
- 無向圖 vs 有向圖
- 無向圖：邊沒有方向（雙向道路）
- 有向圖：邊有方向（單行道）
- 加權圖 vs 無權圖
- 無權圖：所有邊的「成本」相同
- 加權圖：每條邊有不同的權重（距離、時間等）
圖的表示法
1. 鄰接矩陣（Adjacency Matrix）# 適合稠密圖，查詢快但佔空間
graph = [[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]]
# 適合稀疏圖，節省空間
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
圖的遍歷
廣度優先搜尋（BFS）：一層一層探索- 使用佇列（Queue）
- 找最短路徑（無權圖）
- 使用堆疊（Stack）或遞迴
- 探索所有路徑
範例程式碼
範例 1：建立星際航道網絡
import sys
from collections import defaultdict
# 任務：建立太空站網絡
n = int(sys.stdin.readline()) # 太空站數量
m = int(sys.stdin.readline()) # 航道數量
# 使用鄰接串列
graph = defaultdict(list)
print("建立航道：")
for _ in range(m):
a, b = map(int, sys.stdin.readline().strip().split())
graph[a].append(b)
graph[b].append(a) # 無向圖
print(f"太空站 {a} ↔ 太空站 {b}")
print("\n網絡結構：")
for station in sorted(graph.keys()):
neighbors = sorted(graph[station])
print(f"太空站 {station}: 連接到 {neighbors}")
範例 2：BFS - 最短路徑搜索
import sys
from collections import deque, defaultdict
def bfs_shortest_path(graph, start, end):
"""使用 BFS 找出最短路徑"""
if start == end:
return [start]
# 佇列：儲存 (當前節點, 路徑)
queue = deque([(start, [start])])
visited = {start}
while queue:
current, path = queue.popleft()
# 探索所有鄰居
for neighbor in graph[current]:
if neighbor in visited:
continue
new_path = path + [neighbor]
# 找到目標
if neighbor == end:
return new_path
visited.add(neighbor)
queue.append((neighbor, new_path))
return None # 無法到達
# 任務：找出從地球到冥王星的最短航道
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = defaultdict(list)
for _ in range(m):
a, b = map(int, sys.stdin.readline().strip().split())
graph[a].append(b)
graph[b].append(a)
start = int(sys.stdin.readline())
end = int(sys.stdin.readline())
path = bfs_shortest_path(graph, start, end)
if path:
print(f"最短路徑：{' → '.join(map(str, path))}")
print(f"需要經過 {len(path) - 1} 個航道")
else:
print("無法到達目標！")
範例 3：DFS - 探索所有路徑
import sys
from collections import defaultdict
def dfs_all_paths(graph, start, end, path=[]):
"""使用 DFS 找出所有路徑"""
path = path + [start]
# 到達目標
if start == end:
return [path]
# 沒有鄰居
if start not in graph:
return []
paths = []
for neighbor in graph[start]:
# 避免循環
if neighbor not in path:
new_paths = dfs_all_paths(graph, neighbor, end, path)
paths.extend(new_paths)
return paths
# 任務：找出所有可能的探索路線
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = defaultdict(list)
for _ in range(m):
a, b = map(int, sys.stdin.readline().strip().split())
graph[a].append(b)
graph[b].append(a)
start = int(sys.stdin.readline())
end = int(sys.stdin.readline())
all_paths = dfs_all_paths(graph, start, end)
print(f"找到 {len(all_paths)} 條路徑：\n")
for i, path in enumerate(all_paths, 1):
print(f"路徑 {i}: {' → '.join(map(str, path))}")
範例 4：迷宮探索（網格圖）
import sys
from collections import deque
def maze_bfs(maze, start, end):
"""在迷宮中找最短路徑"""
rows = len(maze)
cols = len(maze[0])
# 四個方向：上下左右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
direction_names = ['上', '下', '左', '右']
queue = deque([(start, [start])])
visited = {start}
while queue:
(r, c), path = queue.popleft()
# 到達終點
if (r, c) == end:
return path
# 探索四個方向
for (dr, dc), name in zip(directions, direction_names):
nr, nc = r + dr, c + dc
# 檢查邊界
if 0 <= nr < rows and 0 <= nc < cols:
# 檢查是否可通行且未訪問
if maze[nr][nc] != '#' and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append(((nr, nc), path + [(nr, nc)]))
return None
# 任務：在小行星帶中找到安全路徑
# '.' = 安全區域, '#' = 隕石, 'S' = 起點, 'E' = 終點
rows = int(sys.stdin.readline())
cols = int(sys.stdin.readline())
maze = []
start = end = None
for i in range(rows):
row = list(sys.stdin.readline().strip())
maze.append(row)
for j in range(cols):
if row[j] == 'S':
start = (i, j)
maze[i][j] = '.'
elif row[j] == 'E':
end = (i, j)
maze[i][j] = '.'
path = maze_bfs(maze, start, end)
if path:
print(f"找到安全路徑！長度：{len(path)}")
print("\n迷宮（標記路徑）：")
# 標記路徑
for r, c in path:
if (r, c) != start and (r, c) != end:
maze[r][c] = '*'
maze[start[0]][start[1]] = 'S'
maze[end[0]][end[1]] = 'E'
for row in maze:
print(''.join(row))
else:
print("無法找到安全路徑！")
範例 5：連通分量檢測
import sys
from collections import defaultdict
def find_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(sorted(component))
return components
# 任務：識別獨立的星系群
n = int(sys.stdin.readline()) # 太空站數量
m = int(sys.stdin.readline()) # 航道數量
graph = defaultdict(list)
for _ in range(m):
a, b = map(int, sys.stdin.readline().strip().split())
graph[a].append(b)
graph[b].append(a)
components = find_connected_components(graph, n)
print(f"發現 {len(components)} 個獨立星系群：\n")
for i, comp in enumerate(components, 1):
print(f"星系群 {i}: {comp}")
print(f" 包含 {len(comp)} 個太空站")
程式碼解說
關鍵技術點
- BFS vs DFS 的選擇
- visited 集合的重要性
visited = set() # 防止重複訪問
# 在有環的圖中，沒有 visited 會無限循環！
- 網格圖的技巧
# 四個方向的移動
directions = [(-1,0), (1,0), (0,-1), (0,1)]
for dr, dc in directions:
new_r, new_c = r + dr, c + dc
# 檢查邊界
if 0 <= new_r < rows and 0 <= new_c < cols:
# 處理
- defaultdict 的妙用
from collections import defaultdict
# 自動創建空列表
graph = defaultdict(list)
graph[1].append(2) # 不需要先初始化 graph[1]
Quiz: 星際救援任務
題目：多目標最短路徑
你的太空船在太空站 S，需要救援位於太空站 T1 和 T2 的兩組太空人，然後返回基地 E。
請找出一條路徑，使得總航道數最少。你可以選擇先救援 T1 或 T2。
輸入格式：- 第一行：N M（太空站數量，航道數量）
- 接下來 M 行：每行兩個整數 a b，表示太空站 a 和 b 之間有航道
- 最後一行：S T1 T2 E（起點、兩個救援點、終點）
6 7
1 2
1 3
2 4
3 4
4 5
4 6
5 6
1 2 5 6
最佳路徑：1 → 2 → 4 → 5 → 4 → 6
總航道數：5
救援順序：
- 從起點 1 到救援點 2
- 從救援點 2 到救援點 5
- 從救援點 5 到終點 6
💡 提示
- 使用 BFS 計算任意兩點間的最短距離
- 比較兩種順序：S→T1→T2→E 和 S→T2→T1→E
- 選擇總距離較短的路徑
---
Quiz 解答
import sys
from collections import deque, defaultdict
def bfs_distance(graph, start, end):
"""計算從 start 到 end 的最短距離"""
if start == end:
return 0, [start]
queue = deque([(start, [start])])
visited = {start}
while queue:
current, path = queue.popleft()
for neighbor in graph[current]:
if neighbor in visited:
continue
new_path = path + [neighbor]
if neighbor == end:
return len(new_path) - 1, new_path
visited.add(neighbor)
queue.append((neighbor, new_path))
return float('inf'), []
# 讀取輸入
n, m = map(int, sys.stdin.readline().strip().split())
graph = defaultdict(list)
for _ in range(m):
a, b = map(int, sys.stdin.readline().strip().split())
graph[a].append(b)
graph[b].append(a)
S, T1, T2, E = map(int, sys.stdin.readline().strip().split())
# 計算所有需要的距離
dist_S_T1, path_S_T1 = bfs_distance(graph, S, T1)
dist_S_T2, path_S_T2 = bfs_distance(graph, S, T2)
dist_T1_T2, path_T1_T2 = bfs_distance(graph, T1, T2)
dist_T2_T1, path_T2_T1 = bfs_distance(graph, T2, T1)
dist_T1_E, path_T1_E = bfs_distance(graph, T1, E)
dist_T2_E, path_T2_E = bfs_distance(graph, T2, E)
# 方案 1：S → T1 → T2 → E
route1_dist = dist_S_T1 + dist_T1_T2 + dist_T2_E
route1_path = path_S_T1[:-1] + path_T1_T2[:-1] + path_T2_E
# 方案 2：S → T2 → T1 → E
route2_dist = dist_S_T2 + dist_T2_T1 + dist_T1_E
route2_path = path_S_T2[:-1] + path_T2_T1[:-1] + path_T1_E
# 選擇較短的路徑
if route1_dist <= route2_dist:
best_path = route1_path
best_dist = route1_dist
order = [T1, T2]
else:
best_path = route2_path
best_dist = route2_dist
order = [T2, T1]
print(f"最佳路徑：{' → '.join(map(str, best_path))}")
print(f"總航道數：{best_dist}")
print(f"\n救援順序：")
print(f"1. 從起點 {S} 到救援點 {order[0]}")
print(f"2. 從救援點 {order[0]} 到救援點 {order[1]}")
print(f"3. 從救援點 {order[1]} 到終點 {E}")
解答說明
- 分段計算
- 將問題分解為多個兩點間最短路徑
- 使用 BFS 計算每段距離
- 比較兩種方案
# 方案 1：S → T1 → T2 → E
# 方案 2：S → T2 → T1 → E
# 選擇總距離較短的
- 路徑拼接
# 注意：拼接時要去掉中間節點的重複
path_S_T1[:-1] + path_T1_T2[:-1] + path_T2_E
---
訓練完成！
恭喜你完成 星際網絡與圖論 訓練！