📖 引入故事：一张地铁线路图
地铁图上是站点（点）和线路（线）。问“从 A 站到 B 站怎么换乘最少”“哪两个站之间最堵”，本质上都是在问一张图上的问题。现实里还有太多“图”：微信好友（人是点、好友关系是线）、城市路网、比赛对阵表……
这些问题的共同点是：关心的不是“点排成一排”，而是“谁和谁连着”。于是计算机用一种叫“图（Graph）”的结构来抽象它们——这也是数据结构里最通用、最强大的一种。
掌握图 G=(V,E) 的基本概念，以及邻接矩阵、邻接表两种存储方式与 DFS/BFS 遍历、握手定理。
从“如何用计算机表示一张地铁线路图、朋友圈关系图”出发，理解图结构怎样抽象现实中的“点对连接”，以及两种最常用存法。
地铁图上是站点（点）和线路（线）。问“从 A 站到 B 站怎么换乘最少”“哪两个站之间最堵”，本质上都是在问一张图上的问题。现实里还有太多“图”：微信好友（人是点、好友关系是线）、城市路网、比赛对阵表……
这些问题的共同点是：关心的不是“点排成一排”，而是“谁和谁连着”。于是计算机用一种叫“图（Graph）”的结构来抽象它们——这也是数据结构里最通用、最强大的一种。
把每个人画成一个点，如果两个人是好友，就在两点之间连一条线。这样一张“点+线”的网就是图。线有没有方向？好友关系是相互的（无向）；但“关注”微博博主是单向的（有向）——这就引出了无向图和有向图。
关键约束：图只关心“连接关系”，不关心点画在纸上的位置。同一张图可以有无数种画法，只要连边一样就是同一张图。
图 G = (V, E)：V 是顶点（vertex）集合，E 是边（edge）集合。顶点也叫“结点”，边表示两个顶点之间的关系。
无向边：用 (u, v) 表示，u、v 没有顺序之分（如好友）。有向边：用 <u, v> 表示，从 u 指向 v（如关注）。
权值：边上可带数字（如路长、费用），叫“带权图”。度（degree）：无向图中与顶点相连的边数；有向图分“入度”（指向它的边）和“出度”（从它指出去的边）。
“点叫顶点边叫边，有向无向看箭头；邻接矩阵二维表，邻接表链表串；遍历 DFS 往深走，BFS 一层层铺；度数加起来，两倍是边数。”
| 知识点 | 你要掌握 | 难度 |
|---|---|---|
| 图的基本概念 | 顶点、边、有向/无向、权、度 | ★ |
| 邻接矩阵 | 二维表 g[u][v]=1/权 | ★★ |
| 邻接表 | 每个顶点挂一个邻居链表 | ★★ |
| DFS / BFS | 深度优先 / 广度优先遍历 | ★★ |
| 度数与握手定理 | 总度数 = 2 × 边数 | ★ |
| 两种存法对比 | 稠密用矩阵、稀疏用邻接表 | ★★ |
先看图的基本术语，再学两种存法（邻接矩阵、邻接表）并各配一次遍历，最后用“度数”把图的大小量化。
看下面这张无向图：5 个顶点、6 条边。顶点集 V={1,2,3,4,5}，边集 E={(1,2),(1,3),(2,4),(3,4),(3,5),(4,5)}。
开一个二维数组 g[u][v]：若 u、v 之间有边就记 1（带权图记权值），否则记 0。无向图的矩阵沿主对角线对称。
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 0 |
| 3 | 1 | 0 | 0 | 1 | 1 |
| 4 | 0 | 1 | 1 | 0 | 1 |
| 5 | 0 | 0 | 1 | 1 | 0 |
优点：判断“u、v 是否相连”只要 O(1) 查表；缺点：即使边很少也要开 n×n 的空间，稀疏图浪费大。配合 DFS（深度优先搜索）可遍历全图。
#include <iostream>
using namespace std;
int g[6][6]; // 1-based，5 个顶点
bool vis[6];
void dfs(int u) {
vis[u] = true;
cout << u << " ";
for (int v = 1; v <= 5; v++)
if (g[u][v] && !vis[v]) dfs(v);
}
int main() {
// 无向图边：1-2, 1-3, 2-4, 3-4, 3-5, 4-5
int e[][2] = {{1,2},{1,3},{2,4},{3,4},{3,5},{4,5}};
for (auto& x : e) { g[x[0]][x[1]] = 1; g[x[1]][x[0]] = 1; }
cout << "邻接矩阵（5 个顶点，无向图，1 表示相连）：" << endl;
for (int i = 1; i <= 5; i++) {
for (int j = 1; j <= 5; j++) cout << g[i][j] << " ";
cout << endl;
}
cout << "从顶点 1 出发 DFS：";
dfs(1);
cout << endl;
return 0;
}邻接矩阵（5 个顶点，无向图，1 表示相连）：
0 1 1 0 0
1 0 0 1 0
1 0 0 1 1
0 1 1 0 1
0 0 1 1 0
从顶点 1 出发 DFS：1 2 4 3 5DFS 沿着一条路走到头再回头（回溯），输出 1 2 4 3 5。
为每个顶点维护一个“邻居列表”（常用 vector<int> adj[N]）。顶点 u 的列表里放所有与它相邻的 v。无向图里 (u,v) 要在 u 和 v 两边各记一次。
优点：只存实际存在的边，空间 O(V+E)，稀疏图极省；遍历某个顶点的邻居很快。缺点是“判断 u、v 是否相连”要扫一遍邻居列表。配合 BFS（广度优先搜索）用队列一层层扩展。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[6]; // 1-based 邻接表
int main() {
int e[][2] = {{1,2},{1,3},{2,4},{3,4},{3,5},{4,5}};
for (auto& x : e) { adj[x[0]].push_back(x[1]); adj[x[1]].push_back(x[0]); }
cout << "邻接表（每个顶点的邻居）：" << endl;
for (int i = 1; i <= 5; i++) {
cout << i << " : ";
for (int v : adj[i]) cout << v << " ";
cout << endl;
}
bool vis[6] = {false};
queue<int> q;
q.push(1); vis[1] = true;
cout << "从顶点 1 出发 BFS：";
while (!q.empty()) {
int u = q.front(); q.pop();
cout << u << " ";
for (int v : adj[u]) if (!vis[v]) { vis[v] = true; q.push(v); }
}
cout << endl;
return 0;
}邻接表（每个顶点的邻居）：
1 : 2 3
2 : 1 4
3 : 1 4 5
4 : 2 3 5
5 : 3 4
从顶点 1 出发 BFS：1 2 3 4 5BFS 像水波一层层扩散，先访问离起点近的点，输出 1 2 3 4 5。
每条边连着两个顶点，因此所有顶点的度数加起来，正好是边数的两倍。这叫握手定理，常用来快速检查“一张图是否可能存在”（出现奇度顶点个数为奇数时不可能）。
#include <iostream>
#include <vector>
using namespace std;
vector<int> adj[6];
int main() {
int e[][2] = {{1,2},{1,3},{2,4},{3,4},{3,5},{4,5}};
for (auto& x : e) { adj[x[0]].push_back(x[1]); adj[x[1]].push_back(x[0]); }
cout << "各顶点的度（无向图 = 邻居个数）：" << endl;
for (int i = 1; i <= 5; i++)
cout << "顶点 " << i << " 的度 = " << adj[i].size() << endl;
int sum = 0;
for (int i = 1; i <= 5; i++) sum += adj[i].size();
cout << "总度数 = " << sum << " = 2 × 边数(" << 6 << ")" << endl;
return 0;
}各顶点的度（无向图 = 邻居个数）：
顶点 1 的度 = 2
顶点 2 的度 = 2
顶点 3 的度 = 3
顶点 4 的度 = 3
顶点 5 的度 = 2
总度数 = 12 = 2 × 边数(6)度数 2+2+3+3+2 = 12 = 2×6，完美吻合。
| 对比项 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(V²) | O(V+E) |
| 查“是否相连” | O(1) 直接查 | O(度) 扫邻居 |
| 遍历所有边 | O(V²) | O(V+E) |
| 适用 | 稠密图、要频繁查边 | 稀疏图（CSP-J 常用） |
初赛与复赛中，邻接表（vector 数组）是最常用写法；邻接矩阵适合顶点少（如 ≤ 2000）且边密的情况。
三道分析编程题：换一张小图写邻接矩阵并 DFS、用邻接表 BFS、统计度数验证握手定理。均给出可编译运行的参考实现。
把边填进 4×4 矩阵，再从顶点 1 深度优先遍历。
#include <iostream>
using namespace std;
int g[5][5]; // 4 个顶点
bool vis[5];
void dfs(int u) {
vis[u] = true;
cout << u << " ";
for (int v = 1; v <= 4; v++)
if (g[u][v] && !vis[v]) dfs(v);
}
int main() {
// 4 顶点边：1-2, 1-3, 2-3, 3-4
int e[][2] = {{1,2},{1,3},{2,3},{3,4}};
for (auto& x : e) { g[x[0]][x[1]] = 1; g[x[1]][x[0]] = 1; }
cout << "邻接矩阵（4 个顶点）：" << endl;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) cout << g[i][j] << " ";
cout << endl;
}
cout << "从顶点 1 出发 DFS：";
dfs(1);
cout << endl;
return 0;
}邻接矩阵（4 个顶点）：
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
从顶点 1 出发 DFS：1 2 3 4DFS 输出 1 2 3 4，矩阵沿对角线对称。
换用邻接表存储，再用队列做广度优先遍历。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[5]; // 4 个顶点
int main() {
int e[][2] = {{1,2},{1,3},{2,3},{3,4}};
for (auto& x : e) { adj[x[0]].push_back(x[1]); adj[x[1]].push_back(x[0]); }
bool vis[5] = {false};
queue<int> q;
q.push(1); vis[1] = true;
cout << "邻接表 BFS（从顶点 1 出发）：";
while (!q.empty()) {
int u = q.front(); q.pop();
cout << u << " ";
for (int v : adj[u]) if (!vis[v]) { vis[v] = true; q.push(v); }
}
cout << endl;
return 0;
}邻接表 BFS（从顶点 1 出发）：1 2 3 4BFS 输出 1 2 3 4，一层层扩散。
数每个顶点的邻居数，再把度数相加看是否等于 2×边数。
#include <iostream>
#include <vector>
using namespace std;
vector<int> adj[5];
int main() {
int e[][2] = {{1,2},{1,3},{2,3},{3,4}};
for (auto& x : e) { adj[x[0]].push_back(x[1]); adj[x[1]].push_back(x[0]); }
cout << "各顶点的度：" << endl;
for (int i = 1; i <= 4; i++)
cout << "顶点 " << i << " 的度 = " << adj[i].size() << endl;
int sum = 0;
for (int i = 1; i <= 4; i++) sum += adj[i].size();
cout << "总度数 = " << sum << " = 2 × 边数(" << 4 << ")" << endl;
return 0;
}各顶点的度：
顶点 1 的度 = 2
顶点 2 的度 = 2
顶点 3 的度 = 3
顶点 4 的度 = 1
总度数 = 8 = 2 × 边数(4)度数 2+2+3+1 = 8 = 2×4，握手定理成立。
把图术语、两种存法、遍历与度数规律一次性理清。
| 结论 | 说明 |
|---|---|
| 图 G=(V,E) | 顶点集 + 边集；边有向 / 无向 |
| 邻接矩阵 | g[u][v]，O(V²)，查边 O(1) |
| 邻接表 | vector 数组，O(V+E)，稀疏图省 |
| DFS | 递归/栈，往深走，回溯 |
| BFS | 队列，一层层扩散 |
| 握手定理 | 总度数 = 2 × 边数 |
⚠️ “图的定义 + 邻接矩阵/邻接表 + DFS/BFS”属 CSP-J 应知；最短路、拓扑排序等属提高，初赛可能考概念、复赛一般不要求手写。
5 大易错点 + 速查表 + 笔记卡，考前一眼回顾。
无向图只在矩阵里记一次边。无向边 (u,v) 必须同时写 g[u][v]=1 和 g[v][u]=1，否则遍历会漏半边。
邻接表下标用错（0-based 还是 1-based）。要么统一从 1 开始，要么统一从 0 开始，别混用。
DFS/BFS 忘记“标记已访问”。不标记会在线圈里反复横跳、死循环。
以为“图”的顶点有固定位置。图只关心连边关系，画法任意、连边相同即同一图。
把“有向图的度”和“无向图”混算。有向图分入度/出度；握手定理对无向图成立，有向图则是“入度总和 = 出度总和 = 边数”。
| 概念 | 要点 |
|---|---|
| 图 | G=(V,E)；边有向/无向 |
| 邻接矩阵 | g[u][v]，O(V²) |
| 邻接表 | vector 数组，O(V+E) |
| DFS/BFS | 都要 visited 标记 |
| 握手定理 | 无向：总度数=2×边数 |
图 Graph = (V, E)
① 顶点 + 边；边有向 / 无向。
② 邻接矩阵：g[u][v]，查边 O(1)，占 O(V²)。
③ 邻接表：vector 数组，占 O(V+E)，稀疏图省。
④ DFS 递归往深走；BFS 队列一层层。
⑤ 无向图总度数 = 2 × 边数（握手定理）。
A基础 / B提高 / C挑战，难度递增，点击展开答案与解析。
点 + 边。
图 G=(V,E)：V 是顶点集、E 是边集。无向图的边 (u,v) 无方向（双向可达）；有向图的边 <u,v> 有方向（仅 u→v）。
思路：图 G = (V, E)：V 是顶点集、E 是边集。无向图的边 (u, v) 双向可达；有向图的边
易错：在有向图里也把一条边当成双向的，重复统计边或度数。
对称矩阵，对角线为 0。
5×5 矩阵：g[1][2]=g[2][1]=1，g[2][3]=g[3][2]=1，g[3][4]=g[4][3]=1，g[4][5]=g[5][4]=1，g[1][5]=g[5][1]=1，其余为 0。
思路：无向图的邻接矩阵是对称的，每条无向边 (u, v) 要在 g[u][v] 与 g[v][u] 两处都置 1。
易错：只填了 g[u][v] 一个位置，漏掉对称的那一格。
数邻居个数。
顶点 1、2、3、4、5 的度均为 2；总度数 = 10 = 2×5（边数 5），符合握手定理。
思路：无向图中顶点的度数 = 邻接矩阵该行 1 的个数 = 邻接表中邻居的个数；所有顶点度数之和 = 2 × 边数，这就是握手定理。
易错：把总度数直接等同于边数，忘了每条无向边为总度数贡献 2。
深搜 vs 广搜。
DFS 适合“是否存在路径、找一条路”；BFS 适合“最少步数/最短层数”。标记 visited 防止在环里重复访问、死循环。
思路：DFS 沿一条路走到底再回溯，适合判连通、找一条路径；BFS 逐层向外扩展，适合求最少步数/最短层数。visited 用来防止在含环的图里反复绕圈。
易错：图上遍历时忘记标记 visited，一遇到环就会死循环或重复入队。
填矩阵后 DFS。
矩阵：g[1][2]=g[1][4]=g[2][3]=g[3][4]=1（对称）。一种 DFS 结果：1 2 3 4。
思路：按边集把矩阵对应的两个对称位置置 1；DFS 从顶点 1 出发，依次尝试尚未访问的邻居，沿一条路走到底再回溯。
易错：DFS 序列并不唯一，逐位去比“标准答案”没有意义；只要满足“走到底再回溯、不重复访问”就都是合法结果。
两边各记一次。
adj[1]={2,4}，adj[2]={1,3}，adj[3]={2,4}，adj[4]={1,3}。
思路：邻接表 adj[u] 存下所有与 u 相邻的顶点；无向图中每条边要在两端的表里各存一次。
易错：只往 adj[u] 里加了 v，忘记同时往 adj[v] 里加 u，导致反向走不通。
队列一层层。
1 的邻居是 2、5；然后 2 的邻居 3、5 的邻居 4（若 2 先于 5 扩展）：1 2 5 3 4。
思路：BFS 用队列逐层推进：起点 1 先入队，每弹出一个结点，就把它尚未访问的邻居按顺序入队；先扩展的邻居，它们的下一层也先出队。
易错：把 BFS 当成“一条路走到底”，写成了 DFS 风格的序列。
队列 + visited。
队列 q 初始 push(起点) 并标记访问；while(q 非空){ u=q.front();弹出；对每个未访问邻居 v 标记访问并入队 }。输出即 BFS 序。
思路：队列先放入起点并标记访问；每轮弹出队头 u，遍历它的所有邻居 v，把尚未访问的标记后入队；结点出队的顺序就是 BFS 序。
易错：在结点“入队时”忘记标记 visited，导致同一个结点被反复入队（应在入队瞬间就标记）。
每条边贡献 2 度。
每条无向边恰好连接两个顶点，给这两个顶点各贡献 1 度，故每条边贡献 2 度；n 条边共贡献 2n 度，即总度数 = 2×边数。
思路：每条无向边连接两个顶点，对总度数的贡献恰好是 2；求和时每条边被两个端点各计一次，所以所有顶点度数之和 = 2 × 边数。
易错：只按一个端点计一次，错误地得出总度数等于边数。
用握手定理 + 奇度个数。
总度数=18 为偶数（满足 2×边数=9），但奇度顶点有 1,3,3,3 共 4 个（偶数个），单看握手定理不排除；然而顶点 1 度=5 意味着与其余 5 个全连，剩余 5 顶点间至少需凑出各自度数，可构造（如 1 连全部，再在 2-3-4-5-6 间配 2+2+...），故可能。注：握手定理只排除“总度数奇数”或“奇度个数为奇数”的情况。
思路：先用握手定理做必要条件检查：总度数必须为偶数，且奇度顶点的个数也必须是偶数（此处 18 和 4 都满足）；再做构造——顶点 1 度为 5 就连满其余 5 个点，剩下的度数也能在局部凑出，故可能。
易错：只看总度数是偶数就下结论，漏掉“奇度顶点个数必须为偶数”这一条。
复用本讲链表 + DFS。
vector<int> adj[N]；读边双向 push_back；bool vis[N]；dfs(u) 标记后递归访问未访问邻居；main 调 dfs(1)。
思路：用 vector 数组做邻接表，读边时双向 push_back；vis 数组标记访问，dfs(u) 进入时先标记，再遍历所有尚未访问的邻居递归下去。
易错：无向图只 push 了一次单向边，导致反向走不通；或进入 dfs 时忘记标记，造成重复递归。
两种方法对照。
矩阵法：int g[N][N]，读边双向置 1，度=第 i 行 1 的个数。邻接表法：度=adj[i].size()。两者边数都=m，度数应一致。
思路：矩阵法：读边时把 g[u][v]、g[v][u] 都置 1，顶点度数 = 该行 1 的个数。邻接表法：度数 = adj[i].size()。两种方法得到的总边数与各顶点度数应当完全一致。
易错：统计度数时把矩阵整行求和（若要含自身 g[i][i] 就会偏大），或邻接表只加了单向边导致度数偏小。