无向图算法核心：邻接表、DFS/BFS与连通分量详解

啃到图这一章，算是把《算法》这本书的分水岭真正趟过去了。前面学排序、学查找，处理的都是“一个元素跟另一个元素”之间的关系，到了无向图，突然变成了“一堆元素互相之间都有关系”，思维模式一下子就不一样了。无向图是图论里最基础也最常用的一块，后面的有向图、加权图、最小生成树、最短路径，全都是在它的骨架上长出来的。这篇笔记我会从图的表示开始，把深度优先搜索、广度优先搜索、连通分量、环检测、二分图检测这几个核心内容一次讲透，最后附上我实际写代码时踩过的坑。适合正在啃这本书的读者，也适合准备面试想快速把图的基础捡起来的人。

说实话，图这个章节我第一次读的时候差点弃书，因为代码量突然变大，抽象程度也高。但真啃下来之后会发现，图的算法套路其实非常固定，核心就那么几个模板，一旦理解了搜索过程本身，剩下的全是在这个骨架上做变形。所以这篇笔记我不会照抄书里的代码，而是把每个算法的“为什么”讲清楚，再给一份可以直接抄的模板。

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 List<Integer>[] adj; // 邻接表 public Graph(int V) { this.V = V; this.E = 0; adj = (List<Integer>[]) 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 Iterable<Integer> adj(int v) { return adj[v]; } }

这份代码本身就是无向图最核心的性质：因为边没有方向，所以添加一条连接v和w的边时，必须同时把v加到w的邻接表里，也把w加到v的邻接表里，维护好这个对称性。很多新手写无向图算法出错，根源就在漏掉了这个对称操作。

另一个细节是，我用List<Integer>而不是链表，在实际开发里灵活性和性能表现都不错。如果读的是原书，它用的是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 Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) return null; // 从v倒着往起点推，借助栈反转顺序 java.util.Stack<Integer> 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，但这只是治标。二是把递归改写成显式的栈迭代版本，自己维护一个Stack<Integer>来模拟递归过程。后者代码会啰嗦一些，但可控性更强。

我自己的建议是：刷题和学习阶段，递归版本完全够用，理解起来也更直接。如果到了处理真实海量图的工程场景，再考虑改成迭代版。别一上来就追求“高性能写法”，先把递归版本吃透，因为后面的很多算法，比如环检测、二分图检测、拓扑排序，都是基于递归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) { Queue<Integer> 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到底该怎么选

这是面试和学习中最高频的问题，我直接给一个实用的对照：

实际选型就一句话：要最短路径，用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(V+E)；而用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 常见问题速查表

代码写得越多，踩的坑就越深。我把写无向图算法时最常见的几个问题整理成了一张速查表：

这里的每一个坑我都真实踩过。尤其是第一个，新建邻接表时忘了给每个顶点初始化，结果一调用adj(v)就空指针，Debug了半个下午才发现是最基础的问题。写代码时先把这些基础检查表过一遍，比出错了再排查效率高得多。

6.2 我的几个实操心得

先说测试用例的构造。很多人写图算法，喜欢拿书上的小图一跑就完事，这其实远远不够。我自己测试时会故意构造几个特殊形状：一个完全连通的环、一个带孤立顶点的图、一个包含多连通分量的图、一个宽度很大的图。这些边界情况能把算法里的逻辑漏洞暴露出来，比单纯验证“能跑通”靠谱得多。

再说性能层面的观察。当图的顶点数达到百万级别时，如果使用递归DFS，栈深度可能是压死骆驼的最后一根稻草。这时候需要用显式栈或改写BFS来规避。但反过来，如果你在刷题或笔试阶段，过度优化只会让代码变得难读难调，先把正确性保证好，再来谈性能。

最后还有一个小技巧：把图的邻接表打印出来做可视化。很多算法看起来抽象，但当你把adj数组的内容按顶点一行行打印出来，整个图的结构就清晰了，调试时一眼就能看出邻接关系对不对、边有没有漏加。

6.3 下一步可以往哪走

无向图学完后，很自然的延伸就是有向图。有向图里的边带了方向，环检测的逻辑需要区分有向环和无向环，拓扑排序、强连通分量（比如Tarjan算法）、最短路径算法（Dijkstra、Bellman-Ford）全都会在无向图的基础上进一步发展。

我个人在学完这一章后最深刻的一个感受是：无向图的所有算法，本质上都是在DFS和BFS这两个搜索模板上做扩展。连通分量是DFS加一个计数数组，环检测是DFS加一个父顶点参数，二分图检测是DFS加一个颜色数组，最短路径是BFS加一个edgeTo数组。理解了这层关系，学到后面的有向图时，你会发现处处都是熟悉的面孔。如果你也正在啃这一章，我的建议是先别急着刷题，把DFS和BFS这两个模板手写十遍，写到闭着眼都能默写出来，再往后面的章节走，你会轻松很多。