企业官网建设流程全解析

图论这块内容，是蓝桥杯C++组从基础语法迈向算法设计的第一个分水岭。很多同学在DAY6之前，天天跟数组、字符串、结构体打交道，觉得编程不过如此；到了图这一章，第一次发现原来代码还能描述这么复杂的关系。我在复盘蓝桥杯真题和带集训队时，最常听到的就是一句话：图我看了半天，题也会做，就是代码敲不出来。这篇文章就以蓝桥杯C++DAY6图为主题，把图的存储、遍历、最短路、拓扑排序这些高频考点从头串一遍，全部给到能直接抄进IDE的模板和踩坑记录。适合刚学完STL准备啃图论的同学，也适合刷真题时总卡在段错误、TLE上不知道怎么查的人。

1. 蓝桥杯为什么爱考图，DAY6到底要学什么

1.1 从真题分布看图的份量

先说结论：图论不一定是每场必考的大题，但它是拉开差距的常客。省赛C++组的题目里，搜索、动态规划、贪心常年占据前三，图论题目经常以隐式图的形式出现——题目不会直接告诉你"这是一张图"，需要你自己抽出来。比如网格寻路、迷宫最短步数、任务依赖排序、连通区域计数，本质上全是图。

我把近几届蓝桥杯真题按题型归类统计过，图相关的高频考点大概集中在下面几类：图的存储与遍历、连通块计数、最短路径、拓扑排序、二分图判定、最小生成树。其中前四类出现的概率最高，恰好是DAY6一个晚上加一个上午能啃下来的范围。真正到了国赛阶段，才会出现更多和状态压缩、网络流结合的综合题，但省赛阶段把基础图论吃透，足够稳稳拿下大部分分数。

1.2 DAY6的知识边界：会建图、会遍历、会跑板子

很多同学有个误区，觉得图论内容那么多，必须把网络流、强连通分量都学了才能做题。实际上蓝桥杯对图论的考察非常克制，你只需要做到三件事：第一，给定数据能正确建图；第二，能用DFS或BFS完成遍历、计数、寻路；第三，能根据题目要求套对最短路或拓扑排序的模板。

DAY6建议把学习边界划在这五个点上：邻接矩阵和邻接表、链式前向星、DFS遍历、BFS遍历、Dijkstra最短路。学有余力再补Floyd和拓扑排序。不要一上来就啃Tarjan、网络流，那是国赛冲刺阶段的事情。我见过太多人DAY6就去刷“强连通分量缩点”的题，结果连邻接表都写不利索，刷了两天直接劝退。图论是搭积木，遍历和存储是底座，底座不稳，后面全白搭。

2. 图的存储方案：从邻接矩阵到链式前向星

2.1 邻接矩阵：小规模数据的无脑解

邻接矩阵就是一个二维数组，g[i][j]表示顶点i到顶点j是否有边，或者边的权值是多少。无向图记得对称赋值，即g[i][j] = g[j][i] = w。有权图就把权值存进去，没权的就存0或1。

int g[505][505]; memset(g, 0x3f, sizeof g); // 初始化成无穷大，适合最短路 for (int i = 1; i <= n; i++) g[i][i] = 0; // 读入m条边 for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u][v] = min(g[u][v], w); g[v][u] = min(g[v][u], w); // 无向图加上这行 }

这里有个非常容易踩的坑：题目如果没说保证无重边，读入时一定要做min取小。我见过不少同学直接g[u][v] = w，结果后读入的边覆盖了前面更短的边，Dijkstra跑出来答案偏大，查半天查不出来。

邻接矩阵的优势是写起来快、查任意两个顶点之间是否有边是O(1)。缺点是空间是O(n²)，n超过1000基本就危险了。蓝桥杯的数据范围，n在500以内用邻接矩阵完全没问题，一旦n上了10000，矩阵直接爆炸，必须换邻接表。

2.2 vector邻接表：绝大多数蓝桥杯题目的最优解

邻接表的核心思想是"每个顶点只存跟它相连的边"。用vector<int> g[N]存无向图，vector<pair<int,int>> g[N]存带权图。代码几乎无脑：

#include <bits/stdc++.h> using namespace std; const int N = 100010; vector<pair<int, int>> g[N]; // g[u] 里存 {v, w} void add(int u, int v, int w = 1) { g[u].push_back({v, w}); // 无向图再加一行: g[v].push_back({u, w}); }

遍历一个顶点的所有邻居：

for (auto [v, w] : g[u]) { // v是邻居，w是权值 }

用vector做邻接表，空间是O(n+m)，遍历邻居的均摊复杂度也优秀。对蓝桥杯来说，90%的图论题用这一种存储就够了。唯一的代价是常数略大，但在2秒时限和10⁵级别的数据下，vector完全扛得住。我集训队的学生第一次写邻接表，十个里有八个会忘记无向图要加两遍边，这是最经典的入门错误，没有之一。

2.3 链式前向星：省赛想拿高分建议掌握

链式前向星本质是用数组模拟链表，把每条边存进一个结构体数组，通过next指针串起来。看起来比vector复杂，但它有两个实打实的优势：内存连续、访问快，而且在某些题目里能直接按边的插入顺序做操作。

const int N = 100010, M = 200010; struct Edge { int to, w, next; } e[M]; int head[N], cnt = 0; void add(int u, int v, int w) { e[++cnt] = {v, w, head[u]}; head[u] = cnt; }

遍历时这样写：

for (int i = head[u]; i; i = e[i].next) { int v = e[i].to, w = e[i].w; // 处理边 }

注意数组M要开成边总数的两倍，因为无向图每条边会add两次。这个点我每次强调，每次还是有人开小数组导致段错误。如果你的目标只是省赛拿个省二省三，vector够用了；但如果想冲国赛，链式前向星必须练到闭眼能写，因为很多进阶题目的标准解法都用它。

3. 图的遍历：DFS与BFS的底层逻辑、模板和变体

3.1 DFS：从递归模板到回溯思维

DFS的模板不算长，但递归的思想比代码本身重要。核心就四步：标记当前点、处理当前点、递归访问没访问过的邻居、如果需要就回溯。

bool vis[N]; void dfs(int u) { vis[u] = true; // 这里处理当前节点，比如记录路径、累加答案 for (int v : g[u]) { if (!vis[v]) { dfs(v); } } // 如果题目要求枚举所有路径，递归结束后要取消标记 // vis[u] = false; // 回溯 }

初学者最容易搞混的是visited标记的位置。普通的连通性遍历，标记放在进入dfs时，因为每个点只需要访问一次；而全排列、迷宫所有路径这类问题，标记要放在递归前后做回溯，否则路径会互相干扰。判断该用哪种，只需要问自己一句话：这个点能不能被多条路径经过？能，就回溯；不能，就别回溯。

DFS还有一类常见变体是带权值的深度优先，比如计算连通块面积。此时把"处理当前节点"写成累加计数器即可。在蓝桥杯真题里，DFS最常见的场景就是岛屿数量、八连通区域统计、二叉树路径求和这类问题。

3.2 BFS：最短步数与层序思想

BFS用队列实现，天然自带"按层扩展"的特性。第一次访问到某个点时，走的步数一定是最少的——前提是每条边的权值都为1。这是BFS能求无权图最短路的核心原因。

int step[N]; queue<int> q; void bfs(int s) { memset(step, -1, sizeof step); step[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (step[v] == -1) { step[v] = step[u] + 1; q.push(v); } } } }

注意这里我用step[v] == -1同时充当了"是否访问过"和"距离"两个角色，这是比单独开vis数组更省事也更不容易错的写法。BFS的层序思想在蓝桥杯里最经典的应用是迷宫最短步数、华容道类滑块问题、以及八数码这种需要状态压缩的BFS。

还有一个小技巧：如果网格题，可以把二维坐标映射成一维编号，id = x * m + y，这样BFS队列里只存一个int，写起来清爽很多。

3.3 连通块计数：遍历模板最直接的考点

连通块问题是图遍历最简单的落地场景。给定一张图，数一数有几个互不相连的部分。做法是循环所有顶点，遇到没访问过的就启动一次DFS或BFS，启动次数就是连通块数。

int cnt = 0; for (int i = 1; i <= n; i++) { if (!vis[i]) { cnt++; dfs(i); // 或 bfs(i) } } cout << cnt << endl;

这类题在蓝桥杯中经常披着网格的外衣，比如0-1矩阵里数1组成的连通区域。处理网格时，方向数组是最容易写错的点。建议统一写成：

int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; // 八连通再加四个斜向 int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

我见过有人把dx和dy的对应关系写反，导致搜索方向全乱，样例能过、数据一大就错。建议每次写完先跑一遍最简单的2x2网格验证四个方向都对，别嫌麻烦。

4. 从Dijkstra到拓扑排序：DAY6最能提分的三类板子

4.1 Dijkstra的堆优化写法

Dijkstra解决的是单源最短路问题，也就是从一个起点出发到所有其他点的最短距离。学了它就等于把蓝桥杯近十年最短路相关的题吃掉了一大半。堆优化版本是必背模板，用优先队列维护当前距离最小的点。

const int INF = 0x3f3f3f3f; int dist[N]; bool done[N]; void dijkstra(int s) { memset(dist, 0x3f, sizeof dist); dist[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (done[u]) continue; done[u] = true; for (auto [v, w] : g[u]) { if (dist[v] > d + w) { dist[v] = d + w; pq.push({dist[v], v}); } } } }

三个重点说一下。第一，0x3f3f3f3f约等于10⁹，作为无穷大足够大，而且两个无穷大相加不会溢出int，可以放心做d + w。第二，if (done[u]) continue这行必须有，它保证每个点只真正出队处理一次，否则复杂度退化成O(nm)。第三，pair在优先队列里默认按first排序，所以必须把距离放前面，否则比较的是顶点编号，结果完全错误。

有些同学问为什么要用greater<>，因为默认的优先队列是大顶堆，而Dijkstra每次要取最小的，不翻转就是错的。实在记不住，就死记这一行，比赛时别纠结原理。

4.2 Floyd：想不起来Dijkstra时的兜底方案

Floyd是算法复杂度最高的最短路方案，O(n³)，但它有一个别人比不了的优势：代码极短，且一次求出所有点对的最短路径。n在200以内时用Floyd，写起来比Dijkstra还快。

int f[N][N]; // 读入边，f[u][v] = w，其他为INF，f[i][i] = 0 for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (f[i][j] > f[i][k] + f[k][j]) { f[i][j] = f[i][k] + f[k][j]; } } } }

中间点k必须在最外层循环，这个是Floyd正确性的关键。如果把k放到最内层，得到的是完全错误的结果。我自己刚学的时候犯过这个错，调了一晚上，后来把"k放最外面"当成口诀才记住。Floyd在蓝桥杯里常见于传递闭包问题，比如判断一张有向图中哪些点互相可达，这种题用Floyd改写成f[i][j] |= f[i][k] && f[k][j]即可。

4.3 拓扑排序：判环与依赖分析的万能钥匙

拓扑排序处理的是有向无环图，典型场景是课程先修关系、任务依赖、编译顺序。模板核心是不断删除入度为0的节点，维护一个队列即可。

int indeg[N]; queue<int> q; for (int i = 1; i <= n; i++) { if (indeg[i] == 0) q.push(i); } vector<int> topo; while (!q.empty()) { int u = q.front(); q.pop(); topo.push_back(u); for (int v : g[u]) { indeg[v]--; if (indeg[v] == 0) q.push(v); } } if (topo.size() < n) { cout << "有环" << endl; } else { for (int x : topo) cout << x << ' '; }

做完后如果拓扑序列长度不等于n，说明图里存在环。这个判环能力非常实用，很多题目表面上问"能否完成所有任务""是否存在矛盾依赖"，本质都是拓扑排序判环。

注意题目如果要求输出字典序最小的拓扑序列，需要把queue换成priority_queuegreater<>，并且入堆条件不变。蓝桥杯有一类题专门考这个变体，比如字典序最小的课程安排，优先队列方案能直接过。

5. 常见问题与赛场排错实录

5.1 段错误：数组越界是图论代码第一杀手

蓝桥杯评测环境里，段错误最常见的原因就是数组开小。我统计过集训队同学交的图论代码，超过一半的Runtime Error是同一个原因：邻接表只开了N个vector，结果题目n最大是10⁵，你按10⁴开。更隐蔽的是链式前向星的边数组，无向图要开2倍，很多人只开了M，第m条边add两次时直接越界。

建议统一养成习惯：看到n的最大范围，vector就开N + 5，边数数组就开2 * M + 5，先多开再优化。别为了省几个字节的内存去赌数据范围，蓝桥杯的内存限制通常很宽裕。

另一个常见段错误点是DFS递归函数里访问了不存在的邻居，比如网格题里坐标越界没判断。写网格DFS时，第一行必须是边界检查：

if (x < 0 || x >= n || y < 0 || y >= m) return;

5.2 爆栈：DFS深度过大怎么办

蓝桥杯的DFS递归深度如果超过几十万层，程序会直接栈溢出崩溃，报错可能显示为段错误，容易被误判成数组问题。n=10⁵量级的链状图，DFS递归个10⁵层，很多评测环境就撑不住了。

三个应对办法。第一，能换BFS就换BFS，BFS没有递归栈的问题，这也是为什么迷宫最短步数类题目默认用BFS的原因。第二，DFS递归改成显式栈模拟，用vector当栈，手动push、pop，可以完全避开系统栈限制。第三，加编译器指令开大栈，但蓝桥杯环境不一定支持，不推荐作为第一方案。

我比赛时的经验是：深度可能超过10⁴的优先想BFS，实在要DFS就手写栈，别赌递归不爆。省赛题目为了照顾多数选手，一般会把图设计得不会导致爆栈，但国赛就不一定了。

5.3 TLE：输入输出和常数优化

图论题的输入输出量通常比较大，很多同学用cin读10⁵条边，不开加速直接TLE。解决方法是在main开头加两行：

ios::sync_with_stdio(false); cin.tie(nullptr);

这两行能让cin和scanf速度接近，是蓝桥杯必备写法。千万别漏，漏了就是白丢的分。

如果加了加速还TLE，就要检查算法复杂度。比如n=10⁵、m=10⁵的稠密图，用邻接矩阵肯定炸；Dijkstra用未优化版本O(n²)也可能超时。这时候优先确认存储是不是邻接表、优先队列是不是小顶堆。

还有个容易被忽略的点：多组测试数据时，记得每次初始化vector和dist数组。清空vector用for (int i = 1; i <= n; i++) g[i].clear();，dist用fill(dist + 1, dist + n + 1, INF)，比memset更准确，因为memset是按字节填充，处理0x3f没问题，但处理-1以外的值容易出错。

5.4 边界样例：图论题最容易漏的测试点

我复盘真题时总结出几个高频边界，建议每次写完代码都主动测一下：第一个是只有一个顶点且没有边的图，DFS和BFS必须能输出这个顶点；第二个是重边和自环，自环不能导致死循环，所以visited标记必须在入队/入递归前设置；第三个是无向图两条方向都要存，漏了半边会导致答案偏小；第四个是n=1时拓扑排序的输出，应该是这个唯一节点而不是空。

还有一个经常出问题的点：题目里顶点编号从0还是从1开始。蓝桥杯大多从1开始，但偶尔有从0开始的，如果你用1到n跑循环，0号顶点被漏掉，连通块计数就会错。我习惯先看样例，确认编号规则再写循环边界。

最后再分享一个我自己的小习惯：每道图论题写完，我都会构造一个最简单的例子——两个点一条边，先跑一遍验证基本逻辑，再跑一个稍大的随机数据验证复杂度。这个习惯帮我省下了无数次调试时间，也让我在赛场上遇到段错误时能从"数组越界、递归爆栈、访问未初始化"三个方向快速排查。图论是你接触的第一类需要抽象建模的题目，DAY6把这些基础模板写熟、把坑踩完，后面学动态规划和更复杂的算法时，你会感谢今天这个扎实的开始。