刷题打卡刷到第50天，正好碰到这道“可达路径”，编号是98。这个位置挺巧，前面刚把二叉树和回溯过了一遍，现在开始正式进入图论。不少人在这个阶段会有个共同感受：树的问题套路清晰，一入图就有点飘，因为图的结构比树自由太多——没有固定的“根”，没有“父节点”这个概念，甚至可能存在环。而“可达路径”这道题，恰好是图论入门的第一道坎，能把BFS（广度优先搜索）的基础打扎实，后面遇到最短路径、拓扑排序、岛屿类问题都会顺很多。
这篇文章我不会只讲一道题的解法，而是把它当成一个支点，把BFS的理论基础、代码实现、常见坑点一次性讲透。适合正在按清单刷题的人，也适合刚学完二叉树、准备进入图论但还有点虚的读者。如果你已经刷过一些图论题，可以直接跳到第5部分，那些坑点大概率对你有用。
1. 题目本质：从“能不能走到”到建图思维
1.1 题目说了什么
题目描述很直白：给定一个包含N个节点和M条边的图，节点编号从1到N，每条边连接两个节点，问从节点1出发，能否到达节点N。能到达输出1，不能到达输出0。
很多第一次看这道题的人会觉得有点简单过头了，这不就是顺着边往下找吗？但恰恰是这个“顺着边往下找”，涉及图论里两个最基本的问题：图怎么存，以及怎么遍历。
先看输入格式，通常是这样的：
5 5 1 2 1 3 1 4 2 5 3 5第一行是N M，表示N个节点、M条边。后面M行是具体的边，比如“1 2”表示节点1和节点2之间存在一条边。题目没有明确说是有向还是无向，这时候要看仔细，如果题目说“连接”，通常是双向连通的，建图时两边都要加；如果题目说“有向边”，那就只加一个方向。这个细节直接决定代码正确性，后面我会展开说。
1.2 为什么这类题目先考建图
图论题的第一步永远不是写遍历代码，而是把“关系”变成计算机能理解的数据结构。图的存储方式常见的有三种：邻接矩阵、邻接表、链式前向星。其中邻接表是最适合作为教学起点的，也是刷题时用得最多的一种。
邻接表的思路特别简单：对每个节点维护一个列表，列表里存的是它能直接到达的邻居。用C++的vector来实现，就是：
vector<int> graph[N + 1];graph[1]里存的就是节点1的所有邻居。比邻接矩阵省空间，而且遍历邻居时天然就是“我只关心和当前节点相关的边”，不会去扫描那些无关的节点。
选邻接表而不是邻接矩阵，主要原因是稀疏图。大部分刷题场景里，N可以到几千甚至几万，但边的数量M可能只有几万，用N*N的矩阵根本开不下。就算开得下，遍历时多出来的那部分无效操作也会拖慢速度。所以我的建议是：除非N非常小（比如50以内）且题目特殊，否则无脑用邻接表。
1.3 可达路径与其他题目的关系
这道题在很多刷题清单里被归为“图论入门”或“搜索基础”，因为它其实是一道“连通性检测”问题。连通性检测是图论里最底层的需求之一，后面你会遇到的许多问题都可以抽象成它或它的变体：
- 判断一个图是不是连通图
- 判断两个点之间是否存在路径
- 在迷宫中判断从起点到终点能不能走出去
- 社交网络里判断两个人之间是否存在关注链
所以别看这道题代码量不大，建图能力、搜索能力、对visited数组的理解都在这一题里得到了训练。把这道题吃透，比盲目刷10道类似题目都更有价值。
2. BFS理论基础：像水波一样扩散
2.1 核心思想：一层一层地摸
BFS的全称是Breadth-First Search，广度优先搜索。它的核心思想是：从起点出发，先访问离起点最近的节点，再访问更远的节点，一层一层向外扩散。
想象往水面扔一颗石子，水波不是直线跑出去的，而是以落点为中心，一圈一圈地往外扩散。BFS就是这种水波式的搜索方式。
具体到代码层面，BFS的本质是配合“队列”这个数据结构运转。队列是先进先出的，先入队的节点先被处理，这就保证了“先发现的节点先扩展”，也就保证了搜索顺序是从近到远。
2.2 队列在BFS里扮演什么角色
队列里存的是“当前已经被发现、但还没有被扩展”的节点。在BFS的过程中，每次从队头取出一个节点，把它的所有邻居中“尚未访问过”的节点标记为已访问，然后入队。这样，队里的节点永远是被搜索到的、但下一轮才轮到扩展的那一层。
用一个最简单的例子理解：起点是1号节点，1的邻居是2和3。最开始队列是空的，把1入队，标记1已访问。从队列取出1，查到1的邻居2和3都没访问过，把2和3都标记已访问并入队。接下来从队列取出2，扩展2的邻居……你会发现，1、2、3被访问的顺序，正好是按照离起点距离排序的。
这个“先来先服务”的顺序，恰恰是BFS区别于DFS的最关键特性。DFS是一条路走到黑，撞了南墙才回头；BFS则是地毯式推进，所有方向同步推进。
2.3 BFS与DFS的对比：为什么这道题两种都能做
从可达路径这道题来看，DFS（深度优先搜索）也可以做，而且代码可能更短，用递归几行就写完了。那为什么还要专门学BFS？因为后续很多问题只有BFS才是最佳选择，而DFS会很吃力甚至做不了。
我整理了一个对比表，方便你理解二者的区别：
| 对比维度 | BFS | DFS |
|---|---|---|
| 搜索策略 | 按层扩散，从近到远 | 一条路走到底，再回溯 |
| 数据结构 | 队列 | 栈（递归时用函数调用栈） |
| 能否找最短路径 | 能，第一次到达终点时即最短 | 不能保证，依赖搜索顺序 |
| 空间复杂度 | 大约与当前层节点数相关 | 大约与最深路径长度相关 |
| 适用场景 | 最短路径、层级关系、连通性 | 全路径枚举、回溯类问题、拓扑排序 |
对于“可达路径”这道题，BFS确实不是唯一解，但你在BFS里学到的“层”的概念，是后面解决“最短路径”问题的基础。因为你用BFS走迷宫时，第一次遇到终点的那一层深度，就是最短路径的步数——这个结论在后面经常会被用到。
2.4 时间复杂度分析
BFS的时间复杂度是O(N + M)，N是节点数，M是边数。为什么是这个结果？因为在最坏情况下，每个节点都会被访问一次（入队、出队各一次），每条边也会最多被检查一次（遍历某节点的邻居时）。这个复杂度在图中已经是最理想的级别了，因为你至少要读一遍所有节点和边才能确定连通性。
空间复杂度则是O(N)，主要消耗在visited数组和队列上。visited数组大小是N，队列在极端情况下最多也可能放N个节点，所以整体是O(N)。
3. 可达路径的BFS解法落地
3.1 完整代码（C++版本）
下面我给出一个完整可运行的BFS解法，核心逻辑都用注释标出来了。
#include <iostream> #include <vector> #include <queue> using namespace std; int main() { int N, M; cin >> N >> M; // 邻接表建图，节点编号从1开始，所以数组开N+1 vector<vector<int>> graph(N + 1); // 读入M条边 for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; // 注意：这里默认是无向图，所以双向都加 graph[a].push_back(b); graph[b].push_back(a); } // visited数组，标记是否访问过，避免重复入队 vector<bool> visited(N + 1, false); queue<int> q; // 起点入队 visited[1] = true; q.push(1); bool canReach = false; while (!q.empty()) { int cur = q.front(); q.pop(); if (cur == N) { canReach = true; break; } // 遍历cur的所有邻居 for (int next : graph[cur]) { if (!visited[next]) { visited[next] = true; q.push(next); } } } cout << (canReach ? 1 : 0) << endl; return 0; }这个代码已经可以直接跑过题目样例。下面我把几个关键细节拆开讲，这些都是新手容易出错的地方。
3.2 建图阶段：双向边别漏
这道题如果默认是无向图，那输入“1 2”意味着可以从1走到2，也可以从2走到1。所以建图时必须graph[a].push_back(b)和graph[b].push_back(a)两条都写。漏了任何一条，结果都可能不对。比如一条边“1 2”，如果漏了反向边，而终点N正好是2，从1出发就永远到不了2，直接输出0——这是很冤的一个错误。
3.3 入队即标记visited，这是BFS的黄金法则
很多人第一次写BFS时会写出这样的代码：取出节点时再判断是否访问过，或者取出时才标记visited。这会导致一个严重的问题：一个节点还没被取出，就已经被多个邻居加入队列了。
举个例子，假设节点5同时是节点3和节点4的邻居。在扩展3时，发现5没访问过，把5入队；在扩展4时，又发现5没访问过，再把5入队。此时队列里出现了两个5。虽然最终结果可能还是正确的，但效率变差，而且一旦图中存在环，队列里可能出现大量重复节点，甚至导致程序卡死。
正确做法是：在把节点入队的那一刻就标记visited。这样后续其他邻居看到它已经被标记，就不会再入队了。这也是BFS代码里最常见的一个细节考点。
3.4 提前终止优化
理论上，我们可以在遍历完整张图后才判断是否到达了终点，但没必要。当队列弹出某个节点等于N时，说明已经找到终点，可以提前跳出循环。这个优化对结果没有影响，但能省掉不必要的搜索，尤其在图比较大的时候收益明显。
3.5 关于起点与终点重合的情况
有一个容易被忽略的边界条件：如果题目里N等于1，也就是起点和终点是同一个节点，这时答案到底应该是1还是0？
从语义上说，从一个点出发当然可以到达它自己，所以答案是1。在我们代码里，起点1入队时标记visited，进入循环后取出cur=1，直接判断cur==N成立，打印1，逻辑是正确的。但如果有些题目规定“需要经过至少一条边”，那就要额外判断。刷题时要养成读题的习惯，这种一眼看过去很简单的边界，反而最容易被坑。
4. DFS解法对照与选型分析
4.1 递归实现DFS版本
BFS写完之后，我建议你顺手把DFS版本也写一遍。不仅是为了对比，也是在训练“一题多解”的意识。DFS的代码长这样：
#include <iostream> #include <vector> using namespace std; vector<vector<int>> graph; vector<bool> visited; bool canReach = false; void dfs(int node, int target) { if (node == target) { canReach = true; return; } visited[node] = true; for (int next : graph[node]) { if (!visited[next] && !canReach) { dfs(next, target); } } } int main() { int N, M; cin >> N >> M; graph.resize(N + 1); visited.resize(N + 1, false); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } dfs(1, N); cout << (canReach ? 1 : 0) << endl; return 0; }DFS的代码确实更短，因为递归天然替你管理了“回溯”的栈。但递归也有它的代价：递归深度过大时可能导致函数调用栈溢出。对于这道题，如果N比较大，且图是一条链状结构，递归深度可能达到N的数量级，在某些平台上会直接爆栈。题目如果给了限制，优先BFS更稳。
4.2 BFS和DFS在这道题上的微妙差异
可达路径只关心“能不能到”，不关心“怎么到”，所以BFS和DFS在正确性上没有本质差别。但如果题目稍微变形，比如“输出从1到N的最短路径长度”，BFS就成了更自然的选择，因为BFS第一次到达终点时的层数就是最短路径长度。DFS如果想要输出最短路径，反而要遍历所有路径才能确定哪条最短，复杂度是指数级的。
在做这道题的时候，建议你思考一个问题：如果要求输出路径本身，BFS怎么记录前驱节点？这个问题留个钩子，等后面遇到最短路径题时你会回来感谢现在的思考。
4.3 什么时候必须用BFS，什么时候用DFS
给出一个简单粗暴的选择原则：
- 题目问“最短”、“最少步数”——优先BFS
- 题目问“是否存在”、“能否到达”——BFS和DFS都行，选你顺手、不容易写错的
- 题目问“一共有多少种路径”——通常DFS（因为要枚举所有可能路径）
- 题目问“按什么顺序输出”——看具体要求，有时DFS，有时BFS
这道题属于第二种，所以选BFS更稳妥，因为BFS的模板更统一，写起来不容易出错。而且你既然已经在学BFS，就别在简单题里面偷懒用DFS逃避掉队列的练习。
5. 常见问题与排查技巧实录
5.1 visited标记的位置问题
前面已经反复强调：入队即标记。这里再举一个反例说明后果。
int cur = q.front(); q.pop(); if (!visited[cur]) { visited[cur] = true; // 处理邻居... }这种写法的问题在于，如果两个不同的节点都把同一个邻居加入队列，那这个邻居在队列里会出现两次。当它第一次被取出时，visited[cur]为false，正常处理；第二次被取出时，visited[cur]已经是true，跳过处理。结果虽然可能对，但队列中多出不少冗余节点，复杂图里性能会明显下降。还有一种更隐蔽的情况：如果你在弹出时标记visited，那某个节点可能在入队前就被同时多个邻居加入，导致队列里大量相同节点，最终可能因为重复节点太多而超时。
5.2 邻接表忘开N+1导致越界
节点编号如果从1开始，数组一定要开N + 1。新手经常只开N，访问graph[N]时就越界了。在本地可能不会立刻崩溃，但提交到平台时可能随机出现“运行时错误”。排查时优先看是不是数组越界问题。解决方案：所有与节点编号相关的容器，一律N + 1起步，别省这个1。
5.3 图里可能有自环和重边
自环是“a到a”的边，重边是两条完全相同的边。在邻接表里，重边会导致同一个邻居被push两次，但由于visited的存在，BFS不会重复入队，所以不影响正确性。自环也一样，graph[a]里包含a自己，visited[a]已经是true，直接忽略。
不过，如果题目给定的图极大，为了省内存，建图时可以顺手去重，比如用set代替vector存邻接表，或者push时遍历一遍判断是否已存在。但对这道题来说，其实没必要，visited数组已经天然去重了。
5.4 无向图 vs 有向图：一个字母的惨痛教训
这是我实际刷题过程中见过最多的错误。题目如果是无向图，按有向图建，答案基本会错一半；反过来，有向图按无向图建，会把本来不通的路径“打通”。所以做图论题的第一步永远是先搞清楚图的方向性。输入格式里如果写“u v之间有一条直接连接”，多半是无向；如果写“存在从u到v的边”，多半是有向。拿不准时可以看样例，试一下从反向能不能走到，推理题目设计者的意图。
5.5 大数据量下vector的开销问题
大多数情况下，vector<vector<int>>的邻接表写法完全够用。但如果N特别大，比如到10万级别，vector的自动扩容和频繁push_back可能会产生一定开销。此时可以考虑用vector<int> graph[N + 1]固定数组，或者提前reserve。不过这类优化在这道题里属于过度设计，知道有这回事就行。
5.6 实测排查流程参考
如果你提交后遇到错误，我提供一个排查顺序建议：
- 先确认建图方向：无向图是否两边都加边了
- 再检查visited初始化大小：是不是N+1
- 检查读入循环：M条边是否全部读对
- 输出前确认数据类型：是输出1/0，不是路径长度
这样一个一个过，基本上能覆盖大部分低级错误。
6. 扩展思考：从这道题还能带出什么
6.1 从BFS到最短路径：只需要加一个数组
这道题学完，最有价值的扩展就是最短路径问题。你只需要在BFS的基础上增加一个dist数组，用来记录每个节点到起点的步数。每当一个新节点入队时，dist[next] = dist[cur] + 1。当第一次到达终点时，dist[终点]就是最短距离。这是后面很多经典题目的底层逻辑。
6.2 从可达路径到岛屿类问题
网格类问题里的“岛屿数量”、“腐烂橘子”、“迷宫最短路径”，本质都是图上的搜索问题。网格本身就是一个天然的图，每个格子是一个节点，上下左右相邻的格子是边。学会了BFS，这类题目只需要把“邻居”的获取方式改成四个方向的偏移量即可。模板不变，变的只是建图的方式。
6.3 从这道题到拓扑排序
拓扑排序处理的是有向无环图，核心是不断找出度为0的节点。虽然拓扑排序用的是队列思想，但它并不是标准的BFS——它不按“距离”扩散，而是按“依赖关系”推进。不过，掌握BFS之后理解拓扑排序的队列操作会轻松很多，因为它们都是“用队列维护一个待处理集合”。
回过来看“Day50 ＞＞ 98、可达路径 + 广度优先搜索理论基础”这个标题，核心价值不在于这道题本身多难，而在于它给你划了一条线：从树到图的跨越，从递归到队列的跨越。把BFS的模板吃透，遇到图论题就先有了一根主心骨。后面无论是并查集、最小生成树，还是网络流，你都会发现它们建立在搜索的基本功上。
我个人在刷这道题时最大的体会是：不要只满足于写出代码跑通样例，建议顺手把DFS版本也写了，再对比两者的访问顺序；再试着改出最短路径版本，最后再看看如果题目变成有向图，代码哪里要改。这一套折腾下来，一道简单题也能榨出好几道题的价值。刷题打卡到第50天，真正拉开差距的不是谁刷得多，而是谁把题目嚼得更透。
