图:术语与存储结构
线性表是「一对一」,树是「一对多」,图是「多对多」。这一讲只抓三件事: 图的常用术语、邻接矩阵与邻接表的取舍、以及 DFS / BFS 两种遍历。
8.1 图是什么:定义、分类与规模
8.1.1 从线性表、树到图:逻辑结构的第三次跳跃
线性表是「一对一」,树是「一对多」,图是「多对多」: 任意两个顶点之间都可能有边,允许有环,也允许不连通。 社交网络、道路网、课程先修关系,都是图。
8.1.2 图的严格定义:G = (V, E)
图由顶点集 V 和边集 E 组成,记作 G = (V, E)。
无向边记 (v,w),有向边(弧)记 <v,w>。
顶点数记 n = |V|,边数记 e = |E|。
8.1.3 有向图、无向图、多重图、自环、简单图
- 无向图:每条边都没有方向,
(v,w)与(w,v)是同一条边。 - 有向图:每条边都有方向,
<v,w>与<w,v>是两条不同的弧。 - 多重图:允许两个顶点之间有多条边(平行边)。
- 自环:一条边从顶点连回它自己。
- 简单图:既没有自环,也没有平行边的图。后面不做特别说明时,默认讨论简单图。
8.1.4 稠密图与稀疏图
边数相对于 n² 很多,叫稠密图;边数远小于 n²,叫稀疏图。
两者没有绝对的分界,工程上常按 e 与 n² 的比例粗略判断。
这个区分很重要:本讲用的邻接矩阵要开 n×n 个格子,空间是 O(n²),
所以它更适合稠密图;稀疏图如果硬用矩阵,会浪费大量空间。
8.2 图的术语体系
8.2.1 邻接点与度
有边相连的两个顶点互为邻接点。无向图中,顶点 v 的度
d(v) 是与它相连的边数;自环对度的贡献是 2。
度为 0 的点叫孤立点,度为 1 的点叫悬挂点。
8.2.2 入度与出度
有向图中,入度是以该点为弧头的弧数,出度是以该点为弧尾的弧数。
出度为 0 的点叫汇点,入度为 0 的点叫源点;
所有点的入度之和 = 出度之和 = 弧数 e。
8.2.3 握手定理
无向图:Σd(v) = 2e,所有顶点的度数之和等于边数的两倍。
有向图:入度之和 = 出度之和 = e。
两个常用推论:度数之和一定是偶数;奇度顶点的个数一定是偶数。 例如「只有 1 个奇度顶点」的图不存在。
8.2.4 连通、连通图、连通分量、强连通分量
无向图中,两点之间能沿着边走通就叫连通;任意两点都连通叫连通图; 极大的连通子图叫连通分量。 有向图中,若两点可以互相到达,叫强连通;对应的极大子图叫强连通分量。
8.2.5 子图与生成树
子图:从原图中取一部分顶点和一部分边组成的图。
连通无向图的生成树,是包含全部 n 个顶点、恰好 n−1 条边、
并且仍然连通的子图。
8.3 存储结构:邻接矩阵
8.3.1 定义:用二维数组记录「谁和谁相邻」
用 n×n 的二维数组 A 存图:
有边 (i,j) 时 A[i][j] = 1,否则为 0。
无向图的矩阵关于主对角线对称;有向图一般不对称。
带权图把 1 换成边权,没有边用一个很大的数表示。
8.3.2 从矩阵能读出什么
- 判断两点是否相邻:看
A[i][j],O(1); - 无向图求度:第
i行的和; - 有向图求出度:第
i行的和;求入度:第i列的和; - 枚举一个点的所有邻接点:扫描第
i行,O(n)。
8.3.3 空间复杂度 O(n²)
邻接矩阵固定占 n² 个单元,与边数 e 无关。
所以稠密图用它很合适,稀疏图会浪费大量空间。
8.3.4 邻接矩阵的 C++ 实现
#include <iostream>
using namespace std;
const int N = 8;
int g[N][N];
int main() {
int edges[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},
{3,4},{4,5},{5,6},{5,7}};
for (int i = 0; i < 9; ++i) {
int u = edges[i][0], v = edges[i][1];
g[u][v] = g[v][u] = 1; // 无向图:一条边写两格
}
cout << "0 的度 = ";
int deg = 0;
for (int j = 0; j < N; ++j) deg += g[0][j];
cout << deg << "\n"; // 2
cout << "0 和 1 相邻吗? " << (g[0][1] ? "是" : "否") << "\n";
return 0;
}
8.4 邻接表:只存真正存在的边
邻接矩阵把不存在的边也记成 0,稀疏图会浪费很多格子。 邻接表换一个思路:给每个顶点挂一个列表,列表里只放它真正相连的邻接点。
- 空间:
O(n + e)(无向图存两条方向,常数是 2); - 枚举 u 的邻接点:直接遍历
g[u],只花O(deg(u)); - 判断 u、v 是否相邻:要在
g[u]里查找,最坏O(deg(u)); - 适合:稀疏图;不适合频繁判断两点是否直接相邻。
8.5 邻接矩阵 vs 邻接表
两种存法没有绝对的好坏,关键看图是稠密还是稀疏、最常做什么操作。
设图有 n 个顶点、e 条边:
| 对比项 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(n²),与边数无关 | O(n+e) |
| 判断 u、v 是否相邻 | O(1) | O(deg(u)) |
| 枚举 u 的所有邻接点 | O(n) | O(deg(u)) |
| 求无向图某点的度 | 第 u 行求和,O(n) | 链表长度,O(1) 或 O(deg(u)) |
| 适合的图 | 稠密图 | 稀疏图 |
| 代码难度 | 最简单 | 稍多一层列表 |
本讲的 DFS / BFS 代码统一用邻接表,因为它枚举邻接点更快; 如果图很稠密,或者经常要判断“两点是否直接相连”,用邻接矩阵更合适。
8.6 图的遍历(一):深度优先搜索 DFS
8.6.1 一句话本质:一条路走到黑,撞墙再回头
从起点出发,访问它并标记;然后依次看它的每个邻接点: 没访问过就递归进去;走不通就退回上一个点,换下一个邻接点。
8.6.2 手推过程
仍用示例图 G(8 个顶点、9 条边),从 0 出发,
约定邻接点按编号从小到大访问,得到 DFS 序列:
0 1 2 3 4 5 6 7。
每次走到新点就继续深入,走不动再回溯。
8.6.3 完整递归代码
#include <bits/stdc++.h>
using namespace std;
const int N = 8;
vector<int> g[N];
bool vis[N];
void dfs(int u) {
vis[u] = true;
cout << u << " ";
for (int v : g[u]) {
if (!vis[v]) dfs(v);
}
}
int main() {
int edges[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},
{3,4},{4,5},{5,6},{5,7}};
for (int i = 0; i < 9; ++i) {
int u = edges[i][0], v = edges[i][1];
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 0; i < N; ++i) sort(g[i].begin(), g[i].end());
dfs(0); // 输出:0 1 2 3 4 5 6 7
cout << "\n";
return 0;
}
DFS 用递归(系统栈),所以会先往深处走,走不通再回溯。
8.6.4 复杂度
用邻接表存图时,每个顶点访问一次、每条边检查两次,时间复杂度是
O(n+e);空间是 O(n)(visited 数组 + 递归栈)。
如果改用邻接矩阵,复杂度会变成 O(n²)。
8.6.5 DFS 能做什么
- 求连通分量:外层循环遇到未访问点就 DFS 一次;
- 记录访问顺序和父结点,得到一棵 DFS 树;
- 走迷宫:把格子看成顶点,DFS 能找一条可行路径(不保证最短);
- 与二叉树先序遍历对应:先访问自己,再递归孩子。
8.7 图的遍历(二):广度优先搜索 BFS
8.7.1 一句话本质:一圈一圈向外扩散
把起点入队并标记;每次从队头取出一个点,把它所有未访问的邻接点入队并标记; 队列空为止。DFS 用栈,BFS 用队列。
8.7.2 手推过程与分层
从 0 出发,BFS 的层次是:
L0 = {0}、L1 = {1,6}、
L2 = {2,7,5}、L3 = {3,4}。
每个点第一次被访问时,所在的层就是它到 0 的最短边数。
8.7.3 复杂度
邻接表下,每个顶点入队出队各一次、每条边检查常数次,时间复杂度是
O(n+e);队列、visited 数组占 O(n) 空间。
如果改用邻接矩阵,复杂度会变成 O(n²)。
8.7.4 无权图的单源最短路
BFS 第一次到达某个点时,经过的边数就是最短距离。
下面用 dist[] 记录距离、pre[] 记录前驱,
并给出从 0 到 7 的一条最短路径。
#include <bits/stdc++.h>
using namespace std;
const int N = 8;
vector<int> g[N];
int dist[N], pre[N];
int main() {
int edges[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},
{3,4},{4,5},{5,6},{5,7}};
for (int i = 0; i < 9; ++i) {
int u = edges[i][0], v = edges[i][1];
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 0; i < N; ++i) sort(g[i].begin(), g[i].end());
fill(dist, dist + N, -1);
fill(pre, pre + N, -1);
queue<int> q;
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int u = q.front(); q.pop();
cout << u << " "; // BFS 序列
for (int v : g[u]) {
if (dist[v] != -1) continue; // 已经入过队
dist[v] = dist[u] + 1;
pre[v] = u;
q.push(v);
}
}
cout << "\n";
/* 从 7 倒推到 0,再反转,就是一条最短路 */
vector<int> path;
for (int x = 7; x != -1; x = pre[x]) path.push_back(x);
reverse(path.begin(), path.end());
for (int x : path) cout << x << " ";
cout << "\n"; // 0 1 7
return 0;
}