-
第12章 图结构
第12章 图结构
12.1 引言
在数据结构的学习中，线性结构（数组、链表）处理“一对一”关系，树形结构（二叉树、堆）处理“一对多”关系，但现实世界中存在大量“多对多”关系：社交网络中用户间的相互关注、地图中城市间的道路连接、电路中元件引脚的连接关系等。这些关系无法用线性或树形结构准确描述，需要一种更通用的数据结构——图（Graph）。
图由顶点（Vertex） 和边（Edge） 组成，顶点代表实体，边代表实体间的关系。其核心价值在于灵活描述多对多连接，是解决网络分析、路径规划、依赖调度等复杂问题的基础。本章将从图的定义出发，系统讲解图的分类、存储方式、遍历算法及工程应用，结合Python实现，帮助读者建立“图论思维”，掌握处理复杂连接问题的方法。
12.2 图的基本概念
12.2.1 图的定义
定义12.1 图（Graph）：由顶点集 V V V 和边集 E E E 组成的二元组，记为 G=(V,E) G=(V,E) G=(V,E)。其中：
顶点（Vertex）：集合 V V V 中的元素，是图的基本组成单元，通常用字母或数字标识（如 v0,v1 v_0, v_1 v0,v1 或 A,B A, B A,B）；
边（Edge）：集合 E E E 中的元素，是顶点间关系的抽象，用顶点对表示（如 (u,v) (u,v) (u,v) 表示连接 u u u 和 v v v 的边）。
12.2.2 图的分类
-
按边的方向分类
无向图（Undirected Graph）：边无方向，(u,v) (u,v) (u,v) 与 (v,u) (v,u) (v,u) 表示同一条边。
示例：社交网络中的“好友关系”（若A是B的好友，则B必是A的好友）。
有向图（Directed Graph）：边有方向，(u,v) (u,v) (u,v) 称为“弧”，表示从 u u u 到 v v v 的单向连接，u u u 为起点，v v v 为终点。
示例：微博中的“关注关系”（A关注B不代表B关注A）。 -
按边的权重分类
无权图（Unweighted Graph）：边仅表示“是否连接”，无附加信息。
示例：判断两个城市是否有道路相通。
带权图（Weighted Graph）：边关联一个数值（权重），表示连接的代价、距离或强度。
示例：地图中道路的长度（权重为距离）、网络中链路的带宽（权重为传输速率）。 -
特殊图结构
图类型 定义 示例场景
完全图 任意两顶点间均有边连接（无向完全图有 n(n−1)/2 n(n-1)/2 n(n−1)/2 条边，n n n 为顶点数） 稠密网络（如小型局域网）
连通图 无向图中任意两顶点间存在路径（边组成的序列） 城市道路网（任意两城市可达）
有向无环图 有向图中不存在从顶点出发回到自身的路径（无环） 任务调度（任务间无循环依赖）
12.2.3 基本术语
度（Degree）：无向图中，顶点的度是与该顶点相连的边数；有向图中，分为入度（指向该顶点的边数）和出度（从该顶点出发的边数）。
路径（Path）：从顶点 u u u 到 v v v 的顶点序列 [u,v1,v2,...,v] [u, v_1, v_2, ..., v] [u,v1,v2,...,v]，相邻顶点间有边连接，路径长度为边数。
环（Cycle）：起点与终点相同的路径（如无向图中 u−v−w−u u-v-w-u u−v−w−u）。
连通分量：无向图中极大连通子图（无法添加更多顶点仍保持连通）。
12.2.4 图的抽象表示
用图形直观描述图结构：顶点用圆圈表示，边用线段（无向）或箭头（有向）表示。
无向无权图示例：
v0 --- v1
| |
| |
v2 --- v3
顶点集 V={v0,v1,v2,v3} V={v0,v1,v2,v3} V={v0,v1,v2,v3}，边集 E={(v0,v1),(v0,v2),(v1,v3),(v2,v3)} E={(v0,v1),(v0,v2),(v1,v3),(v2,v3)} E={(v0,v1),(v0,v2),(v1,v3),(v2,v3)}。
有向带权图示例：
v0 -> v1 (2)
^ |
| v
v2 <- v3 (5)
顶点集 V={v0,v1,v2,v3} V={v0,v1,v2,v3} V={v0,v1,v2,v3}，边集 E={(v0,v1,2),(v1,v3,5),(v3,v2,1),(v2,v0,3)} E={(v0,v1,2),(v1,v3,5),(v3,v2,1),(v2,v0,3)} E={(v0,v1,2),(v1,v3,5),(v3,v2,1),(v2,v0,3)}（括号内为权重）。
12.3 图的存储方式
图的存储需高效表示顶点间的连接关系，核心需求是：判断两顶点是否有边、快速获取顶点的邻接顶点。主流存储方式有邻接矩阵和邻接表。
12.3.1 邻接矩阵（Adjacency Matrix）
-
基本原理
用 n×n n imes n n×n 的二维数组 A A A 存储图（n n n 为顶点数），数组元素 A[i][j] A[i][j] A[i][j] 表示顶点 i i i 和 j j j 的连接关系：
无权图：A[i][j]=1 A[i][j] = 1 A[i][j]=1（有边），A[i][j]=0 A[i][j] = 0 A[i][j]=0（无边）；
带权图：A[i][j]=权重 A[i][j] = ext{权重} A[i][j]=权重（有边），A[i][j]=∞ A[i][j] = infty A[i][j]=∞（无边，通常用一个极大值如 109 10^{9} 109 表示）；
无向图：矩阵对称（A[i][j]=A[j][i] A[i][j] = A[j][i] A[i][j]=A[j][i]）；
有向图：矩阵不对称（A[i][j] A[i][j] A[i][j] 仅表示从 i i i 到 j j j 的边）。 -
示例
无向无权图的邻接矩阵（顶点数 n=4 n=4 n=4，顶点编号 0∼3 0 sim 3 0∼3）：
A=[0110100110010110] A = egin{bmatrix} 0 & 1 & 1 & 0 1 & 0 & 0 & 1 1 & 0 & 0 & 1 0 & 1 & 1 & 0 end{bmatrix} A=0110100110010110
（行/列对应顶点0~3，1表示有边，0表示无边）。 -
优缺点
优点 缺点
判断两顶点是否有边：O(1)（直接访问 A[i][j] A[i][j] A[i][j]） 空间复杂度 O(n2) O(n^2) O(n2)，顶点数多时浪费空间（如稀疏图）
实现简单，适合稠密图（边数接近完全图） 获取顶点的邻接顶点需遍历一行，时间复杂度 O(n) O(n) O(n)
12.3.2 邻接表（Adjacency List） -
基本原理
用数组（或字典）存储每个顶点的邻接顶点列表：数组下标（或字典的键）为顶点编号，列表存储与该顶点相连的顶点（及权重，若带权）。
无权图：邻接表存储邻接顶点编号；
带权图：邻接表存储 (邻接顶点编号,权重) ( ext{邻接顶点编号}, ext{权重}) (邻接顶点编号,权重) 元组；
无向图：每条边在两顶点的邻接表中各存一次；
有向图：仅在起点的邻接表中存储有向边。 -
示例
无向无权图的邻接表（同上例顶点0~3）：
python
adj_list = [
[1, 2], # 顶点0的邻接顶点：1, 2
[0, 3], # 顶点1的邻接顶点：0, 3
[0, 3], # 顶点2的邻接顶点：0, 3
[1, 2] # 顶点3的邻接顶点：1, 2
]
有向带权图的邻接表（边集 {(0,1,2),(1,3,5),(3,2,1),(2,0,3)} {(0,1,2),(1,3,5),(3,2,1),(2,0,3)} {(0,1,2),(1,3,5),(3,2,1),(2,0,3)}）：
python
adj_list = [
[(1, 2)], # 顶点0的出边：(1, 2)（到顶点1，权重2）
[(3, 5)], # 顶点1的出边：(3, 5)
[(0, 3)], # 顶点2的出边：(0, 3)
[(2, 1)] # 顶点3的出边：(2, 1)
]
-
优缺点
优点 缺点
空间复杂度 O(n+m) O(n + m) O(n+m)（m m m 为边数），适合稀疏图 判断两顶点是否有边需遍历邻接列表，时间复杂度 O(k) O(k) O(k)（k k k 为邻接顶点数）
获取顶点的邻接顶点仅需遍历列表，时间复杂度 O(k) O(k) O(k) 实现较邻接矩阵复杂（需维护动态列表）
12.3.3 存储方式选择
| 场景 | 推荐存储方式 | 理由 |
|---|---|---|
| 稠密图（边数接近 n2 n^2 n2） | 邻接矩阵 | 空间浪费少，边判断效率高（O(1)） |
| 稀疏图（边数远小于 n2 n^2 n2） | 邻接表 | 空间效率高（O(n+m)），邻接顶点访问快 |
| 需频繁判断两顶点是否有边 | 邻接矩阵 | 直接访问数组元素，避免遍历列表 |
| 需频繁获取顶点的邻接顶点 | 邻接表 | 直接返回邻接列表，无需遍历无关顶点（邻接矩阵需遍历一行） |
12.4 图的Python实现（基于邻接表）
邻接表在稀疏图中空间效率更高，工程中应用广泛。以下实现一个支持无向/有向、无权/带权的通用图类。
12.4.1 图类定义
python
class Graph:
def __init__(self, directed=False, weighted=False):
"""初始化图
:param directed: 是否为有向图（默认无向）
:param weighted: 是否为带权图（默认无权）
"""
self.directed = directed # 图类型（有向/无向）
self.weighted = weighted # 边类型（带权/无权）
self.vertices = set() # 顶点集（存储所有顶点）
self.adj_list = {} # 邻接表：{顶点: 邻接列表}
def add_vertex(self, v):
"""添加顶点v（若已存在则不操作）"""
if v in self.vertices:
return
self.vertices.add(v)
self.adj_list[v] = [] # 初始化邻接列表
def add_edge(self, u, v, weight=None):
"""添加边（u, v），带权图需指定weight"""
# 确保顶点u、v存在
if u not in self.vertices:
self.add_vertex(u)
if v not in self.vertices:
self.add_vertex(v)
# 带权图必须提供权重
if self.weighted and weight is None:
raise ValueError("Weighted graph requires 'weight' for edges")
# 添加边到邻接表
if self.weighted:
self.adj_list[u].append((v, weight)) # 带权图存储元组 (v, weight)
else:
self.adj_list[u].append(v) # 无权图存储顶点v
# 无向图需添加反向边
if not self.directed:
if self.weighted:
self.adj_list[v].append((u, weight))
else:
self.adj_list[v].append(u)
def get_neighbors(self, v):
"""获取顶点v的邻接顶点（带权图返回 (邻接顶点, 权重) 元组）"""
if v not in self.vertices:
raise ValueError(f"Vertex {v} not in graph")
return self.adj_list[v]
def __str__(self):
"""返回图的邻接表表示"""
res = []
for v in sorted(self.vertices): # 按顶点顺序输出
neighbors = self.adj_list[v]
res.append(f"{v}: {neighbors}")
return "Graph Adjacency List:
" + "
".join(res)
12.4.2 使用示例
-
无向无权图
python
# 创建无向无权图
g = Graph(directed=False, weighted=False)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print(g)
输出：
Graph Adjacency List:
0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]
-
有向带权图
python
# 创建有向带权图
g = Graph(directed=True, weighted=True)
g.add_edge(0, 1, weight=2)
g.add_edge(1, 3, weight=5)
g.add_edge(3, 2, weight=1)
g.add_edge(2, 0, weight=3)
print(g)
输出：
Graph Adjacency List:
0: [(1, 2)]
1: [(3, 5)]
2: [(0, 3)]
3: [(2, 1)]
12.5 图的遍历算法
图的遍历是按规则访问所有顶点（每个顶点仅访问一次），核心算法有深度优先搜索（DFS） 和广度优先搜索（BFS），是解决路径查找、环检测等问题的基础。
12.5.1 深度优先搜索（DFS）
-
基本思想
从起点出发，沿一条路径尽可能深入访问（“一条路走到黑”），直至无法继续（无未访问邻接顶点），再回溯到上一顶点，选择新路径继续，直至所有顶点访问完毕。 -
实现方法
递归法（利用函数栈实现回溯）：
1.访问顶点 v v v，标记为已访问；
2.递归访问 v v v 的所有未访问邻接顶点。
迭代法（用显式栈存储待访问顶点）：
1.初始化栈，压入起点；
2.弹出栈顶顶点 v v v，若未访问则标记并记录；
3.将 v v v 的未访问邻接顶点压入栈（逆序压入，保证访问顺序与递归一致）；
4.重复步骤2~3直至栈空。 -
代码实现（无向无权图）
python
def dfs_recursive(graph, v, visited=None):
"""深度优先搜索（递归版），返回遍历序列"""
if visited is None:
visited = set() # 记录已访问顶点
visited.add(v)
traversal = [v] # 遍历序列（从v开始）
# 递归访问所有未访问的邻接顶点
for neighbor in graph.get_neighbors(v):
if neighbor not in visited:
traversal.extend(dfs_recursive(graph, neighbor, visited))
return traversal
def dfs_iterative(graph, start):
"""深度优先搜索（迭代版，用栈），返回遍历序列"""
visited = set()
stack = [start] # 栈存储待访问顶点
traversal = []
while stack:
v = stack.pop() # 弹出栈顶顶点
if v not in visited:
visited.add(v)
traversal.append(v)
# 逆序添加邻接顶点（保证与递归版遍历顺序一致）
neighbors = graph.get_neighbors(v)
for neighbor in reversed(neighbors):
if neighbor not in visited:
stack.append(neighbor)
return traversal
-
示例
对无向无权图 0−1−3−2−0 0-1-3-2-0 0−1−3−2−0（顶点0连接1、2；1连接0、3；2连接0、3；3连接1、2），从顶点0出发的DFS遍历序列为 [0,1,3,2] [0, 1, 3, 2] [0,1,3,2]（递归/迭代结果一致）。
12.5.2 广度优先搜索（BFS） -
基本思想
从起点出发，按“层次”访问顶点：先访问起点（第0层），再访问其所有邻接顶点（第1层），然后访问邻接顶点的邻接顶点（第2层），以此类推，直至所有顶点访问完毕。 -
实现方法
用队列存储待访问顶点：
1.初始化队列，入队起点；
2.出队顶点 v v v，若未访问则标记并记录；
3.将 v v v 的未访问邻接顶点入队；
4.重复步骤2~3直至队空。 -
代码实现（无向无权图）
python
from collections import deque
def bfs(graph, start):
"""广度优先搜索（用队列），返回遍历序列"""
visited = set()
queue = deque([start]) # 队列存储待访问顶点（用deque提高popleft效率）
traversal = []
while queue:
v = queue.popleft() # 出队（先进先出）
if v not in visited:
visited.add(v)
traversal.append(v)
# 添加未访问的邻接顶点到队列
for neighbor in graph.get_neighbors(v):
if neighbor not in visited:
queue.append(neighbor)
return traversal
-
示例
对上述无向无权图，从顶点0出发的BFS遍历序列为 [0,1,2,3] [0, 1, 2, 3] [0,1,2,3]（先访问第0层顶点0，再访问第1层顶点1、2，最后访问第2层顶点3）。
12.5.3 DFS与BFS对比
| 特性 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归/显式栈） | 队列 |
| 访问顺序 | 深度优先（一条路走到黑） | 广度优先（逐层扩散） |
| 空间复杂度 | O(h) O(h) O(h)（h h h 为图的深度） | O(w) O(w) O(w)（w w w 为图的宽度） |
| 适用场景 | 路径查找、拓扑排序、连通分量 | 最短路径（无权图）、层次遍历 |
12.5 工程应用
12.5.1 无权图最短路径（BFS）
问题：在无权图中，求从起点到其他所有顶点的最短路径（边数最少）。
原理：BFS按层次访问顶点，首次访问顶点时经过的路径即为最短路径（边数最少）。
实现：记录每个顶点的“前驱顶点”，通过前驱回溯路径。
python
def shortest_path_unweighted(graph, start):
"""无权图最短路径（BFS），返回各顶点的最短路径长度及路径"""
from collections import deque
visited = {start: 0} # {顶点: 最短路径长度}
predecessor = {start: None} # {顶点: 前驱顶点（用于回溯路径）}
queue = deque([start])
while queue:
v = queue.popleft()
for neighbor in graph.get_neighbors(v):
if neighbor not in visited:
visited[neighbor] = visited[v] + 1 # 路径长度 = 父顶点路径长度 + 1
predecessor[neighbor] = v
queue.append(neighbor)
# 回溯路径（从顶点到start的列表）
def get_path(v):
path = []
while v is not None:
path.append(v)
v = predecessor[v]
return path[::-1] # 反转路径（从start到v）
return {
"distance": visited, # 各顶点最短路径长度
"path": {v: get_path(v) for v in visited} # 各顶点最短路径
}
示例：对无向无权图 0−1−3−2−0 0-1-3-2-0 0−1−3−2−0，从顶点0出发：
顶点1的最短路径：长度1，路径 [0,1] [0, 1] [0,1]；
顶点3的最短路径：长度2，路径 [0,1,3] [0, 1, 3] [0,1,3] 或 [0,2,3] [0, 2, 3] [0,2,3]。
12.5.2 拓扑排序（有向无环图）
问题：对有向无环图（DAG）的顶点排序，使得对任意有向边 (u,v) (u, v) (u,v)，u u u 均出现在 v v v 之前（解决依赖调度问题）。
算法：Kahn算法（基于入度表和队列）：
1.计算所有顶点的入度（指向该顶点的边数）；
2.入度为0的顶点入队（无依赖，可优先执行）；
3.出队顶点 u u u，加入排序序列，同时将 u u u 的邻接顶点入度减1（解除依赖）；
4.重复步骤2~3，直至队空。若排序序列长度等于顶点数，则图无环；否则存在环。
代码实现
python
def topological_sort_kahn(graph):
"""拓扑排序（Kahn算法），返回排序序列（有环则返回空列表）"""
from collections import deque
# 1. 计算入度
in_degree = {v: 0 for v in graph.vertices}
for v in graph.vertices:
for neighbor in graph.get_neighbors(v):
in_degree[neighbor] += 1 # 有向边 (v, neighbor)，neighbor入度+1
# 2. 入度为0的顶点入队
queue = deque([v for v in graph.vertices if in_degree[v] == 0])
topo_order = []
# 3. 处理顶点并更新入度
while queue:
u = queue.popleft()
topo_order.append(u)
for v in graph.get_neighbors(u):
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
# 若排序序列长度不等于顶点数，说明有环
return topo_order if len(topo_order) == len(graph.vertices) else []
示例：任务调度图 A→B→C A ightarrow B ightarrow C A→B→C（A依赖B，B依赖C），拓扑排序序列为 [C,B,A] [C, B, A] [C,B,A]。
12.6 本章总结
图的核心价值：描述多对多关系，是网络分析、路径规划、依赖调度等复杂问题的基础。
存储方式：邻接矩阵适合稠密图和快速边判断（O(1)），邻接表适合稀疏图和高效邻接顶点访问（O(k)）。
遍历算法：DFS（栈实现，深度优先）和BFS（队列实现，广度优先）是图处理的基础，支撑最短路径、拓扑排序等高级应用。
应用场景：路径规划（BFS最短路径）、任务调度（拓扑排序）、社交网络分析（连通分量）等。
图结构的灵活性使其在现实中应用广泛，但需根据图类型和问题需求选择合适的存储方式和算法，平衡时间与空间效率。
12.7 思考题
1.实现带权图的Dijkstra算法，求从起点到其他顶点的最短路径（提示：用优先队列存储待访问顶点及当前最短距离）。
2.判断有向图是否有环（提示：DFS中检测“回边”，或用拓扑排序Kahn算法判断序列长度）。
3.用邻接表实现无向图的最小生成树（MST）算法（Kruskal或Prim算法）。
4.设计一个简单的社交网络推荐系统，基于共同好友数推荐可能认识的人（提示：用邻接表存储好友关系，计算两非好友顶点的共同邻接顶点数）。
5.用图结构表示课程依赖关系（有向边 (A,B) (A,B) (A,B) 表示A是B的先修课），实现算法判断某课程是否可修（即所有先修课均已完成）。
本站原创，转载请注明出处：https://www.xin3721.com/python3/python49304.html
