返回：0400 算法设计与分析总目录 · 上一章：0402 Chap2 算法分析基础 · 下一章：0404 Chap4 贪心算法

1、学习目标

图是算法设计里最常用的建模工具之一。关系、依赖、道路、网络、社交连接、任务先后顺序，都可以先画成图，再选择遍历、最短路、生成树、流等算法。

模块 要掌握的内容
图模型 顶点、边、有向、无向、权重
存储 邻接表、邻接矩阵
遍历 BFS、DFS
二分图 染色判定、奇环
有向连通性 可达性、强连通直觉
DAG 拓扑序、依赖调度

2、图的基本定义

图通常写作：

1
G = (V, E)

其中 V 是顶点集合，E 是边集合。

类型 说明
无向图 边没有方向，(u, v) 等同于 (v, u)
有向图 边有方向，u -> v 不等同于 v -> u
加权图 每条边带权重，如距离、成本、容量
稀疏图 边数接近 O(V)
稠密图 边数接近 O(V^2)

3、图的存储

存储方式 空间 判断边是否存在 遍历邻居 适用场景
邻接矩阵 O(V^2) O(1) O(V) 稠密图
邻接表 O(V+E) 依邻居数 O(deg(v)) 稀疏图

算法设计题里，邻接表更常见，因为大多数实际图是稀疏的。

4、BFS

BFS 从起点按层扩展，适合求无权图最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
queue<int> q;
dist[s] = 0;
q.push(s);

while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (dist[u] == INF) {
            dist[u] = dist[v] + 1;
            parent[u] = v;
            q.push(u);
        }
    }
}

性质：

  1. 第一次访问到某点时，路径边数最少。
  2. 队列保证按距离层次推进。
  3. 邻接表复杂度为 O(V+E)。

5、DFS

DFS 沿一条路径尽可能深入，再回溯。

1
2
3
4
5
6
7
8
9
void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            parent[u] = v;
            dfs(u);
        }
    }
}

DFS 常用于：

  1. 判断连通性。
  2. 找环。
  3. 拓扑排序。
  4. 强连通分量。
  5. 搜索状态空间。

DFS 的关键不是“递归写法”，而是进入时间、退出时间和边分类所带来的结构信息。

6、二分图判定

二分图可以把顶点分成两组，使每条边都跨组。

判定方法：BFS 或 DFS 染色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
color[s] = 0;
queue<int> q;
q.push(s);

while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (color[u] == -1) {
            color[u] = color[v] ^ 1;
            q.push(u);
        } else if (color[u] == color[v]) {
            return false;
        }
    }
}

二分图等价于不存在奇环。染色冲突时，说明存在一条奇长度回路。

7、有向图连通性

无向图里，连通比较直观；有向图中要区分：

概念 含义
可达 从 u 沿有向边能走到 v
强连通 任意两点互相可达
强连通分量 极大的强连通顶点集合
弱连通 忽略方向后连通

强连通分量可以用 Kosaraju 或 Tarjan 求。当前阶段先理解：方向会打破“连通”的对称性。

8、DAG 与拓扑排序

DAG 是有向无环图，常用于描述依赖关系：

1
先学离散数学 -> 再学数据结构 -> 再学算法

拓扑序要求每条边 u -> v 中，u 都排在 v 前面。

Kahn 算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
queue<int> q;
for (int v = 0; v < n; ++v) {
    if (indeg[v] == 0) q.push(v);
}

while (!q.empty()) {
    int v = q.front();
    q.pop();
    order.push_back(v);
    for (int u : adj[v]) {
        if (--indeg[u] == 0) q.push(u);
    }
}

若最终 order.size() < n，说明图中存在环。

9、复杂度汇总

算法 邻接表复杂度 典型用途
BFS O(V+E) 无权最短路、层次遍历
DFS O(V+E) 连通性、环检测、拓扑排序
二分图染色 O(V+E) 判断奇环、匹配前置
拓扑排序 O(V+E) 依赖调度、DAG DP

10、易错点

易错点 修正
BFS 出队时才标记 入队时标记更稳，避免重复入队
无权最短路用 Dijkstra 无权图 BFS 即可
二分图只从 0 号点开始 非连通图要遍历所有分量
拓扑排序输出少了没检查 输出不足说明有环
有向图连通当成无向图连通 有向图要考虑可达方向

11、复盘清单

检查项 状态
能比较邻接表和邻接矩阵 待复盘
能写 BFS 并还原最短路径 待复盘
能写 DFS 并说明回溯过程 待复盘
能用染色法判断二分图 待复盘
能解释 DAG 和拓扑序 待复盘
能用拓扑排序判断有向环 待复盘