图详解
约 1568 字大约 5 分钟
2025-11-19
一、图的定义
图（Graph） 是一种非线性数据结构，由 顶点（Vertex） 集合和 边（Edge） 集合构成，记作 G = (V, E)。
- V：非空顶点集，
V = {v₁, v₂, ..., vₙ} - E：边集，
E ⊆ V × V，每条边连接两个顶点
v₁ ─── v₂
│ │
│ │
v₃ ─── v₄
V = {v₁, v₂, v₃, v₄}
E = {(v₁,v₂), (v₁,v₃), (v₂,v₄), (v₃,v₄)}比线性表和树更进一步：线性表是"一对一"，树是"一对多"，图是**"多对多"**，每个顶点都可以和任意其他顶点相连。
二、图的类型
2.1 按方向分类
| 类型 | 说明 | 示例 |
|---|---|---|
| 无向图（Undirected Graph） | 边没有方向，(u,v) 与 (v,u) 等价 | 社交好友关系 |
| 有向图（Directed Graph / Digraph） | 边有方向，<u,v> 与 <v,u> 不同 | 网页超链接、关注关系 |
ASCII 对比：
无向图: v₁ ─── v₂ 有向图: v₁ ──→ v₂
│ ↑
│ │
v₃ ─── v₄ v₃ ←── v₄2.2 按权重分类
| 类型 | 说明 |
|---|---|
| 无权图（Unweighted Graph） | 边只有连接关系，没有权值 |
| 加权图（Weighted Graph） | 每条边带有一个数值（距离、成本、时间等） |
加权图示例（数字表示权重）:
v₁ ──5── v₂
\ /
\ /
3 2
\ /
v₃2.3 按连通性分类
| 类型 | 说明 |
|---|---|
| 连通图（Connected Graph） | 任意两个顶点之间都有路径（无向图） |
| 强连通图（Strongly Connected Graph） | 任意两个顶点之间都有双向路径（有向图） |
| 非连通图（Disconnected Graph） | 存在至少一对顶点之间无路径 |
连通图: 非连通图:
a ─ b ─ c a ─ b c ─ d2.4 特殊图
| 类型 | 说明 |
|---|---|
| 完全图（Complete Graph / Kₙ） | 每对顶点之间都有一条边。` |
| 稀疏图（Sparse Graph） | ` |
| 稠密图（Dense Graph） | ` |
| 有向无环图（DAG） | 有向图中不存在环，可用于拓扑排序 |
完全图 K₄（6 条边）:
a ─── b
│\ /│
│ × │
│/ \│
c ─── d三、图的表示方法
3.1 邻接矩阵（Adjacency Matrix）
用一个 n × n 的二维数组 A 表示图，A[i][j] 表示顶点 i 到 j 的关系。
无向无权图 G 的邻接矩阵:
v₁ v₂ v₃ v₄
v₁ [ 0 1 1 0 ]
v₂ [ 1 0 0 1 ]
v₃ [ 1 0 0 1 ]
v₄ [ 0 1 1 0 ]- 优点：判断任意两点是否相邻只需 O(1)
- 缺点：存储空间 O(V²)，对稀疏图浪费严重
3.2 邻接表（Adjacency List）
用一个数组存储每个顶点的邻接顶点链表（或动态数组）。
无向无权图 G 的邻接表:
v₁: [v₂, v₃]
v₂: [v₁, v₄]
v₃: [v₁, v₄]
v₄: [v₂, v₃]- 优点：存储空间 O(V+E)，适合稀疏图
- 缺点：判断两点是否相邻需要 O(V) 遍历
3.3 对比总结
| 特性 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(V²) | O(V+E) |
| 检查边 (u,v) | O(1) | O(V) |
| 遍历所有邻接点 | O(V) | O(degree(v)) |
| 添加边 | O(1) | O(1) |
| 删除边 | O(1) | O(V) |
| 适合场景 | 稠密图 | 稀疏图 |
四、图的遍历
4.1 广度优先搜索（BFS）
按层逐层访问，使用队列实现。
BFS 执行过程 (起点 v₁):
步骤 1: 访问 v₁, 入队 [v₁]
步骤 2: 出队 v₁, 访问其邻居 v₂, v₃, 入队 [v₂, v₃]
步骤 3: 出队 v₂, 访问其未访问邻居 v₄, 入队 [v₃, v₄]
步骤 4: 出队 v₃ (邻居都已访问), 入队 [v₄]
步骤 5: 出队 v₄, 完成
BFS 序列: v₁ → v₂ → v₃ → v₄伪代码:
BFS(V, start):
visited = 集合(初始为空)
queue = 队列()
visited.add(start)
queue.enqueue(start)
while queue 不为空:
v = queue.dequeue()
for 每个邻居 u of v:
if u 不在 visited 中:
visited.add(u)
queue.enqueue(u)- 时间复杂度：O(V+E)
- 空间复杂度：O(V)
- 应用：无权图最短路径、层次遍历
4.2 深度优先搜索（DFS）
尽可能深地访问，遇到死胡同则回溯，使用栈（或递归）实现。
DFS 执行过程 (起点 v₁):
步骤 1: 访问 v₁ (入栈 [v₁])
步骤 2: 从 v₁ 走到 v₂ (入栈 [v₁, v₂])
步骤 3: 从 v₂ 走到 v₄ (入栈 [v₁, v₂, v₄])
步骤 4: 从 v₄ 回到 v₂, 再到 v₃ (入栈 [v₁, v₂, v₃])
步骤 5: v₃ 无未访问邻居, 回溯
步骤 6: 全部回溯完成
DFS 序列: v₁ → v₂ → v₄ → v₃伪代码（递归版）:
DFS(V, start):
visited = 集合(初始为空)
def dfs(v):
visited.add(v)
for 每个邻居 u of v:
if u 不在 visited 中:
dfs(u)
dfs(start)- 时间复杂度：O(V+E)
- 空间复杂度：O(V)（递归栈或显式栈）
- 应用：连通性检测、拓扑排序、环检测
BFS vs DFS 对比
| 特性 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列 | 栈/递归 |
| 遍历顺序 | 按层（宽度优先） | 沿分支（深度优先） |
| 最短路径 | 可求无权图最短路径 | 不保证 |
| 空间使用 | 宽树时可能大 | 深树时可能大 |
五、算法复杂度总表
| 算法 | 时间复杂度 | 空间复杂度 | 适用条件 |
|---|---|---|---|
| BFS | O(V+E) | O(V) | 无权图遍历 |
| DFS | O(V+E) | O(V) | 图遍历、连通性 |
| Dijkstra | O((V+E)log V) | O(V) | 非负权单源最短路径 |
| Bellman-Ford | O(V·E) | O(V) | 任意权值、检测负环 |
| Prim (MST) | O(E log V) | O(V) | 稠密图最小生成树 |
| Kruskal (MST) | O(E log E) | O(V) | 稀疏图最小生成树 |
| 拓扑排序 | O(V+E) | O(V) | DAG 线性排序 |
| Floyd-Warshall | O(V³) | O(V²) | 全源最短路径（练） |
六、图的应用场景
社交网络分析
- 好友推荐：共同好友、最短路径
- 影响力传播：BFS 模拟信息扩散
- 社区发现：图聚类算法
GPS 导航与路径规划
- 最短路径：Dijkstra 算法是 GPS 的核心引擎
- 实时交通：加权图为每条道路赋予实时通行时间
- 路线推荐：多目标最短路径
网页爬虫
- 网页作为顶点：每个 URL 是一个顶点
- 超链接作为边：链接是方向性边
- 爬取策略：BFS（广度优先爬取）或 DFS（深度优先爬取）
推荐系统
- 协同过滤：用户-物品二部图
- 图神经网络（GNN）：基于图结构的深度学习推荐
- 知识图谱：实体关系网络增强推荐精度
其他应用
| 领域 | 应用 |
|---|---|
| 编译器 | 依赖图、指令调度 |
| 操作系统 | 资源分配图、死锁检测 |
| 计算机网络 | 路由协议（OSPF、BGP） |
| 生物信息学 | 蛋白质相互作用网络 |
| 软件工程 | 版本控制 DAG、模块依赖图 |