🕸️ 图的定义及遍历
城市之间的航线、朋友之间的关注、地铁换乘……这些关系都能画成「图」：用点代表人、城市，用线代表关系。这一页先认识图的定义、有向无向、顶点的度，再学会用邻接矩阵、邻接表把图存进电脑，最后用 DFS 和 BFS 把整张图逛一遍。
考纲知识点：图的概念
图的广度优先遍历
图的深度优先遍历
图的广度优先遍历
图的深度优先遍历
📖
考纲 · 知识点详述
摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 七级
(3) 为考纲同一条目，同束图的定义及遍历与图论算法两知识块
- (3)图的定义及基本图论算法。包括图的定义、图的种类（有向图、无向图），图节点的度的概念。掌握编程时图的数据结构表示，以及基于深度优先搜索（DFS）和广度优先搜索（BFS）的图搜索与遍历方法，图的泛洪（floodfill）算法。
📚
先学一学
花 6 分钟读完下面 5 课，再去闯关就不慌啦
1
🕸️ 图是什么：点和线的故事
图（graph）由两样东西组成：顶点（vertex）是图里的点，边（edge）是点与点之间的连线。一张图就像一个关系网：把每个同学画成一个点，两个人是好朋友就连一条线，全班就成了一张图。
↔️ 有向图 vs 无向图
· 无向图：边没有方向。微信好友是「互相加」的，你是我好友、我也是你好友，用一条不带箭头的线。
· 有向图：边带箭头。微博关注是有方向的：你关注了 A，不代表 A 关注你，所以要画带箭头的线。
💡 口诀：无向=一来一回都算，有向=箭头指谁才算；好友无向，关注有向。
📏 顶点的度
无向图里，一个顶点连了几条边，就叫它的度。有向图里分两半：箭头指向它的边数叫入度，箭头从它指出去的边数叫出度。有个好用的规律叫握手定理：无向图所有顶点的度数之和 = 边数的两倍（因为每条边被数了两次，两头各一次）。
💡 口诀：度是连了几条线；有向分入和出；度数加起来，等于两倍边数。
2
💾 图怎么存：邻接矩阵和邻接表
把图装进电脑，最常用的两种办法是邻接矩阵和邻接表。
🔢 邻接矩阵：一张 n×n 的表格
有 n 个顶点就开 n × n 的二维数组，第 i 行第 j 列写 1 表示 i 到 j 有边、写 0 表示没边。优点：判断两点有没有边非常快，O(1)；缺点：即使边很少，也要占 n² 格空间。
📋 邻接表：每个点一张邻居清单
给每个顶点开一张「邻居列表」：顶点 1 连了 2、3，就记 1: [2, 3]。优点：边少时很省空间，而且遍历一个点的所有邻居超快；缺点：想立刻知道两点之间有没有边，不如矩阵方便。
💡 口诀：矩阵查边一秒钟，却占 n² 大格子；邻接表省地方，走邻居最方便。
🧪 读代码：邻接表的骨架
看得懂就好，不用背：
vector<int> graph[n]; // n 个顶点，每个一张空列表
graph[u].push_back(v); // 加一条 u -> v 的边
graph[v].push_back(u); // 无向图还要反向加一条
graph[u].push_back(v); // 加一条 u -> v 的边
graph[v].push_back(u); // 无向图还要反向加一条
3
🕳️ DFS 深度优先遍历：一条道走到黑
深度优先搜索（DFS）像勇敢探险家：从起点出发，挑一个邻居就一头钻到底，走不动了再退回上一个岔路口换条路。这种「退一步看看有没有别的路」的动作叫回溯。实现上常用递归或栈（后进先出）。
🌳 和树的联系
二叉树其实也是一种图。树的前序遍历、后序遍历都是「一条道走到底」的 DFS；只有按一层一层从左到右的才是 BFS。所以 DFS 和二叉树先序遍历的道理是一样的。
💡 口诀：DFS 一条道走到黑，撞墙回溯换条路；树的前序后序都是它。
🧪 读代码：用栈做 DFS
看得懂就好，不用背：先把起点放进栈，每取出一个顶点，就把没去过的邻居放进栈。
stack<int> s;
s.push(start); visited[start] = true;
while (!s.empty()) {
int node = s.top(); s.pop();
cout << node << " "; // 访问当前顶点
for (int nb : graph[node])
if (!visited[nb]) {
visited[nb] = true;
s.push(nb);
}
}
s.push(start); visited[start] = true;
while (!s.empty()) {
int node = s.top(); s.pop();
cout << node << " "; // 访问当前顶点
for (int nb : graph[node])
if (!visited[nb]) {
visited[nb] = true;
s.push(nb);
}
}
4
🌊 BFS 广度优先遍历：一圈一圈往外扩
广度优先搜索（BFS）像往水面丢石子：先看起点周围最近的一圈，再看第二圈、第三圈……实现上靠队列（先进先出）把「下一圈要看谁」排好队。
🧭 为什么 BFS 第一次碰到就是最近？
因为它是按距离一层层搜的：第 1 圈没找到才看第 2 圈。所以在一个无权图里求「最少经过几条边」，BFS 第一次碰到目标顶点时，那个层数就是最少的边数。注意：如果边带权重（每条路长度不同），就要用别的高级算法了。
💡 口诀：BFS 一圈一圈扩，谁先碰到谁最近；队列先进先出，波纹推向前。
⏱️ 复杂度：V 个点 E 条边
不管 DFS 还是 BFS，每个顶点最多进一次、每条边最多看一次，所以遍历一张图的时间复杂度都是 O(V + E)（V 顶点数，E 边数）。如果图不连通，就从一个起点遍历完一块，再找下一个没去过的点继续，一样能逛完全图。
🧪 读代码：BFS 靠队列
看得懂就好，不用背：
queue<int> q;
q.push(start); visited[start] = true;
while (!q.empty()) {
int node = q.front(); q.pop();
cout << node << " "; // 访问当前顶点
for (int nb : graph[node])
if (!visited[nb]) {
visited[nb] = true;
q.push(nb);
}
}
q.push(start); visited[start] = true;
while (!q.empty()) {
int node = q.front(); q.pop();
cout << node << " "; // 访问当前顶点
for (int nb : graph[node])
if (!visited[nb]) {
visited[nb] = true;
q.push(nb);
}
}
注意别把 DFS 的栈和 BFS 的队列搞混啦。
5
⚖️ DFS vs BFS 一张表 + 图的应用
📊 两兄弟怎么区分？
· DFS：一条道走到黑，常用递归或栈。适合「找一条可行路、穷举所有可能」。
· BFS：一圈一圈往外扩，常用队列。适合「找最少步数、最近目标」。
不管图是连通的还是有好几块，DFS/BFS 都可以一块一块地遍历完。它们对有向图、无向图都适用。
💡 口诀：DFS 用栈走到底，BFS 用队列铺开圈；图不连通也没事，一块一块逛完它。
🌍 行业实际：图到处都是
社交网络（人是点、关注是边）、交通地图（城市是点、路是边）、网页链接（网页是点、超链接是边）全都是图。地图 App 的「附近的人」「最少换乘」背后，就是计算机在图里做搜索。
🎯
闯关小锦囊 · 考点提醒
- 图 = 顶点 + 边；无向图边没方向，有向图边带箭头；微博关注用有向图、微信好友用无向图。
- 度：无向图一个点的度 = 连的边数；有向图分入度、出度。握手定理：所有顶点度数之和 = 2 × 边数。
- 连通简单无向图 n 个顶点最多 n×(n−1)÷2 条边；有向图最多 n×(n−1) 条边。
- 邻接矩阵查两点有没有边 O(1)；邻接表省空间、走邻居快；稀疏图优先邻接表。
- DFS 一条道走到黑，用递归或栈；二叉树前序/后序遍历都是 DFS。
- BFS 一圈圈往外扩，用队列；无权图里第一次碰到目标 = 最少边数。别把 DFS 的栈和 BFS 的队列记反。
- 遍历整个图的时间复杂度是 O(V + E)；图不连通也能一块一块遍历。
🎮
学完了？来闯关！
下面 16 个小挑战，点一点就能玩
Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。