返回：0300 数据结构总目录 · 上一章：0305 Chap5 二叉树 · 下一章：0307 Chap7 二叉搜索树

1、学习目标

图是最一般的关系结构。树是一种特殊图，链表也可以看成特殊图。复盘图结构时，要把三件事分开：图怎么存、图怎么遍历、遍历过程中能顺手解决什么问题。

模块 要掌握的内容
概念 顶点、边、邻接、关联、路径、环路
存储 邻接矩阵、邻接表
遍历 BFS、DFS
应用 连通分量、最短路径、拓扑排序、最小生成树
算法 PFS、Prim、Dijkstra

2、资料范围

PDF 课件 内容
06.Graph.A.Introduction.pdf 图的概念
06.Graph.B1.Adjacency_Matrix.pdf 邻接矩阵
06.Graph.B2.Adjacency_List.pdf 邻接表
06.Graph.C.BFS.pdf BFS
06.Graph.D.DFS.pdf DFS
06.Graph.E.TS.pdf 拓扑排序
06.Graph.F.PFS.pdf 优先级搜索
06.Graph.G.Prim.pdf Prim
06.Graph.H.Dijkstra.pdf Dijkstra

3、图的基本概念

概念 说明
顶点 图中的对象
边 顶点之间的连接
无向图 边没有方向
有向图 边有方向
权重 边或顶点附带的代价
路径 顶点和边交替组成的序列
环路 起点和终点相同的路径

图算法里常用两个规模：

1
2
n = 顶点数
e = 边数

复杂度要同时看 n 和 e。

4、图的存储

4.1 邻接矩阵

用二维数组 A[n][n] 表示边：

1
2
A[i][j] = 1 或 weight，表示 i 到 j 有边
A[i][j] = INF 或 0，表示没有边

特点：

操作 复杂度
判断边是否存在 O(1)
枚举某顶点所有邻居 O(n)
空间 O(n^2)

适合稠密图。

4.2 邻接表

每个顶点维护一个边列表：

1
vector<vector<pair<int, int>>> adj;

特点：

操作 复杂度
判断边是否存在 O(deg(v))
枚举某顶点所有邻居 O(deg(v))
空间 O(n+e)

适合稀疏图。

5、BFS

BFS 用队列，按距离从近到远扩展。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bfs(int s) {
    queue<int> q;
    visited[s] = true;
    dist[s] = 0;
    q.push(s);

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

应用：

  1. 无权图单源最短路。
  2. 判断连通分量。
  3. 二分图判定。
  4. 树或图的层次遍历。

6、DFS

DFS 用递归或栈，沿一条路深入到底再回退。

1
2
3
4
5
6
7
8
9
10
11
void dfs(int v) {
    visited[v] = true;
    dtime[v] = ++clock;
    for (auto [u, w] : adj[v]) {
        if (!visited[u]) {
            parent[u] = v;
            dfs(u);
        }
    }
    ftime[v] = ++clock;
}

DFS 重要概念：

项目 说明
发现时间 第一次访问顶点的时间
完成时间 顶点所有邻边处理完的时间
树边 DFS 树中的边
回边 指向祖先的边
前向边 指向后代的非树边
跨边 连接不同 DFS 分支的边

DFS 可用于拓扑排序、强连通分量、环检测等。

7、拓扑排序

拓扑排序只适用于 DAG。

DFS 版本：

1
对所有顶点 DFS，按完成时间逆序输出。

入度版本：

1
2
3
4
5
6
7
8
9
10
11
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);
    }
}

如果输出顶点数少于 n，说明有环。

8、PFS、Prim 与 Dijkstra

PFS 是优先级搜索框架：每次从未确定顶点里选优先级最高的顶点，再松弛相关边。

算法 优先级含义 解决问题
Prim 到当前树的最小边权 最小生成树
Dijkstra 源点到顶点的最短距离 非负权单源最短路

Dijkstra 框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dist[s] = 0;
pq.push({0, s});

while (!pq.empty()) {
    auto [d, v] = pq.top(); pq.pop();
    if (d != dist[v]) continue;
    for (auto [u, w] : adj[v]) {
        if (dist[u] > dist[v] + w) {
            dist[u] = dist[v] + w;
            pq.push({dist[u], u});
        }
    }
}

Dijkstra 要求边权非负。若存在负权边，要考虑 Bellman-Ford 或其他算法。

9、复杂度汇总

算法 邻接矩阵 邻接表
BFS O(n^2) O(n+e)
DFS O(n^2) O(n+e)
拓扑排序 O(n^2) O(n+e)
Prim 朴素 O(n^2) 可配合堆优化
Dijkstra 堆优化 不常用 O((n+e)log n)

10、易错点

易错点 修正
只写 O(n) 图算法通常要写 O(n+e)
BFS 出队时才标记 入队时标记能避免重复入队
Dijkstra 用在负权边 Dijkstra 只适合非负权
拓扑排序忘记判环 输出数量不足说明有环
邻接矩阵用于大稀疏图 空间可能爆炸

11、复盘清单

检查项 状态
能比较邻接矩阵和邻接表 待复盘
能写 BFS 并求无权最短路 待复盘
能写 DFS 并解释发现/完成时间 待复盘
能写入度版拓扑排序 待复盘
能区分 Prim 和 Dijkstra 的优先级含义 待复盘