简介：这是一份面向算法学习者的图解数据结构笔记，聚焦“图”这一复杂非线性结构。内容从图的定义出发，系统梳理无向图、有向图、邻接点、顶点的度、完全图、子图、路径与回路、连通分量、强连通分量以及带权值的网等核心概念，并对比邻接矩阵与邻接表两种存储方式的优缺点。资源附有C#实现的邻接矩阵结构代码与创建图的完整示例，便于读者理解如何用二维数组保存顶点和边信息，为后续学习深度优先搜索、广度优先遍历、最短路径及最小生成树打下基础。资源为PDF格式，共1个文件，压缩包大小97KB，轻量易读，适合正在入门图论或准备算法面试的程序员快速回顾要点。目前已有188人学习下载，内容精炼实用，可帮助学习者用较短时间掌握图的基本框架和存储建模思路。
1. 算法速成第十四天：为什么树的套路到图里会集体失灵
算法系列15天速成进行到第十四天，今天啃的是图（Graph）。前十三天你攒下的数组、链表、树的套路，到了图这里会先失灵一半：树有根、有层级、没有环，图却有环、有孤立顶点、还分有向无向，连「这图该怎么存」都是一道选择题。这篇是「图【上】」，只干三件事：把一张图存进程序、写深度优先遍历（DFS）、写广度优先遍历（BFS）。三件事吃透，下篇的最短路径和拓扑排序才接得住。适合刚学完树想趁热打铁的人，也适合面试前快速过一遍图遍历模板的熟手。
2. 建图第一步：邻接矩阵与邻接表怎么选、代码怎么落地
图没有「根节点」，也没有天然的父子层级，所以不能像树那样只存左右孩子。存图本质上只回答两个问题：点与点之间是否相连、相连的话边权是多少。围绕这两个问题，业界最常见的方案就是邻接矩阵和邻接表。选错存储结构，后面的遍历复杂度会差出一个数量级，这一章就把两种方案讲透。
2.1 邻接矩阵：稠密图的最直观写法
邻接矩阵是一个V x V的二维数组，graph[u][v]表示从节点 u 到节点 v 的边。无向图的矩阵是对称的，有向图则不一定。它最大的优点是判断两点是否相连只需要 O(1) 时间，写起来也几乎不用动脑。
我一般用vector<vector<int>>而不是定长二维数组，因为很多题目不会在题目描述里直接给最大顶点数，运行时动态分配更稳妥：
#include <vector> using namespace std; const int INF = 1e9; // 表示两点之间不连通 vector<vector<int>> graph; // graph[u][v] = 边权，无权图存 0 或 1 void initMatrix(int n) { graph.assign(n, vector<int>(n, INF)); // 默认全不连通 for (int i = 0; i < n; i++) { graph[i][i] = 0; // 自己到自己的距离是 0 } } void addEdge(int u, int v, int w) { graph[u][v] = w; // 有向图：只加这一条 // graph[v][u] = w; // 无向图：把注释打开，双向各加一次 }这段代码的重点在initMatrix里的双重assign：外层给 n 行，内层给每行 n 个元素。INF用来表示「不连通」，如果全部初始化为 0，就会把「无权」和「不连通」搞混。addEdge里我刻意留了一行注释，提醒无向图要双向建边，这个习惯能省掉后面排查的一整晚。
空间上邻接矩阵是 O(V²)，所以当顶点数 V 超过 2000 时就要警惕内存。2000² 个 int 大约是 16MB，5000² 就直接跑到 100MB 级别，很多在线评测系统会直接判内存超限。
2.2 邻接表：稀疏图的主力存储
邻接表的核心思想是：每个顶点只存它「真正有边」的邻居，而不是为所有可能的边预留位置。实现上就是vector<vector<Edge>>，graph[u]里存的是从 u 出发的所有边。这是竞赛和面试里最常用的写法，没有之一。
#include <vector> using namespace std; struct Edge { int to; // 这条边通向哪个顶点 int weight; // 边权，无权图可以省去这个字段 }; vector<vector<Edge>> graph; void initList(int n) { graph.assign(n, vector<Edge>()); // n 个顶点，每个顶点一个空列表 } void addEdge(int u, int v, int w) { graph[u].push_back({v, w}); // 有向图：只加一条 // graph[v].push_back({u, w}); // 无向图：再加一条反向边 }两个参数值得说明：Edge结构体里的to是必须的，weight在无权图里可以直接删掉，让结构体只剩一个int to，遍历时更快。graph.assign(n, vector<Edge>())这一步不能省，否则graph[u]是空容器，push_back会直接越界崩溃。
邻接表遍历某个顶点的所有邻居时，时间复杂度是 O(这个顶点的度数)，而邻接矩阵要扫描一整行 O(V)。对于稀疏图（边数远小于 V²），这是质变级的优化。
2.3 两种存储的取舍：一张表看懂
到底用哪个，不能凭感觉。我做题前会先看一眼输入规模，然后按下面的表快速决策：
| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(V²)，V 大就爆 | O(V + E)，稀疏图极其省 |
| 判断 u 和 v 是否相连 | O(1)，直接取下标 | O(度数)，需要遍历列表 |
| 遍历 u 的所有邻居 | O(V)，要扫一整行 | O(度数)，只走有边的 |
| 适合场景 | 稠密图、V ≤ 1000、频繁查连通性 | 稀疏图、V 到 10⁵、需要遍历邻居 |
| 代码难度 | 极低 | 中等 |
我的经验是：V 超过 5000 或者 E 明显小于 V²，直接无脑邻接表。只有 V 很小、又频繁需要判断「u 和 v 通不通」时，才用邻接矩阵图个省事。还有一种竞赛里常见的链式前向星写法，本质是用数组模拟邻接表，性能更好但代码更难读，速成阶段不建议优先接触，等邻接表写熟了再看不迟。
3. 深度优先遍历 DFS：递归模板与三个必须吃透的参数
DFS 的思路一句话就能说清：从起点出发，能往前走就一直往前走，走不动了再回头，换个方向继续。这种「一条路走到黑」的策略，实现起来比 BFS 短，但隐藏的参数细节更多，翻车率更高。这一章把递归版 DFS 拆开讲。
3.1 递归 DFS 的最小可运行模板
先看最朴素的版本。假设图已经用邻接表建好，我们只关心「能不能遍历到每个点」：
#include <vector> using namespace std; vector<vector<int>> graph; vector<bool> visited; // visited[u] = true 表示 u 已经访问过 void dfs(int u) { visited[u] = true; // 进来先标记，防止重复访问 for (int v : graph[u]) { if (!visited[v]) { dfs(v); // 没访问过的邻居，递归进去 } } } int main() { int n = (int)graph.size(); visited.assign(n, false); dfs(0); // 从顶点 0 开始，实际题目里起点由输入决定 return 0; }这段代码只有两个关键动作：标记自己、递归邻居。visited[u] = true必须写在函数第一行，不能等遍历完再标记。否则在无向图里，两个相邻节点会互相反复调用，直接栈溢出。dfs(v)的调用没有返回值，因为我们的目标只是「访问」，不是「计算」。
整个遍历的复杂度是 O(V + E)，每个顶点进一次、每条边被检查一次。这也是面试里最常问的递推点：为什么不是 O(V × E)？因为邻接表只遍历有边的邻居，不会扫描全表。
3.2 三个必须吃透的参数：起点、visited、递归深度
第一个参数是起点。图可能不是连通图，一次dfs(0)只能遍历起点所在的连通块。如果题目要求统计整张图，就必须在外层套循环，对每个未访问的顶点都调一次dfs。这个细节我在第 5 章还会展开讲，它是最容易漏的。
第二个参数是visited的语义。布尔值只区分「访问过/没访问过」，但有些题需要区分「正在访问中」和「访问结束」，这就要把bool升级成三色标记：0 表示未访问、1 表示在递归栈里、2 表示已经访问完。三色标记是后面学环检测和拓扑排序的地基。
第三个参数是递归深度。很多人小数据全对，一到 V = 10⁵ 就运行时错误，这就是递归栈爆了。系统给递归的栈空间有限，一条链状的图会让 DFS 递归到一万层以上。遇到这种情况，要么改用 BFS，要么用手写栈模拟递归。这是血泪经验，不是玄学。
3.3 DFS 的扩展信息：进入时间与离开时间
做一个很小的改动，就能让 DFS 额外输出两个重要的时间点：进入某个顶点的时间和离开它的时间。这两个时间戳是后面学习拓扑排序、桥和割点、强连通分量的基础，第十四天先混个脸熟。
#include <vector> using namespace std; vector<vector<int>> graph; vector<int> state; // 0=未访问, 1=访问中, 2=已结束 vector<int> tin, tout; // tin=进入时间, tout=离开时间 int timer = 0; void dfsWithTime(int u) { state[u] = 1; tin[u] = timer++; for (int v : graph[u]) { if (state[v] == 0) { dfsWithTime(v); } } state[u] = 2; tout[u] = timer++; }tin记录的是「第一次碰到这个点」的时刻，tout记录的是「它的所有子孙都访问完」的时刻。这两个值之间有重要的包含关系：如果tin[u] < tin[v] && tout[u] > tout[v]，那 v 一定在 u 的子树里。这个性质在判断「两个节点是否有祖先关系」时非常有用，树形 DP 里也经常出现。
4. 广度优先遍历 BFS：队列模板与层级信息的实际价值
BFS 的思路和 DFS 正好相反：不追求深入，而是从起点一圈一圈往外扩，先访问距离为 1 的所有点，再访问距离为 2 的所有点。这种「一层一层推开」的特性，让 BFS 天然适合求无权图的最短路径。
4.1 BFS 模板：队列加 dist 数组
#include <vector> #include <queue> using namespace std; vector<vector<int>> graph; vector<int> dist; // 起点到各点的距离，-1 表示还没访问到 void bfs(int start) { dist.assign(graph.size(), -1); queue<int> q; dist[start] = 0; q.push(start); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (dist[v] == -1) { // 没访问过才处理 dist[v] = dist[u] + 1; // 距离在当前点基础上 +1 q.push(v); } } } }这段代码里最核心的是dist[v] == -1这个判断。它同时承担了两个职责：判断是否访问过、记录起点到 v 的最短距离。用-1而不是false作初值，是因为 BFS 天然能给每个节点一个「起点到它要走几步」的数字，这个数字就是最短路径长度。
如果题目只关心连通性、不关心距离，可以把dist换成bool visited，逻辑完全一样。但要追求最短路径，dist数组就是必需品。
4.2 入队时标记还是出队时标记
这里有个特别隐蔽的坑：标记访问的时机。我见过不止一个 A 同学把dist[v] = dist[u] + 1写在q.pop()之后而不是q.push()之前。表面看没什么区别，实际会让同一节点被多次入队。
原因很简单：如果出队才标记，某个节点 v 可能被它的多个邻居依次发现，而每次发现时dist[v]都还是-1，于是 v 会被压进队列多次。等它终于出队时，dist[v]可能已经被一个绕远路的路径覆盖，结果完全错乱。
正确的做法是：压入队列的那一刻就标记。这一步做好，BFS 的时间复杂度才能稳定在 O(V + E)，否则最坏情况退化成 O(V × E)，在大数据量上直接超时。这个细节值得用一句话刻在脑子里：入队即标记，出队即处理。
4.3 BFS 的层级信息能做什么
BFS 的dist数组隐含了「层级」的概念：dist[v] = k表示起点到 v 的最短路径长度是 k。这个信息在无权重图的最短路问题是直接答案，在走迷宫、单词接龙、社交网络好友推荐这类题目里也是核心工具。
迷宫题里，每个格子是图的顶点，上下左右四个方向是边，BFS 从起点开始扩散，第一次扫到终点格时的dist就是最短步数。单词接龙题里，每个单词是顶点，只差一个字母的两个单词之间有边，BFS 扫到目标单词时即可返回层数。
DFS 也能做这些，但 DFS 找到的路径不保证最短，因为它是「一条路走到黑」再回头。这是 DFS 和 BFS 最本质的使用分界线：求最短路径用 BFS，求连通性和路径存在性用 DFS。记住这个分工，做题选型基本不会犯错。
5. 图遍历高频踩坑排查：五个反复出现的翻车现场
图这一章的知识点不算多，但每个考过试的人都会告诉你：图题的调试难度远高于排序和链表。下面五条踩坑记录，基本覆盖了新手到中级选手最常遇到的翻车场景，每条都按「现象 → 原因 → 解决」来写，可以直接对照排查。
5.1 无向图只建了单向边
现象：从起点遍历后，总有一部分顶点永远访问不到，visited数组里始终是false。数据量小的时候甚至看不出来，一换测试用例就错。
原因：addEdge(u, v)里只执行了graph[u].push_back(v)，忘了无向图要加反向边graph[v].push_back(u)。图的遍历沿着边的方向走，没有反向边，就回不到出发点。
解决：写addEdge时默认按无向图写双向，遇到有向题再删掉一行注释。建完图后打印一遍邻接表，肉眼确认每个对称关系都在。
5.2 DFS 递归爆栈
现象：小数据全部正确，V 一上 10⁵，程序在没有任何违反逻辑的情况下崩溃，提交报运行时错误而不是答案错误。
原因：递归深度等于图的纵深。一条链状的图会让 DFS 递归数万层，系统栈空间耗尽。
解决：优先换 BFS，很多 DFS 题目 BFS 一样能做。一定要 DFS 时，把手写栈迭代版本作为备选方案，或者用三色标记配合显式栈。
5.3 BFS 队列里出现重复节点
现象：dist值被越改越小或越改越大，答案混乱。打印队列长度发现远超顶点总数。
原因：把标记访问的代码写在了q.pop()之后。多个邻居在 v 尚未标记时都把它压进了队列。
解决：遵循「入队即标记」的原则，dist[v]的赋值和q.push(v)写在一起。这一条排查最快，但也是最容易反复犯的。
5.4 顶点编号从 1 开始，数组却开了 n 个
现象：程序运行不稳定，有时越界崩溃，有时某个顶点被莫名其妙跳过。
原因：题目里顶点编号是 1 到 n，但初始化邻接表时用的是graph.assign(n, ...)，导致编号 n 的顶点访问graph[n]时越界。
解决：无脑开n + 1，建图时下标直接用原始编号，遍历时也按 1 到 n。存储上多一个空位，换来的是不需要每次做u-1的偏移换算。
5.5 图不连通，只从一个起点遍历
现象：统计连通块数量或者查找所有点满足某条件时，结果偏小。
原因：dfs(0)或bfs(0)只能覆盖起点所在的连通分量。图可能是多个互不相连的分量，其他部分的点根本没被碰过。
解决：外层套一个循环，遍历所有顶点，发现未访问的就从它再触发一次遍历。代码如下：
int countComponents(int n) { int cnt = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { dfs(i); // 用前面写好的 dfs 模板 cnt++; } } return cnt; }这五条坑不是并列的，前两条是建图阶段的问题，后三条是遍历逻辑的问题。按从建图到遍历的顺序排查，一晚上能省下一半调试时间。
6. 上篇收尾技巧：用三色标记做环检测、用一次遍历数连通块
「图【上】」学到这里，你已经能建图、能 DFS、能 BFS。这篇的最后，我把两个最常用的验证型技巧给你：环检测和连通块计数。它们不需要学新知识，只用现有的 DFS 模板加一点点改动，却能解决一大类实际问题。
环检测的经典做法是给visited升级成三色。为什么布尔值不够用？因为在有向图里，从一个节点出发沿着边能回到它自己，这个「回」的过程需要识别递归栈中的节点，而布尔值只告诉你「访问过没有」，没法区分是递归栈中的还是已经结束的：
#include <vector> using namespace std; vector<vector<int>> graph; vector<int> color; // 0=未访问, 1=访问中, 2=访问结束 bool hasCycle(int u) { color[u] = 1; for (int v : graph[u]) { if (color[v] == 1) { return true; // 遇到正在访问中的节点，说明有环 } if (color[v] == 0 && hasCycle(v)) { return true; } } color[u] = 2; // 所有子孙都访问完，标记为结束 return false; }这个实现只多了一个color数组和一个判定分支。color[v] == 1意味着在本次递归链上碰到了自己，这就是环的充要条件。这套逻辑也是后面学拓扑排序判断「是否有解」的底子。
连通块计数就简单了，利用第 5 章的循环：每触发一次新的dfs，连通块数加一。配一张自己画的草图——三个互不相连的小团、一个三角形环、一条长链——跑一遍，能同时验证建图、DFS、环检测三个功能正确。做完这个验证，你就可以自信地进入下一章「图【下】」了。
最后说个我的习惯：每次写完图遍历代码，我都会拿一个带环的图和一个不连通的图各跑一遍。这个习惯帮我挡掉了无数次「样例过了、提交挂了」的尴尬。希望帮到你。
本文还有配套的精品资源，点击获取
