图的表示（邻接矩阵/表）

🌐 从树到图——“多对多”的世界

树是”一对多”——一个节点可以有多个子节点，但每个节点只有一个父节点（除了根）。

但现实世界中有很多”多对多”的关系：

• 微信好友——你加了我，我也加了你（双向关系）
• 地铁线路——一个站点连接多个其他站点
• 网页链接——一个网页可以链接到多个其他网页
• 航班网络——一个城市可以直飞多个其他城市

图（Graph） 就是用来表示这种”多对多”关系的数据结构。

🗺️ 类比：大学校园地图

树的类比是”组织架构图”——CEO → 总监 → 经理，层级清晰。

图的类比是”校园地图”——图书馆和食堂之间有一条路，食堂和宿舍之间也有一条路，宿舍和图书馆之间还有一条路。每个建筑（节点）通过道路（边）相连，形成了网络。

---

📐 图的基本概念

图的定义

图由两部分组成：

• 顶点（Vertex / Node）——图中的”点”
• 边（Edge）——图中连接顶点的”线”

图 G = (V, E)
V = {A, B, C, D}       # 顶点集合
E = {(A,B), (B,C), (C,D), (A,D)}  # 边集合

# 简单的图：四个顶点四条边
    A —— B
    |    |
    D —— C

图的分类

类型	说明	例子
无向图（Undirected Graph）	边没有方向，A-B 和 B-A 一样	微信好友、校园道路
有向图（Directed Graph）	边有方向，A→B 不同于 B→A	微博关注、网页链接
无权图（Unweighted Graph）	边只有”存在/不存在”	社交网络（是否有联系）
有权图（Weighted Graph）	边上有权重	地图（距离）、航线（票价）

无向图             有向图              有权图
A —— B            A → B               A ——— B
|    |            ↑    ↓               |  5   |
|    |            C ← D              8 |      | 3
D —— C                                 D ——— C
                                          2

度的概念

• 无向图中的度（Degree）：和某顶点相连的边的数量（A 的度 = 2）
• 有向图中的入度（In-degree）：指向该顶点的边数
• 有向图中的出度（Out-degree）：从该顶点指出的边数

# 有向图中：
# A → B, C → A, D → A
# A 的入度 = 2（C→A, D→A）
# A 的出度 = 1（A→B）

---

🏗️ 两种存储方式

图在计算机中有两种主流存储方式：

方式 1：邻接矩阵（Adjacency Matrix）

用一个 V×V 的二维矩阵表示：matrix[i][j] = 1 表示从 i 到 j 有边。

# 无向图：A-B, A-C, B-D, C-D
# 顶点：0:A, 1:B, 2:C, 3:D

graph = [
    [0, 1, 1, 0],  # A → B, A → C
    [1, 0, 0, 1],  # B → A, B → D
    [1, 0, 0, 1],  # C → A, C → D
    [0, 1, 1, 0],  # D → B, D → C
]
# 注意：无向图的矩阵是对称的

# 有权图：直接在矩阵中存权重
weighted = [
    [0, 5, 8, 0],   # A-B 权重 5, A-C 权重 8
    [5, 0, 0, 3],   # B-D 权重 3
    [8, 0, 0, 2],   # C-D 权重 2
    [0, 3, 2, 0],
]

方式 2：邻接表（Adjacency List）

每个顶点用一个列表（或链表）存储它的邻居。

# 同样的图，用邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}

# 有权图的邻接表——每个邻居带上权重
weighted = {
    'A': [('B', 5), ('C', 8)],
    'B': [('A', 5), ('D', 3)],
    'C': [('A', 8), ('D', 2)],
    'D': [('B', 3), ('C', 2)],
}

---

⚔️ 邻接矩阵 vs 邻接表

操作	邻接矩阵	邻接表
内存	O(V²)	O(V + E)
查边(u, v)是否存在	O(1)	O(degree(u))
遍历顶点 u 的所有邻居	O(V)	O(degree(u))
添加边	O(1)	O(1)
删除边	O(1)	O(degree(u))

什么时候用哪种？

# 场景 1：稠密图（边非常多，接近 V²）→ 邻接矩阵
# 比如：城市之间的直飞航班——几乎每个城市都有直飞
cities = 100
flights = 9000  # 接近 V² = 10000
# 邻接矩阵：100×100 = 10000，够用
# 邻接表：9000 条边，每个顶点的邻居列表也很大

# 场景 2：稀疏图（边比较少，V² >> E）→ 邻接表
# 比如：社交网站——你认识的人远少于全球用户
users = 1_000_000_000
friendships = 200  # 平均每人 200 个好友
# 邻接矩阵：10^18 个元素 → 不可能！
# 邻接表：10^9 × 200 = 2 × 10^11 条边 → 可行

经验法：

边数 E 接近 V² → 用邻接矩阵
边数 E 远小于 V² → 用邻接表

💡 还有一个选择依据：如果你需要频繁查两个顶点之间是否有边（比如”张三和李四是好友吗？”），邻接矩阵的 O(1) 查询很有优势。但如果你要遍历一个顶点的所有邻居（比如”张三的所有好友”），邻接表更高效。

---

🧩 图的常见表示法——示例对比

用三种表示法存储同一个图：

   北京
  /   \
上海---广州

Python 中的三种实现

# 1. 邻接矩阵
graph_matrix = [
    # 北京 上海 广州
    [0,   1,   1],   # 北京
    [1,   0,   1],   # 上海
    [1,   1,   0],   # 广州
]

# 2. 邻接表（字典+列表）
graph_list = {
    '北京': ['上海', '广州'],
    '上海': ['北京', '广州'],
    '广州': ['北京', '上海'],
}

# 3. 邻接表（数组+列表——顶点用数字编号）
# 编号：0=北京, 1=上海, 2=广州
graph_array = [
    [1, 2],  # 北京→上海, 北京→广州
    [0, 2],  # 上海→北京, 上海→广州
    [0, 1],  # 广州→北京, 广州→上海
]

在算法题和实际工程中，邻接表是最常用的表示法（因为大多数图都是稀疏的）。

---

🌍 从图论到现实

图的表示是图算法的”地基”。理解了这个地基，之后学的所有图算法就都是在这些表示法上操作的：

算法	需要什么操作？	适合什么表示？
BFS/DFS	遍历邻居	邻接表（高效遍历）
Dijkstra 最短路径	遍历邻居 + 查权重	邻接表
Floyd 所有点对最短路径	查任意两点的边	邻接矩阵
判断图是否连通	遍历邻居	邻接表

---

📝 小结

概念	一句话
图（Graph）	顶点 + 边——表达”多对多”关系
有向图/无向图	边是否有方向
有权图/无权图	边上是否有权重
度/入度/出度	顶点有多少条边相连
邻接矩阵	V×V 矩阵——查边 O(1)，但占内存多
邻接表	每个顶点存邻居列表——省内存，遍历快
选择原则	稠密图用矩阵，稀疏图用表

🎯 小练习：给你一个社交网络的数据（用户之间的关注关系），你会选择什么方式存储？为什么？（提示：关注关系是有向的，且大多数人关注的人远少于用户总数）

为什么先学这个？ 图的表示是图算法的基础。接下来学习最基本的两种图搜索算法——DFS / BFS。