简介这是一份面向算法学习者的图解数据结构笔记聚焦“图”这一复杂非线性结构。内容从图的定义出发系统梳理无向图、有向图、邻接点、顶点的度、完全图、子图、路径与回路、连通分量、强连通分量以及带权值的网等核心概念并对比邻接矩阵与邻接表两种存储方式的优缺点。资源附有C#实现的邻接矩阵结构代码与创建图的完整示例便于读者理解如何用二维数组保存顶点和边信息为后续学习深度优先搜索、广度优先遍历、最短路径及最小生成树打下基础。资源为PDF格式共1个文件压缩包大小97KB轻量易读适合正在入门图论或准备算法面试的程序员快速回顾要点。目前已有188人学习下载内容精炼实用可帮助学习者用较短时间掌握图的基本框架和存储建模思路。1. 算法速成第十四天为什么树的套路到图里会集体失灵算法系列15天速成进行到第十四天今天啃的是图Graph。前十三天你攒下的数组、链表、树的套路到了图这里会先失灵一半树有根、有层级、没有环图却有环、有孤立顶点、还分有向无向连「这图该怎么存」都是一道选择题。这篇是「图【上】」只干三件事把一张图存进程序、写深度优先遍历DFS、写广度优先遍历BFS。三件事吃透下篇的最短路径和拓扑排序才接得住。适合刚学完树想趁热打铁的人也适合面试前快速过一遍图遍历模板的熟手。2. 建图第一步邻接矩阵与邻接表怎么选、代码怎么落地图没有「根节点」也没有天然的父子层级所以不能像树那样只存左右孩子。存图本质上只回答两个问题点与点之间是否相连、相连的话边权是多少。围绕这两个问题业界最常见的方案就是邻接矩阵和邻接表。选错存储结构后面的遍历复杂度会差出一个数量级这一章就把两种方案讲透。2.1 邻接矩阵稠密图的最直观写法邻接矩阵是一个V x V的二维数组graph[u][v]表示从节点 u 到节点 v 的边。无向图的矩阵是对称的有向图则不一定。它最大的优点是判断两点是否相连只需要 O(1) 时间写起来也几乎不用动脑。我一般用vectorvectorint而不是定长二维数组因为很多题目不会在题目描述里直接给最大顶点数运行时动态分配更稳妥#include vector using namespace std; const int INF 1e9; // 表示两点之间不连通 vectorvectorint graph; // graph[u][v] 边权无权图存 0 或 1 void initMatrix(int n) { graph.assign(n, vectorint(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 大约是 16MB5000² 就直接跑到 100MB 级别很多在线评测系统会直接判内存超限。2.2 邻接表稀疏图的主力存储邻接表的核心思想是每个顶点只存它「真正有边」的邻居而不是为所有可能的边预留位置。实现上就是vectorvectorEdgegraph[u]里存的是从 u 出发的所有边。这是竞赛和面试里最常用的写法没有之一。#include vector using namespace std; struct Edge { int to; // 这条边通向哪个顶点 int weight; // 边权无权图可以省去这个字段 }; vectorvectorEdge graph; void initList(int n) { graph.assign(n, vectorEdge()); // 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, vectorEdge())这一步不能省否则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; vectorvectorint graph; vectorbool 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; vectorvectorint graph; vectorint state; // 0未访问, 1访问中, 2已结束 vectorint 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; vectorvectorint graph; vectorint dist; // 起点到各点的距离-1 表示还没访问到 void bfs(int start) { dist.assign(graph.size(), -1); queueint 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; vectorvectorint graph; vectorint 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、环检测三个功能正确。做完这个验证你就可以自信地进入下一章「图【下】」了。最后说个我的习惯每次写完图遍历代码我都会拿一个带环的图和一个不连通的图各跑一遍。这个习惯帮我挡掉了无数次「样例过了、提交挂了」的尴尬。希望帮到你。本文还有配套的精品资源点击获取