★ FEATURED ARTICLE 啃到图这一章算是把《算法》这本书的分水岭真正趟过去了。前面学排序、学查找处理的都是“一个元素跟另一个元素”之间的关系到了无向图突然变成了“一堆元素互相之间都有关系”思维模式一下子就不一样了。无向图是图论里最基础也最常用的一块后面的有向图、加权图、最小生成树、最短路径全都是在它的骨架上长出来的。这篇笔记我会从图的表示开始把深度优先搜索、广度优先搜索、连通分量、环检测、二分图检测这几个核心内容一次讲透最后附上我实际写代码时踩过的坑。适合正在啃这本书的读者也适合准备面试想快速把图的基础捡起来的人。说实话图这个章节我第一次读的时候差点弃书因为代码量突然变大抽象程度也高。但真啃下来之后会发现图的算法套路其实非常固定核心就那么几个模板一旦理解了搜索过程本身剩下的全是在这个骨架上做变形。所以这篇笔记我不会照抄书里的代码而是把每个算法的“为什么”讲清楚再给一份可以直接抄的模板。1. 无向图的表示邻接表为什么是默认选择1.1 先搞清楚无向图的三个基础概念无向图由顶点和边组成区别就在于边没有方向。你可以把顶点想成是微信里的好友边就是互相关注的关系——你关注了我我肯定也关注了你不存在“我单向关注你但你对我不可见”的情况。在无向图里两个顶点之间有一条边我们就说它们是“相邻的”。一个顶点的度就是它身上连了多少条边对应到社交场景里就是你微信好友的数量。路径就是从一个顶点出发沿着边一路走到另一个顶点走过的顶点序列环则是起点和终点相同的路径比如三个人互相都认识就形成了一个三角形环。这些概念看起来很基础但它们是后面所有算法讨论的前提。比如度这个概念在判断一个图能不能存在欧拉路径时就要用到环检测就更不用说了后面会专门拿出一个小节来写。1.2 三种存储方案为什么最终选了邻接表随便翻开一本算法书图的存储逃不开三种方案邻接矩阵、边的数组、邻接表。邻接矩阵用V×V的布尔矩阵来记录顶点之间的连接关系matrix[i][j]为true表示顶点i和顶点j之间有边。这种方案最直观判断两个顶点是否相邻的时间复杂度是O(1)。但代价也很明显——需要V²的空间。当图有10000个顶点时就是要开一个一亿个元素的数组在很多场景下直接就不现实了。边的数组就更简单了把所有边存成一个列表每条边记录两个顶点。空间上倒是省了但想查询“顶点A的所有邻居”必须遍历整张边表效率低到没法用。邻接表是这两种方案的折中。它的主体是一个顶点数组数组的每个位置挂一条链表链表里存的是和该顶点相邻的所有顶点。判断两个顶点是否相邻需要遍历链表不如邻接矩阵快但空间上只存实际存在的边对于绝大多数稀疏图来说非常友好。实际在工程里邻接表几乎是默认选择。这也是《算法》这本书的示例代码里采用邻接表的原因并不是作者偏心而是在真实的图数据里绝大多数都是稀疏的——想想一个社交网络几亿用户每人平均几百个好友如果用邻接矩阵存储量直接天文数字了。1.3 邻接表的核心代码模板import java.util.ArrayList; import java.util.List; public class Graph { private final int V; // 顶点数 private int E; // 边数 private ListInteger[] adj; // 邻接表 public Graph(int V) { this.V V; this.E 0; adj (ListInteger[]) new List[V]; for (int v 0; v V; v) { adj[v] new ArrayList(); } } public int V() { return V; } public int E() { return E; } public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); // 无向图的对称性 E; } public IterableInteger adj(int v) { return adj[v]; } }这份代码本身就是无向图最核心的性质因为边没有方向所以添加一条连接v和w的边时必须同时把v加到w的邻接表里也把w加到v的邻接表里维护好这个对称性。很多新手写无向图算法出错根源就在漏掉了这个对称操作。另一个细节是我用ListInteger而不是链表在实际开发里灵活性和性能表现都不错。如果读的是原书它用的是Bag数据结构本质上也是链表你自己用ArrayList替代完全没有问题。2. 深度优先搜索递归其实是一种“走迷宫”2.1 核心思路就是标记加递归深度优先搜索DFS这个名字听起来很高端本质就是一个走迷宫的过程。想象你走进一个岔路很多的迷宫你的策略是随便挑一条路一直走到黑走到死胡同了就退回来换一条没走过的路继续走直到把所有路都走遍。计算机实现这个策略只需要两个要素一个布尔数组标记哪些顶点已经访问过以及递归这个函数调用机制。为什么需要标记因为图里可能有环如果不做标记你会在一个环里无限循环下去。这就好比你在迷宫里如果遇到一条走过的路还不回头就只能原地打转了。DFS的这个特性让它天然适合解决“有没有一条路从A到B”“从A出发能到达哪些顶点”“整张图被分成了几个互不相通的区域”这类连通性问题。2.2 DFS代码其实只有几行public class DepthFirstSearch { private boolean[] marked; // 标记已访问的顶点 private int count; // 与起点连通的顶点数 public DepthFirstSearch(Graph G, int s) { marked new boolean[G.V()]; dfs(G, s); } private void dfs(Graph G, int v) { marked[v] true; count; for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } } }这段代码短到有点让人不敢相信但它确实就是DFS的全部。核心逻辑就一句话每到一个顶点先标记自己然后遍历所有邻居只要邻居没被标记过就递归进去。递归返回的时候说明这个顶点的所有邻居路径都已经探索完了。我当初学这个的时候有一个疑惑递归调用返回之后函数里不是应该还有后续代码要执行吗这个循环里每个递归调用之间不互相影响吗答案是确实不影响因为每次递归进去都是独立的深度探索过程返回后继续执行下一个邻居的递归即可这就实现了深度优先的效果。2.3 从DFS到寻找路径用edgeTo数组记录来路光知道“从起点能到哪些顶点”还不够用很多时候我们需要具体路径从s到v到底经过了哪些顶点方法是在DFS的过程中用一个edgeTo数组记录“我是从哪个顶点来到当前顶点的”。public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; // edgeTo[v] 从起点到v的路径上v的前一个顶点 private final int s; // 起点 public DepthFirstPaths(Graph G, int s) { marked new boolean[G.V()]; edgeTo new int[G.V()]; this.s s; dfs(G, s); } private void dfs(Graph G, int v) { marked[v] true; for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] v; dfs(G, w); } } } public boolean hasPathTo(int v) { return marked[v]; } public IterableInteger pathTo(int v) { if (!hasPathTo(v)) return null; // 从v倒着往起点推借助栈反转顺序 java.util.StackInteger path new java.util.Stack(); for (int x v; x ! s; x edgeTo[x]) { path.push(x); } path.push(s); return path; } }这段代码的巧妙之处在于edgeTo[w] v恰好是在递归前执行的记录的是“通过v这个顶点第一次发现w”这个事实。DFS形成的路径树自然保证了从s到任意可达顶点的路径是存在的。有一个概念要特别强调DFS找到的路径不一定是最短路径。比如从A出发找C可能先走到了一条很长的岔路才到C而实际上C就紧挨着A。深度优先的特性决定了它会“一条道走到黑”所以路径长度和位置的优劣无关。如果需要保证最短就要用下一章要写的BFS了。2.4 递归深度带来的隐患DFS用递归实现虽然代码优雅但有一个实际问题当图非常大比如有几万个顶点的链状图时递归深度会非常深JVM的调用栈可能直接爆掉抛出StackOverflowError。这时候有两个选择。一是调大JVM的栈空间参数-Xss但这只是治标。二是把递归改写成显式的栈迭代版本自己维护一个StackInteger来模拟递归过程。后者代码会啰嗦一些但可控性更强。我自己的建议是刷题和学习阶段递归版本完全够用理解起来也更直接。如果到了处理真实海量图的工程场景再考虑改成迭代版。别一上来就追求“高性能写法”先把递归版本吃透因为后面的很多算法比如环检测、二分图检测、拓扑排序都是基于递归DFS的变形。3. 广度优先搜索无权图最短路径的标准答案3.1 一层一层向外扩散的队列思想和DFS不一样广度优先搜索BFS不是一条路走到黑而是像水波一样从起点开始一圈一圈往外扩散。你把一颗石子扔进平静的水面波纹是匀速往外扩散的BFS就是这么干的先访问起点然后是起点的所有邻居然后是邻居的邻居以此类推。这种“层层扩散”的特性决定了BFS首次到达某个顶点时走的路径一定是最短的。为什么因为第k层的顶点一定是通过最短的k条边就能到达的顶点BFS按层推进到达时就锁定了最短距离。BFS的实现需要一个队列FIFO的先后顺序保证了“先发现的顶点先被扩展”。这跟DFS用栈或者递归“后进先出”的特性正好反过来也是两者核心的行为差异。3.2 BFS代码实现与最短路径还原import java.util.LinkedList; import java.util.Queue; public class BreadthFirstPaths { private boolean[] marked; private int[] edgeTo; private final int s; public BreadthFirstPaths(Graph G, int s) { marked new boolean[G.V()]; edgeTo new int[G.V()]; this.s s; bfs(G, s); } private void bfs(Graph G, int s) { QueueInteger queue new LinkedList(); marked[s] true; queue.add(s); while (!queue.isEmpty()) { int v queue.poll(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] v; marked[w] true; queue.add(w); } } } } // hasPathTo和pathTo方法与DFS版本完全一致 }注意BFS里标记顶点是在入队的时候做的而不是出队的时候。这是个非常关键的性能细节。如果在出队时才标记同一个顶点可能被多个邻居重复加入队列导致大量冗余计算在最坏情况下队列可能会变得非常大。和DFS版本的对比代码结构最大的区别就是把递归换成了while循环加队列。edgeTo的赋值逻辑其实和DFS是一样的所以还原最短路径的pathTo方法可以直接复用倒着回溯就能拿到从起点到任意顶点的最短路径。3.3 DFS和BFS到底该怎么选这是面试和学习中最高频的问题我直接给一个实用的对照维度DFSBFS核心数据结构递归 / 栈队列路径性质不一定最短无权图首次到达即为最短空间占用栈深度与路径长度相关队列大小与当前层宽度相关典型场景连通性、环检测、拓扑排序、回溯穷举最短路径、层次遍历、社交网络“几度好友”实际选型就一句话要最短路径用BFS只要判断“通不通”“有没有环”DFS更简洁。还有一种场景如果图特别深但很窄DFS的递归深度可能成为瓶颈如果图特别宽比如一个顶点连了一百万个邻居BFS的队列可能瞬间被撑爆。需要根据图的形状来权衡。我在做算法题的时候经常先想清楚问的是“路径最短”还是“可达性”这事关选DFS还是BFS很多时候题做不出来不是不会写代码而是根本没分清这个区别。4. 连通分量图里有多少个孤岛4.1 不要低估连通分量的价值如果一张图里有一部分顶点互相之间都能通过路径到达另一部分顶点跟它们完全不相连那么每一个“互不相通的最大区域”就是一个连通分量。你可以把整个图想象成一片群岛每个连通分量就是一座岛岛内的所有地方走路都能到但岛和岛之间没有桥。连通分量这个概念在工程里的应用非常广泛。比如判断一个网络是不是完全连通的如果连通分量数大于1说明存在网络分区图像处理里的连通区域标记用的也是这个思路社交平台判断用户群体是不是被分割成了多个互不交流的圈子同样可以建立在连通分量分析之上。4.2 用一次DFS搞定全图连通分量用DFS统计连通分量其实特别优雅从顶点0开始做一次完整的DFS能够标记所有和顶点0连通的顶点这样第一个连通分量就找到了。然后扫描所有顶点找到第一个还没被标记的顶点再从这个顶点做一次DFS这就是第二个连通分量。重复这个过程直到所有顶点都被标记。public class CC { private boolean[] marked; private int[] id; // 顶点属于哪个连通分量 private int count; // 连通分量总数 public CC(Graph G) { marked new boolean[G.V()]; id new int[G.V()]; for (int s 0; s G.V(); s) { if (!marked[s]) { dfs(G, s); count; } } } private void dfs(Graph G, int v) { marked[v] true; id[v] count; for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } } public boolean connected(int v, int w) { return id[v] id[w]; } }这里的id数组记录了每个顶点所属的分量编号。connected(int v, int w)就是最终极的用法判断两个顶点是否连通只需要O(1)时间比较它们的id是否相等。这个处理方式展示了图算法里一个很重要的思路把全图的静态信息预先计算好建好索引然后后续的每次查询都变成常量时间。很多看上去复杂的图问题其实都能通过这种预计算的思路化简。4.3 快速判断任意两个顶点是否连通有了CC类之后“任意顶点v和w是否连通”这个问题就变得非常简单。如果没有预先计算连通分量每次都要从头做一次DFS或BFS成本是O(VE)而用id数组预计算之后每次查询只是两次数组访问O(1)。这也是为什么我建议大家把这本书的代码自己敲一遍而不是只看。当你在实际项目里真正用到图的时候这种“预计算换查询速度”的思维方式比代码本身值钱得多它能迁移到很多其他场景比如判断两个用户是否在同一个群组网络里判断两个服务器节点是否在同一个可用区网络里全都是一个套路。5. 环检测与二分图检测两个绕不开的性质判断5.1 环检测最常见的翻车点判断一张无向图里有没有环思路朴素到让人容易出错。在DFS过程中如果访问到了一个已经被标记过的邻居而且这个邻居不是“从当前顶点出发时的上一个顶点”那么说明存在一条“回头路”图里就有环。为什么要排除父顶点因为无向图的边是双向的假设从A走到B那么B的邻居里一定包含A。如果在这里看到A已被标记就判断有环那么任何一条普通的边都会被误判为环。所以必须借助递归调用时的“前一个顶点”来排除这个假阳性。public class Cycle { private boolean[] marked; private boolean hasCycle; public Cycle(Graph G) { marked new boolean[G.V()]; for (int s 0; s G.V(); s) { if (!marked[s]) { dfs(G, s, s); } } } private void dfs(Graph G, int v, int parent) { marked[v] true; for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w, v); } else if (w ! parent) { hasCycle true; } } } }特别注意这里的循环处理方式是为了对所有的连通分量都进行环检测防止漏掉“孤岛”上的环。dfs(G, s, s)里把起点的父顶点设为自己这样第一个顶点的邻居里如果出现了别的已访问顶点就不会因为“等于父顶点”被误判。这个题目在面试中出现的频率非常高而且变形极多。解题的关键就是保留父顶点参数这是最容易写错的地方。我见过很多人写出了“发现任何已访问顶点就判定有环”的版本提交后错误百出。5.2 二分图检测染色法的魅力二分图检测是另一个经典的DFS应用。一个图是二分图意味着可以把所有顶点染成两种颜色使得每条边的两个端点颜色不同。说人话就是所有边连接的两个顶点永远是一黑一白不会出现同一个颜色内部相连的情况。这个性质有很强的现实背景。比如一个班级里男生和女生之间有关系男生内部没关系女生内部也没关系关系图天然就是二分图。再比如课程和时间段的冲突图某些调度问题也能建模成二分图判定。染色的过程就是DFS的变形从起点开始染成颜色0遍历邻居时如果邻居没被染过色就染成和当前顶点相反的颜色如果邻居已经被染过色了且颜色和当前顶点相同说明出现了冲突这个图不是二分图。public class TwoColor { private boolean[] marked; private boolean[] color; private boolean isTwoColorable true; public TwoColor(Graph G) { marked new boolean[G.V()]; color new boolean[G.V()]; for (int s 0; s G.V(); s) { if (!marked[s]) { dfs(G, s); } } } private void dfs(Graph G, int v) { marked[v] true; for (int w : G.adj(v)) { if (!marked[w]) { color[w] !color[v]; dfs(G, w); } else if (color[w] color[v]) { isTwoColorable false; } } } }这段代码只用了一个额外的color布尔数组就完成了二分图检测。布尔值天然只有两种状态恰好对应两种颜色。判断冲突的条件就是遍历到一个已染色的邻居时它的颜色跟当前顶点完全相同。我把二分图检测单独拿出来是因为它是DFS在“图的性质判断”上的典型代表。和环检测一样同样是遍历标记的模板只是把标记的内容从“是否访问过”换成了“颜色是什么”然后多了一条判定规则。图算法的大量题目其实都是在这个模板上做文章。6. 调试与避坑写图算法时最容易翻车的几个地方6.1 常见问题速查表代码写得越多踩的坑就越深。我把写无向图算法时最常见的几个问题整理成了一张速查表问题现象根本原因解决办法遍历邻居时抛空指针邻接表初始化遗漏构造时对每个顶点都初始化一个空列表图只有部分顶点被访问忘了循环处理所有顶点只在起点做了一次搜索环检测、连通分量等场景外层套一层for循环DFS死循环没有标记已访问顶点或标记逻辑写错位置进入顶点时立刻标记在递归前判断环检测误报把父顶点当成了环递归方法带上parent参数判断邻居等于父顶点时跳过BFS记录重复入队出队时标记而不是入队时标记入队时就设置marked为true顶点编号越界图是0-indexed但业务数据是1-indexed创建Graph前先确认顶点编号的约定这里的每一个坑我都真实踩过。尤其是第一个新建邻接表时忘了给每个顶点初始化结果一调用adj(v)就空指针Debug了半个下午才发现是最基础的问题。写代码时先把这些基础检查表过一遍比出错了再排查效率高得多。6.2 我的几个实操心得先说测试用例的构造。很多人写图算法喜欢拿书上的小图一跑就完事这其实远远不够。我自己测试时会故意构造几个特殊形状一个完全连通的环、一个带孤立顶点的图、一个包含多连通分量的图、一个宽度很大的图。这些边界情况能把算法里的逻辑漏洞暴露出来比单纯验证“能跑通”靠谱得多。再说性能层面的观察。当图的顶点数达到百万级别时如果使用递归DFS栈深度可能是压死骆驼的最后一根稻草。这时候需要用显式栈或改写BFS来规避。但反过来如果你在刷题或笔试阶段过度优化只会让代码变得难读难调先把正确性保证好再来谈性能。最后还有一个小技巧把图的邻接表打印出来做可视化。很多算法看起来抽象但当你把adj数组的内容按顶点一行行打印出来整个图的结构就清晰了调试时一眼就能看出邻接关系对不对、边有没有漏加。6.3 下一步可以往哪走无向图学完后很自然的延伸就是有向图。有向图里的边带了方向环检测的逻辑需要区分有向环和无向环拓扑排序、强连通分量比如Tarjan算法、最短路径算法Dijkstra、Bellman-Ford全都会在无向图的基础上进一步发展。我个人在学完这一章后最深刻的一个感受是无向图的所有算法本质上都是在DFS和BFS这两个搜索模板上做扩展。连通分量是DFS加一个计数数组环检测是DFS加一个父顶点参数二分图检测是DFS加一个颜色数组最短路径是BFS加一个edgeTo数组。理解了这层关系学到后面的有向图时你会发现处处都是熟悉的面孔。如果你也正在啃这一章我的建议是先别急着刷题把DFS和BFS这两个模板手写十遍写到闭着眼都能默写出来再往后面的章节走你会轻松很多。
阅读完成 · 觉得有帮助？
