1. 从“关系”说起先搞懂无向图到底在解决什么问题如果你学过前面的排序、查找、二叉树你会发现它们其实都在处理一个问题把数据组织成一维或树形的结构。可现实世界的很多关系根本没法用一棵树来表达——比如你一定用过社交软件A是B的好友B是C的好友但A和C可能完全不认识这种“好友关系”就是一张典型的图而且是无向图。再比如地图导航里的道路、电路板上的元器件连接、论文引用网络都天然是图的结构。可以说一旦你开始研究“对象与对象之间复杂的联系”数组、链表、树就不够用了图才是那个能承载复杂关系的容器。无向图是图里最简单的一种形态边没有方向。你和我是好友那我和你也必然是好友这条关系是双向的。别小看这个“简单”它是后续理解有向图、加权图、网络流等所有进阶内容的地基。《算法》这本书在第四章开头用了很大篇幅讲无向图我的笔记走到这里也想把这块彻底吃透。这篇笔记适合什么人如果你刚学完链表、栈、队列、二叉树这些基础数据结构想正式进入图论的世界或者你刷题时总碰到深度优先搜索、广度优先搜索却知其然不知其所以然那这篇笔记的定位就很适合你。我会把无向图的表示、搜索、连通性判断、环检测、二分图判定这些东西串起来讲附带可以直接跑的代码和踩过的坑尽量让你看完不仅懂原理还能自己动手实现一遍。图的问题一个非常突出的特点是表示方法决定了后续所有算法的复杂度。所以第一步不是急着写搜索而是先把“怎么把一个图存进内存里”这件事想明白。2. 图的存储邻接矩阵和邻接表该怎么选2.1 两种表示方式的基本形态先明确几个术语后面全都用得上。图由两个集合组成顶点集合V和边集合E。无向图里每一条边就是两个顶点之间的连接比如顶点0和顶点1之间有一条边记作(0, 1)。在有向图里这条边是有方向的但无向图里这条边同时代表了0连1和1连0。第一种存储方式是邻接矩阵。用一个二维布尔数组matrix那么matrix[i][j]直接表示顶点i和顶点j之间是否存在边存在就置true。这个办法非常直观甚至不需要解释。第二种是邻接表。为每个顶点维护一个列表列表里放这个顶点直接相邻的所有顶点。比如顶点0连着1、2、3那顶点0的链表里就存1、2、3这三个数字。下图这种径向结构很多资料里也直接画成每个顶点后面挂一串邻居。我强烈建议直接选邻接表理由你看完这个对比就明白了。2.2 空间复杂度的量级对比先给一个小规模例子假设图里有V个顶点、E条边。无向图的一条边会在邻接矩阵里占两个存储位因为matrix[i][j]和matrix[j][i]都要记录所以邻接矩阵的空间是V的平方。而邻接表只把每条边存一次严格说也是两次因为无向图会在两个顶点的链表里各出现一次但总存储量是V2E的量级。用一个具体数字感受一下。假设V10000E50000。邻接矩阵要开10000乘10000的bool数组哪怕每个bool按一个字节算那也是1亿字节约100MB。而邻接表呢每个链表节点存一个int大概8个字节节点指针加int值简化估算50000条边产生100000条记录加起来也不过几MB。一百倍以上的差距而且顶点数量越大差距越是恐怖。到百万顶点级别的图邻接矩阵直接就爆内存了邻接表还能轻松存活。还有一个隐藏问题对稀疏图来说真实世界里的社交网络、道路网基本都是稀疏图邻接矩阵里有绝大多数的格子都是false纯属浪费。你可能觉得邻接矩阵查两个顶点是否相连只要O(1)快。但图算法里这种单点查询经常不是瓶颈更大的瓶颈是遍历一个顶点的所有邻居邻接矩阵这时候要扫一整行V个位置邻接表直接顺着链表走就行。后者在稀疏图上的效率优势非常明显。2.3 邻接表的Java实现代码《算法》书里用的Bag背包也就是只支持添加元素、不支持删除的集合来存邻居我用更常见的ArrayList也一样核心代码是这样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]; } }addEdge这里就体现了无向图的关键一条边必须同时在两个顶点的邻接表里出现。很多新手写无向图的addEdge时只加了一边调试半天发现路径怎么都不对。这个细节我在后面故障排查里还会专门说。还有一个小细节构建图的时候如果事先知道不会重复加边可以在addEdge里不做重复检查这样能省掉一个O(度)的扫描。如果你要处理重复输入的测试数据那就得先检查一遍或者干脆用Set作为邻接表的数据结构。现实中我一般先用Set去重等数据干净了再转回ArrayList因为Set的迭代顺序不稳定会对结果的可复现性造成干扰。3. 深度优先搜索一条路走到黑撞墙才回头3.1 迷宫思维与三个关键问题深度优先搜索DFS是图算法里的基础工具。我习惯把它想象成走迷宫从入口出发随便挑一条岔路一直走实在走不通了就退回到上一个岔路口换一条路继续走。这个“退回”动作在程序里就是递归回溯。在正式写代码前先问自己三个问题第一个从起点出发能到哪些点这是连通性判断属于DFS最简单也最核心的用途。第二个走的过程中是否经过了重复的点没有visited标记的DFS会在环里无限循环。无向图里天然就有环的情况哪怕图里只有1和2两个点之间有一条边从1出发访问2再从2又回到1如果不做标记递归就永远停不下来。第三个能不能把走过的路径记录下来方便后续查从起点到某点的完整路线这就需要一个edgeTo数组记录每个顶点是从哪个顶点走过来的。这三个问题基本就是《算法》里Paths类的设计原型。先看代码从上到下逐段拆解。3.2 最简单的DFS实现与路径记录public class DepthFirstPaths { private boolean[] marked; // 是否已访问 private int[] edgeTo; // 记录路径edgeTo[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; DequeInteger path new ArrayDeque(); for (int x v; x ! s; x edgeTo[x]) { path.push(x); } path.push(s); return path; } }这段代码值得好好讲几遍。marked数组的作用是避免绕回已经访问过的顶点。注意这里的visited是从起点开始沿着可达路径逐步扩散的。如果某个顶点和起点不在同一个连通分量里那它永远不会被标记为true这个特性直接被hasPathTo用上了。edgeTo数组则像个隐形的路标。每当我们第一次发现顶点w时一定是通过某个顶点v的这个入口进去的于是记录edgeTo[w] v。等搜索全部结束想要从顶点v回溯到起点s就是沿着edgeTo一条一条往回走v → edgeTo[v] → edgeTo[edgeTo[v]] → … → s。用栈把它正过来就能打印出正向路径。这里有个极易踩的认知误区pathTo返回的路径不一定是最短的。DFS是一口气钻到底找到一条可行路径就记录了不会去比较哪条路更短。在这个例子中从顶点0出发邻接表里先访问1那路径就是0→1→…可要是另一条路0→4→…更短DFS根本不会发现。要保证最短路径就得用下一节讲的广度优先搜索。递归深度的问题也要提前有心理准备。如果图很大比如有几十万甚至上百万个顶点的链路结构递归会让调用栈爆掉。后面我会给一个非递归版本的写法。3.3 非递归DFS与递归版的重要区别显式用栈替代系统递归调用public void dfsIter(Graph G, int v) { DequeInteger stack new ArrayDeque(); stack.push(v); marked[v] true; while (!stack.isEmpty()) { int x stack.pop(); for (int w : G.adj(x)) { if (!marked[w]) { marked[w] true; // 如果要在第一次遇到w时记录路径 edgeTo[w] x; stack.push(w); } } } }仔细观察你会发现非递归版的访问顺序和递归版可能不一样。递归版会先顺着第一条分支一直走到头非递归版则由于栈的后进先出特性最后压进栈的那个邻居会先被弹出访问。这不是bug只是遍历顺序变了。如果对访问顺序有严格要求的场景比如要按照邻接表里的自然顺序输出遍历结果那非递归写法需要在压栈时反着压或者干脆统一用递归。在实际开发里我通常优先写递归版它和数学归纳法的思路完全一致代码短、不易错。只有在明确知道递归深度会很大的情况下才切换成显式栈。4. 广度优先搜索层层推进拿到的是最短路径4.1 用队列实现的层层扩散广度优先搜索BFS走的是另一条路。它不追求“深”而是先扫平起点周边的一整圈再扫下一圈。这个过程可以想象成水面掉进一颗石子波纹一圈一圈往外荡。实现上只需要把DFS的栈换成队列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 ArrayDeque(); marked[s] true; queue.offer(s); while (!queue.isEmpty()) { int v queue.poll(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] v; marked[w] true; queue.offer(w); } } } } }队列的工作方式决定了BFS的特性先入队的顶点先处理。起点先入队随后它的所有邻居入队再随后邻居的邻居入队。因为队列先进先出所以第k圈的顶点一定会在第k1圈的顶点之前被访问这是BFS能找到最短路径的根本原因。为了方便理解拿一个简单图走一遍。假设起点是0邻接表里0连1和2。队列初始是[0]。弹出0把1和2入队变成[1, 2]edgeTo[1]0edgeTo[2]0。弹出1如果1又连着3那就把3入队edgeTo[3]1。弹出2如果2也连着3因为3已经marked了不会重复入队。到这里你会发现从0到3的路径有两条分别是0→1→3和0→2→3但你记录的是edgeTo[3]1也就是第一条被发现的路径。因为层次相同哪条都是最短的。4.2 BFS和DFS的核心权衡选择障碍往往出现在这里DFS代码短、思路直BFS代码也不难区别只在一个数据结构。那么到底用谁我给自己定的规则是需要找“是否存在一条路径”时用DFS因为往往只要找到就有答案不一定需求最优需要找“最短路径”或者“最少步数”时用BFS因为BFS严格按层推进。在无向图的很多实际场景里比如社交网络里两个人之间的最短好友链地铁换乘最少次数BFS就是直观且高效的选择。它的缺点是空间占用可能比DFS更大因为队列里存的都是同一层的顶点如果图很“宽”队列会瞬时膨胀。而DFS只需要显式栈存一条深入路径即可。把这两个方案都实现一遍就会发现一个有意思的事除了容器从栈换成队列以及压入时机略有不同代码骨架高度相似。这也是算法学习中很常见的情况——理解了底层的数据结构差异很多算法都是换汤不换药。5. 连通分量把一张图拆成几块彼此独立的区域5.1 连通分量和DFS的第一次配合还记得前面说的那个问题吗从一个点出发DFS能到达的点就是它所在的连通块。如果图里有多个连通块那么一次DFS就只能标记其中一个块。这时候我们需要对每个顶点都做一次“从它出发”的判断就能把整张图分成若干连通分量。连通分量的一个直观理解一张图里有的顶点和顶点之间有路相连有的之间隔着一条不可逾越的鸿沟每个能互相到达的团体就是一个连通分量。这个关系让我想起班级分组一个组的同学之间可以互相递纸条另一个组的同学完全接触不到第一个组的同学。要快速判断两个顶点是否在同一组连通分量算法节省了每次都做全图搜索的浪费。直接上代码public class ConnectedComponents { private boolean[] marked; private int[] id; // 顶点所属连通分量编号 private int count; // 连通分量数量 public ConnectedComponents(Graph G) { marked new boolean[G.V()]; id new int[G.V()]; for (int v 0; v G.V(); v) { if (!marked[v]) { dfs(G, v); 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]; } public int count() { return count; } }这个算法的工作流程其实就是从编号最小的未访问顶点开始做DFS把能到达的顶点的id全部设为当前的count然后count1。之后再找一个未被标记的顶点重复这个过程。到最后id数组里同一个连通分量的顶点编号相同count就是连通分量总数。这个算法比单独对每对顶点做一次DFS判断连通性要高效得多。判断一个图中v和w是否连通如果每次都重跑DFS那最坏情况是O(V*(VE))。但提前算好连通分量后面每次判断都只是O(1)的数组比较非常适合需要频繁判断的场景比如社交网络里的好友关系判断。在处理真实图数据时连通分量的数量、每个分量的大小分布也能反映图的宏观结构。比如一个网络中如果有一个巨大的连通分量占比接近100%而其他都是孤立的零星小分量那说明整个网络的核心高度连接。5.2 无环图的判定其实是“邻居跟踪”无向图里“环”的定义很简单从某个顶点出发能沿着边不重复地绕一圈回到自己。检测一张图是否包含环是深度优先搜索一个非常自然的应用。DFS过程中有两种回边第一种是回到父节点比如从顶点a走到邻居b再通过b试图访问a。这条边是刚才来时的那条边不算环。第二种是回到一个已经访问过的、又不是父节点的顶点那一定意味着存在环。实现时给方法增加一个参数parent递归调用时把当前节点传进去。这样在遍历邻居时就能区分开“父节点回边”和“真正的环”public boolean hasCycle(Graph G) { marked new boolean[G.V()]; for (int s 0; s G.V(); s) { if (!marked[s]) { if (dfs(G, s, s)) return true; } } return false; } private boolean dfs(Graph G, int v, int parent) { marked[v] true; for (int w : G.adj(v)) { if (!marked[w]) { if (dfs(G, w, v)) return true; } else if (w ! parent) { // 遇到已访问且不是父节点说明存在环 return true; } } return false; }这里有个容易出错的地方初始化的时候如果将parent设成-1有的人判断回边时忘了排除父节点导致在最简单的一条边上就误判有环。我习惯在调用时传s作为parent这样从起点开始的那条边也会被正确排除。5.3 二分图判定染色法里藏着搜索的又一面貌二分图这个名称在现实里到处都是。想象一个“相亲匹配”场景左边是男生右边是女生边代表“互相有意”。男生和男生之间没有边女生和女生之间也没有边这个图就是二分图。判断一幅图是不是二分图最经典的算法叫染色法原理也极其简单给每个顶点涂上黑或白两种颜色要求相邻顶点的颜色必须不同。实现就是在DFS遍历时给顶点赋颜色一旦遇到一条边的两个端点颜色相同就说明这张图不是二分图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; } } } public boolean isBipartite() { return isTwoColorable; } }结合交点经验说个实用点如果考试或面试让你判断无向图是否为二分图你完全可以不用递归DFS改用BFS来做本质一样只要保证“每一对相邻顶点颜色不同”这个约束在全局成立即可。如果图由多个连通分量组成要记得对每个分量都做一次判定只处理一个分量判断不出来。6. 实操中的几个大坑与调试心得6.1 邻接表漏加对称边Bug会非常隐秘我第一次写无向图的addEdge时只写了adj[v].add(w)忘了adj[w].add(v)。结果单个图看起来没事两个顶点一条边的极简场景也能工作但一旦跑DFS路径记录就发现从1出发找不到0而从0出发能找到1。这种不对称现象就是无向图邻接表漏加对称边的典型症状。排查方法是打印每个顶点的邻接表检查每条边是否在两个端点的邻居里都出现。有经验的开发者经常会用这个打印步骤来验证图的构建是否符合预期。6.2 递归爆栈在不同数据规模下会突然发生DFS的递归深度和图的结构密切相关。最坏情况是一个“线性图”比如0连11连2一直到千万级别的顶点。这时候递归深度就等于图的直径JVM默认栈深度根本扛不住程序直接抛StackOverflowError。如果你要处理大型图直接把DFS改成显式栈版本最稳妥别心存侥幸。也可以在递归里做深度检查超过某个阈值就抛出业务异常或者切换非递归逻辑但这属于补丁方案不如一开始就选定正确的实现方式。6.3 别忽略图的数据输入规模很多人在刷题或处理真实数据时看到顶点数V10^5边数E310^5仍用邻接矩阵结果内存直接爆掉。你可以提前估算一下邻接矩阵需要的字节数大约是VV/8如果用BitSet或者VV如果用boolean数组。V10^5时VV10^10等于百亿级别无论如何都不可行。邻接表的空间大约为V2E个引用这个量级在百万级都还好。先估算数据规模再选数据结构是图算法里非常实用的前置习惯。6.4 路径记录用数组还是Map怎么选前面的代码里edgeTo用的是int数组前提是顶点编号正好是从0到V-1的连续整数。现实中很多数据并不是这样比如顶点编号是字符串城市名、用户ID或者离散的大整数。此时更通用的做法是用MapMapString, String edgeTo new HashMap();好处是可以直接用真实ID作为键不需要额外做映射。缺点是自动装箱、哈希计算都会带来额外开销。对于性能敏感的千万级数据还是建议先把顶点重新映射为连续整数编号计算完成后再映射回去。这个“符号表映射”的做法就是后面符号图那一节要讲的东西。6.5 多个连通分量的搜索记得外面对每个分量都要跑做深度优先搜索的经典失误就是只从一个起点s调用dfs(G, s)然后如果图不是全连通那些在其他分量的顶点从来没有被标记过。后面调用hasPathTo当然返回false可你根本不知道false是因为路径不存在还是因为根本没搜过。连通分量那一节给出的遍历所有顶点的for循环就是处理这种情况的标准写法。我建议在做任何“全图分析”类的算法时都默认对每个未被标记的顶点执行一次搜索流程。7. 无向图的进阶话题与后续笔记的预告无向图还有不少值得继续挖的点比如符号图用字符串作为顶点名的图、欧拉路径一笔画问题、以及最大连通分量统计。这些内容本质上还是建立在DFS和BFS之上。比如欧拉路径的判断核心就一条一个无向连通图存在欧拉路径当且仅当有0个或2个顶点的度为奇数。这个结论用DFS走一遍同时统计所有顶点的度数立马就能算出来。符号图那个话题其实更适合在有向图之后一起讲因为很多真实场景网页超链接、任务依赖天然是有向的。等我有空把有向图的笔记也写出来两者放在一起对比很多概念会一下子通透了。这套笔记整体风格是力求用最少的术语把事情讲明白同时给出能跑的代码因为我知道这类东西光看概念不走代码是记不牢的。如果你边看边把每个类敲一遍设几个简单图测试你的印象会比单纯阅读深很多。
1. 从“关系”说起先搞懂无向图到底在解决什么问题如果你学过前面的排序、查找、二叉树你会发现它们其实都在处理一个问题把数据组织成一维或树形的结构。可现实世界的很多关系根本没法用一棵树来表达——比如你一定用过社交软件A是B的好友B是C的好友但A和C可能完全不认识这种“好友关系”就是一张典型的图而且是无向图。再比如地图导航里的道路、电路板上的元器件连接、论文引用网络都天然是图的结构。可以说一旦你开始研究“对象与对象之间复杂的联系”数组、链表、树就不够用了图才是那个能承载复杂关系的容器。无向图是图里最简单的一种形态边没有方向。你和我是好友那我和你也必然是好友这条关系是双向的。别小看这个“简单”它是后续理解有向图、加权图、网络流等所有进阶内容的地基。《算法》这本书在第四章开头用了很大篇幅讲无向图我的笔记走到这里也想把这块彻底吃透。这篇笔记适合什么人如果你刚学完链表、栈、队列、二叉树这些基础数据结构想正式进入图论的世界或者你刷题时总碰到深度优先搜索、广度优先搜索却知其然不知其所以然那这篇笔记的定位就很适合你。我会把无向图的表示、搜索、连通性判断、环检测、二分图判定这些东西串起来讲附带可以直接跑的代码和踩过的坑尽量让你看完不仅懂原理还能自己动手实现一遍。图的问题一个非常突出的特点是表示方法决定了后续所有算法的复杂度。所以第一步不是急着写搜索而是先把“怎么把一个图存进内存里”这件事想明白。2. 图的存储邻接矩阵和邻接表该怎么选2.1 两种表示方式的基本形态先明确几个术语后面全都用得上。图由两个集合组成顶点集合V和边集合E。无向图里每一条边就是两个顶点之间的连接比如顶点0和顶点1之间有一条边记作(0, 1)。在有向图里这条边是有方向的但无向图里这条边同时代表了0连1和1连0。第一种存储方式是邻接矩阵。用一个二维布尔数组matrix那么matrix[i][j]直接表示顶点i和顶点j之间是否存在边存在就置true。这个办法非常直观甚至不需要解释。第二种是邻接表。为每个顶点维护一个列表列表里放这个顶点直接相邻的所有顶点。比如顶点0连着1、2、3那顶点0的链表里就存1、2、3这三个数字。下图这种径向结构很多资料里也直接画成每个顶点后面挂一串邻居。我强烈建议直接选邻接表理由你看完这个对比就明白了。2.2 空间复杂度的量级对比先给一个小规模例子假设图里有V个顶点、E条边。无向图的一条边会在邻接矩阵里占两个存储位因为matrix[i][j]和matrix[j][i]都要记录所以邻接矩阵的空间是V的平方。而邻接表只把每条边存一次严格说也是两次因为无向图会在两个顶点的链表里各出现一次但总存储量是V2E的量级。用一个具体数字感受一下。假设V10000E50000。邻接矩阵要开10000乘10000的bool数组哪怕每个bool按一个字节算那也是1亿字节约100MB。而邻接表呢每个链表节点存一个int大概8个字节节点指针加int值简化估算50000条边产生100000条记录加起来也不过几MB。一百倍以上的差距而且顶点数量越大差距越是恐怖。到百万顶点级别的图邻接矩阵直接就爆内存了邻接表还能轻松存活。还有一个隐藏问题对稀疏图来说真实世界里的社交网络、道路网基本都是稀疏图邻接矩阵里有绝大多数的格子都是false纯属浪费。你可能觉得邻接矩阵查两个顶点是否相连只要O(1)快。但图算法里这种单点查询经常不是瓶颈更大的瓶颈是遍历一个顶点的所有邻居邻接矩阵这时候要扫一整行V个位置邻接表直接顺着链表走就行。后者在稀疏图上的效率优势非常明显。2.3 邻接表的Java实现代码《算法》书里用的Bag背包也就是只支持添加元素、不支持删除的集合来存邻居我用更常见的ArrayList也一样核心代码是这样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]; } }addEdge这里就体现了无向图的关键一条边必须同时在两个顶点的邻接表里出现。很多新手写无向图的addEdge时只加了一边调试半天发现路径怎么都不对。这个细节我在后面故障排查里还会专门说。还有一个小细节构建图的时候如果事先知道不会重复加边可以在addEdge里不做重复检查这样能省掉一个O(度)的扫描。如果你要处理重复输入的测试数据那就得先检查一遍或者干脆用Set作为邻接表的数据结构。现实中我一般先用Set去重等数据干净了再转回ArrayList因为Set的迭代顺序不稳定会对结果的可复现性造成干扰。3. 深度优先搜索一条路走到黑撞墙才回头3.1 迷宫思维与三个关键问题深度优先搜索DFS是图算法里的基础工具。我习惯把它想象成走迷宫从入口出发随便挑一条岔路一直走实在走不通了就退回到上一个岔路口换一条路继续走。这个“退回”动作在程序里就是递归回溯。在正式写代码前先问自己三个问题第一个从起点出发能到哪些点这是连通性判断属于DFS最简单也最核心的用途。第二个走的过程中是否经过了重复的点没有visited标记的DFS会在环里无限循环。无向图里天然就有环的情况哪怕图里只有1和2两个点之间有一条边从1出发访问2再从2又回到1如果不做标记递归就永远停不下来。第三个能不能把走过的路径记录下来方便后续查从起点到某点的完整路线这就需要一个edgeTo数组记录每个顶点是从哪个顶点走过来的。这三个问题基本就是《算法》里Paths类的设计原型。先看代码从上到下逐段拆解。3.2 最简单的DFS实现与路径记录public class DepthFirstPaths { private boolean[] marked; // 是否已访问 private int[] edgeTo; // 记录路径edgeTo[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; DequeInteger path new ArrayDeque(); for (int x v; x ! s; x edgeTo[x]) { path.push(x); } path.push(s); return path; } }这段代码值得好好讲几遍。marked数组的作用是避免绕回已经访问过的顶点。注意这里的visited是从起点开始沿着可达路径逐步扩散的。如果某个顶点和起点不在同一个连通分量里那它永远不会被标记为true这个特性直接被hasPathTo用上了。edgeTo数组则像个隐形的路标。每当我们第一次发现顶点w时一定是通过某个顶点v的这个入口进去的于是记录edgeTo[w] v。等搜索全部结束想要从顶点v回溯到起点s就是沿着edgeTo一条一条往回走v → edgeTo[v] → edgeTo[edgeTo[v]] → … → s。用栈把它正过来就能打印出正向路径。这里有个极易踩的认知误区pathTo返回的路径不一定是最短的。DFS是一口气钻到底找到一条可行路径就记录了不会去比较哪条路更短。在这个例子中从顶点0出发邻接表里先访问1那路径就是0→1→…可要是另一条路0→4→…更短DFS根本不会发现。要保证最短路径就得用下一节讲的广度优先搜索。递归深度的问题也要提前有心理准备。如果图很大比如有几十万甚至上百万个顶点的链路结构递归会让调用栈爆掉。后面我会给一个非递归版本的写法。3.3 非递归DFS与递归版的重要区别显式用栈替代系统递归调用public void dfsIter(Graph G, int v) { DequeInteger stack new ArrayDeque(); stack.push(v); marked[v] true; while (!stack.isEmpty()) { int x stack.pop(); for (int w : G.adj(x)) { if (!marked[w]) { marked[w] true; // 如果要在第一次遇到w时记录路径 edgeTo[w] x; stack.push(w); } } } }仔细观察你会发现非递归版的访问顺序和递归版可能不一样。递归版会先顺着第一条分支一直走到头非递归版则由于栈的后进先出特性最后压进栈的那个邻居会先被弹出访问。这不是bug只是遍历顺序变了。如果对访问顺序有严格要求的场景比如要按照邻接表里的自然顺序输出遍历结果那非递归写法需要在压栈时反着压或者干脆统一用递归。在实际开发里我通常优先写递归版它和数学归纳法的思路完全一致代码短、不易错。只有在明确知道递归深度会很大的情况下才切换成显式栈。4. 广度优先搜索层层推进拿到的是最短路径4.1 用队列实现的层层扩散广度优先搜索BFS走的是另一条路。它不追求“深”而是先扫平起点周边的一整圈再扫下一圈。这个过程可以想象成水面掉进一颗石子波纹一圈一圈往外荡。实现上只需要把DFS的栈换成队列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 ArrayDeque(); marked[s] true; queue.offer(s); while (!queue.isEmpty()) { int v queue.poll(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] v; marked[w] true; queue.offer(w); } } } } }队列的工作方式决定了BFS的特性先入队的顶点先处理。起点先入队随后它的所有邻居入队再随后邻居的邻居入队。因为队列先进先出所以第k圈的顶点一定会在第k1圈的顶点之前被访问这是BFS能找到最短路径的根本原因。为了方便理解拿一个简单图走一遍。假设起点是0邻接表里0连1和2。队列初始是[0]。弹出0把1和2入队变成[1, 2]edgeTo[1]0edgeTo[2]0。弹出1如果1又连着3那就把3入队edgeTo[3]1。弹出2如果2也连着3因为3已经marked了不会重复入队。到这里你会发现从0到3的路径有两条分别是0→1→3和0→2→3但你记录的是edgeTo[3]1也就是第一条被发现的路径。因为层次相同哪条都是最短的。4.2 BFS和DFS的核心权衡选择障碍往往出现在这里DFS代码短、思路直BFS代码也不难区别只在一个数据结构。那么到底用谁我给自己定的规则是需要找“是否存在一条路径”时用DFS因为往往只要找到就有答案不一定需求最优需要找“最短路径”或者“最少步数”时用BFS因为BFS严格按层推进。在无向图的很多实际场景里比如社交网络里两个人之间的最短好友链地铁换乘最少次数BFS就是直观且高效的选择。它的缺点是空间占用可能比DFS更大因为队列里存的都是同一层的顶点如果图很“宽”队列会瞬时膨胀。而DFS只需要显式栈存一条深入路径即可。把这两个方案都实现一遍就会发现一个有意思的事除了容器从栈换成队列以及压入时机略有不同代码骨架高度相似。这也是算法学习中很常见的情况——理解了底层的数据结构差异很多算法都是换汤不换药。5. 连通分量把一张图拆成几块彼此独立的区域5.1 连通分量和DFS的第一次配合还记得前面说的那个问题吗从一个点出发DFS能到达的点就是它所在的连通块。如果图里有多个连通块那么一次DFS就只能标记其中一个块。这时候我们需要对每个顶点都做一次“从它出发”的判断就能把整张图分成若干连通分量。连通分量的一个直观理解一张图里有的顶点和顶点之间有路相连有的之间隔着一条不可逾越的鸿沟每个能互相到达的团体就是一个连通分量。这个关系让我想起班级分组一个组的同学之间可以互相递纸条另一个组的同学完全接触不到第一个组的同学。要快速判断两个顶点是否在同一组连通分量算法节省了每次都做全图搜索的浪费。直接上代码public class ConnectedComponents { private boolean[] marked; private int[] id; // 顶点所属连通分量编号 private int count; // 连通分量数量 public ConnectedComponents(Graph G) { marked new boolean[G.V()]; id new int[G.V()]; for (int v 0; v G.V(); v) { if (!marked[v]) { dfs(G, v); 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]; } public int count() { return count; } }这个算法的工作流程其实就是从编号最小的未访问顶点开始做DFS把能到达的顶点的id全部设为当前的count然后count1。之后再找一个未被标记的顶点重复这个过程。到最后id数组里同一个连通分量的顶点编号相同count就是连通分量总数。这个算法比单独对每对顶点做一次DFS判断连通性要高效得多。判断一个图中v和w是否连通如果每次都重跑DFS那最坏情况是O(V*(VE))。但提前算好连通分量后面每次判断都只是O(1)的数组比较非常适合需要频繁判断的场景比如社交网络里的好友关系判断。在处理真实图数据时连通分量的数量、每个分量的大小分布也能反映图的宏观结构。比如一个网络中如果有一个巨大的连通分量占比接近100%而其他都是孤立的零星小分量那说明整个网络的核心高度连接。5.2 无环图的判定其实是“邻居跟踪”无向图里“环”的定义很简单从某个顶点出发能沿着边不重复地绕一圈回到自己。检测一张图是否包含环是深度优先搜索一个非常自然的应用。DFS过程中有两种回边第一种是回到父节点比如从顶点a走到邻居b再通过b试图访问a。这条边是刚才来时的那条边不算环。第二种是回到一个已经访问过的、又不是父节点的顶点那一定意味着存在环。实现时给方法增加一个参数parent递归调用时把当前节点传进去。这样在遍历邻居时就能区分开“父节点回边”和“真正的环”public boolean hasCycle(Graph G) { marked new boolean[G.V()]; for (int s 0; s G.V(); s) { if (!marked[s]) { if (dfs(G, s, s)) return true; } } return false; } private boolean dfs(Graph G, int v, int parent) { marked[v] true; for (int w : G.adj(v)) { if (!marked[w]) { if (dfs(G, w, v)) return true; } else if (w ! parent) { // 遇到已访问且不是父节点说明存在环 return true; } } return false; }这里有个容易出错的地方初始化的时候如果将parent设成-1有的人判断回边时忘了排除父节点导致在最简单的一条边上就误判有环。我习惯在调用时传s作为parent这样从起点开始的那条边也会被正确排除。5.3 二分图判定染色法里藏着搜索的又一面貌二分图这个名称在现实里到处都是。想象一个“相亲匹配”场景左边是男生右边是女生边代表“互相有意”。男生和男生之间没有边女生和女生之间也没有边这个图就是二分图。判断一幅图是不是二分图最经典的算法叫染色法原理也极其简单给每个顶点涂上黑或白两种颜色要求相邻顶点的颜色必须不同。实现就是在DFS遍历时给顶点赋颜色一旦遇到一条边的两个端点颜色相同就说明这张图不是二分图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; } } } public boolean isBipartite() { return isTwoColorable; } }结合交点经验说个实用点如果考试或面试让你判断无向图是否为二分图你完全可以不用递归DFS改用BFS来做本质一样只要保证“每一对相邻顶点颜色不同”这个约束在全局成立即可。如果图由多个连通分量组成要记得对每个分量都做一次判定只处理一个分量判断不出来。6. 实操中的几个大坑与调试心得6.1 邻接表漏加对称边Bug会非常隐秘我第一次写无向图的addEdge时只写了adj[v].add(w)忘了adj[w].add(v)。结果单个图看起来没事两个顶点一条边的极简场景也能工作但一旦跑DFS路径记录就发现从1出发找不到0而从0出发能找到1。这种不对称现象就是无向图邻接表漏加对称边的典型症状。排查方法是打印每个顶点的邻接表检查每条边是否在两个端点的邻居里都出现。有经验的开发者经常会用这个打印步骤来验证图的构建是否符合预期。6.2 递归爆栈在不同数据规模下会突然发生DFS的递归深度和图的结构密切相关。最坏情况是一个“线性图”比如0连11连2一直到千万级别的顶点。这时候递归深度就等于图的直径JVM默认栈深度根本扛不住程序直接抛StackOverflowError。如果你要处理大型图直接把DFS改成显式栈版本最稳妥别心存侥幸。也可以在递归里做深度检查超过某个阈值就抛出业务异常或者切换非递归逻辑但这属于补丁方案不如一开始就选定正确的实现方式。6.3 别忽略图的数据输入规模很多人在刷题或处理真实数据时看到顶点数V10^5边数E310^5仍用邻接矩阵结果内存直接爆掉。你可以提前估算一下邻接矩阵需要的字节数大约是VV/8如果用BitSet或者VV如果用boolean数组。V10^5时VV10^10等于百亿级别无论如何都不可行。邻接表的空间大约为V2E个引用这个量级在百万级都还好。先估算数据规模再选数据结构是图算法里非常实用的前置习惯。6.4 路径记录用数组还是Map怎么选前面的代码里edgeTo用的是int数组前提是顶点编号正好是从0到V-1的连续整数。现实中很多数据并不是这样比如顶点编号是字符串城市名、用户ID或者离散的大整数。此时更通用的做法是用MapMapString, String edgeTo new HashMap();好处是可以直接用真实ID作为键不需要额外做映射。缺点是自动装箱、哈希计算都会带来额外开销。对于性能敏感的千万级数据还是建议先把顶点重新映射为连续整数编号计算完成后再映射回去。这个“符号表映射”的做法就是后面符号图那一节要讲的东西。6.5 多个连通分量的搜索记得外面对每个分量都要跑做深度优先搜索的经典失误就是只从一个起点s调用dfs(G, s)然后如果图不是全连通那些在其他分量的顶点从来没有被标记过。后面调用hasPathTo当然返回false可你根本不知道false是因为路径不存在还是因为根本没搜过。连通分量那一节给出的遍历所有顶点的for循环就是处理这种情况的标准写法。我建议在做任何“全图分析”类的算法时都默认对每个未被标记的顶点执行一次搜索流程。7. 无向图的进阶话题与后续笔记的预告无向图还有不少值得继续挖的点比如符号图用字符串作为顶点名的图、欧拉路径一笔画问题、以及最大连通分量统计。这些内容本质上还是建立在DFS和BFS之上。比如欧拉路径的判断核心就一条一个无向连通图存在欧拉路径当且仅当有0个或2个顶点的度为奇数。这个结论用DFS走一遍同时统计所有顶点的度数立马就能算出来。符号图那个话题其实更适合在有向图之后一起讲因为很多真实场景网页超链接、任务依赖天然是有向的。等我有空把有向图的笔记也写出来两者放在一起对比很多概念会一下子通透了。这套笔记整体风格是力求用最少的术语把事情讲明白同时给出能跑的代码因为我知道这类东西光看概念不走代码是记不牢的。如果你边看边把每个类敲一遍设几个简单图测试你的印象会比单纯阅读深很多。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
