圖形理論基礎與 NetworkX 入門

什麼是圖形 (Graph)？

圖形是電腦科學中最強大的資料結構之一。它由兩個部分組成：

節點 (Node / Vertex)：代表實體（城市、人物、網頁）
邊 (Edge)：代表節點之間的關係（道路、友誼、超連結）

生活中的圖形範例

| 場景 | 節點 | 邊 | |------|------|-----| | 地圖導航 | 路口/城市 | 道路 | | 社交網路 | 人物 | 好友關係 | | 網路路由 | 伺服器 | 網路線 | | 推薦系統 | 使用者/商品 | 購買行為 |

圖形的種類

有向圖 (Directed Graph)：邊有方向（例如：Instagram 追蹤關係）
無向圖 (Undirected Graph)：邊無方向（例如：Facebook 好友）
加權圖 (Weighted Graph)：邊有權重（例如：道路長度、交通時間）
連通圖 vs 非連通圖：所有節點是否都能互相到達

安裝 NetworkX

pip install networkx matplotlib numpy

NetworkX 快速入門

NetworkX 是 Python 中最流行的圖形分析函式庫，由美國能源部 Los Alamos 國家實驗室開發。

建立你的第一個圖形

import networkx as nx
import matplotlib.pyplot as plt

# 建立一個空的無向圖
G = nx.Graph()

# 加入節點
G.add_node("台北")
G.add_node("台中")
G.add_node("高雄")
G.add_node("花蓮")

# 加入邊（包含權重：距離公里數）
G.add_edge("台北", "台中", weight=180)
G.add_edge("台中", "高雄", weight=200)
G.add_edge("台北", "花蓮", weight=120)
G.add_edge("台中", "花蓮", weight=150)
G.add_edge("高雄", "花蓮", weight=300)

# 畫出圖形
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, with_labels=True, node_color='lightblue',
        node_size=1500, font_size=12, font_weight='bold')

# 在邊上顯示權重
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

plt.title("台灣主要城市路線圖")
plt.show()

圖形的基本分析

# === 圖形基本資訊 ===
print(f"節點數量: {G.number_of_nodes()}")
print(f"邊數量: {G.number_of_edges()}")

# === 鄰居與度數 ===
print(f"\n台北的鄰居: {list(G.neighbors('台北'))}")
print(f"台中的度數 (連接數量): {G.degree('台中')}")

# === 最短路徑 ===
print(f"\n台北到高雄的最短路徑: {nx.shortest_path(G, '台北', '高雄', weight='weight')}")
print(f"台北到高雄的最短距離: {nx.shortest_path_length(G, '台北', '高雄', weight='weight')} km")

# === 所有節點對的最短路徑 ===
print("\n所有城市間的最短距離：")
for source in G.nodes():
    for target in G.nodes():
        if source < target:
            dist = nx.shortest_path_length(G, source, target, weight='weight')
            print(f"  {source} → {target}: {dist} km")

隨機圖形生成與分析

# 生成隨機圖形（Erdos-Renyi 模型）
random_G = nx.erdos_renyi_graph(n=20, p=0.15, seed=42)

print(f"隨機圖形: {random_G.number_of_nodes()} 節點, {random_G.number_of_edges()} 邊")

# 檢查連通性
print(f"是否連通: {nx.is_connected(random_G)}")

# 找出所有連通分量
components = list(nx.connected_components(random_G))
print(f"連通分量數量: {len(components)}")
for i, comp in enumerate(components):
    print(f"  分量 {i+1}: {len(comp)} 個節點")

# 計算中心性 (Centrality) — 找出最重要的節點
degree_centrality = nx.degree_centrality(random_G)
betweenness_centrality = nx.betweenness_centrality(random_G)

# 找出度數中心性最高的節點
most_important = max(degree_centrality, key=degree_centrality.get)
print(f"\n度數中心性最高的節點: {most_important} ({degree_centrality[most_important]:.3f})")

# 畫圖
pos = nx.spring_layout(random_G, seed=42)
plt.figure(figsize=(10, 8))

# 根據度數中心性調整節點大小
sizes = [degree_centrality[n] * 2000 + 200 for n in random_G.nodes()]

nx.draw(random_G, pos, with_labels=True, node_color='lightgreen',
        node_size=sizes, font_size=10)
plt.title("隨機圖形（節點大小 = 度數中心性）")
plt.show()

實戰：建立台灣高鐵路線圖

# === 建立台灣高鐵站點圖形 ===
hsr = nx.Graph()

# 高鐵站點（依序）
stations = ["南港", "台北", "板橋", "桃園", "新竹", "苗栗", "台中", "彰化", "雲林", "嘉義", "台南", "左營"]

# 加入所有站點
for s in stations:
    hsr.add_node(s)

# 加入相鄰站點之間的距離（公里）與行駛時間（分鐘）
distances = [
    ("南港", "台北", 4, 3),
    ("台北", "板橋", 7, 4),
    ("板橋", "桃園", 34, 12),
    ("桃園", "新竹", 39, 13),
    ("新竹", "苗栗", 33, 11),
    ("苗栗", "台中", 52, 17),
    ("台中", "彰化", 17, 7),
    ("彰化", "雲林", 25, 10),
    ("雲林", "嘉義", 20, 8),
    ("嘉義", "台南", 65, 19),
    ("台南", "左營", 40, 13),
]

for s1, s2, dist, time in distances:
    hsr.add_edge(s1, s2, distance=dist, time=time)

# 查詢台北到左營的最快路線（最少時間）
path = nx.shortest_path(hsr, "台北", "左營", weight='time')
path_length = nx.shortest_path_length(hsr, "台北", "左營", weight='time')
print(f"台北→左營最快路線: {' → '.join(path)}")
print(f"總行駛時間: {path_length} 分鐘")

# 查詢最短距離路線
shortest_path_by_dist = nx.shortest_path(hsr, "台北", "左營", weight='distance')
dist = nx.shortest_path_length(hsr, "台北", "左營", weight='distance')
print(f"\n台北→左營最短距離: {dist} 公里")
print(f"路線: {' → '.join(shortest_path_by_dist)}")

# 視覺化
pos = {s: (i, 0) for i, s in enumerate(stations)}  # 直線排列
plt.figure(figsize=(14, 4))
nx.draw(hsr, pos, with_labels=True, node_color='orange',
        node_size=2000, font_size=10, font_weight='bold',
        edge_color='gray', width=2)

# 顯示距離標籤
dist_labels = {(s1, s2): f"{d}km" for s1, s2, d, _ in distances}
nx.draw_networkx_edge_labels(hsr, pos, edge_labels=dist_labels, font_size=8)

plt.title("台灣高鐵路線圖（距離與時間）")
plt.axis('off')
plt.tight_layout()
plt.show()

使用 Vibe Coding 建立圖形

🔥 【圖形分析詠唱範例】 「請幫我分析一個社交網路圖形： 1. 建立一個隨機圖形（50 個節點，連線機率 0.08）。 2. 計算每個節點的度數中心性與中介中心性。 3. 找出最重要的 5 個節點（根據度數中心性）。 4. 用顏色深淺表示中心性高低來畫圖。 5. 輸出圖形的直徑（最遠最短路徑長度）。 6. 檢查圖形是否為「小世界網路」(Small-world)。」

本日總結

在本章中，你學到了：

✅ 圖形的基本概念：節點、邊、有向/無向、加權圖
✅ NetworkX 入門：建立圖形、加入節點與邊
✅ 圖形分析：最短路徑、度數、中心性、連通分量
✅ 真實資料實戰：建立台灣高鐵路線圖
✅ 視覺化：用 Matplotlib 畫出圖形

下一章，我們將深入最經典的圖形搜尋演算法：BFS 與 DFS！