如果你刷过一阵子算法题大概率遇到过这类问题给一堆人和朋友关系问两个人之间隔了几度社交距离把棋盘当成格子地图问你从左上角能不能走到右下角再比如电路网络分析、任务依赖建模。这些问题拆到最底层几乎都是同一件事——在一张无向图上做遍历和判断。这篇笔记就是《算法》系列里无向图部分的完整梳理从数据结构表示讲到深度优先搜索、广度优先搜索、连通分量再到环检测和二分图判断。适合刚接触图论的初学者也适合面试前想把图这块一次过透的开发者。我在实际写业务代码时最常见的误解是把图当成什么高深的东西其实它就是“一堆点 点之间的连接关系”。搞懂无向图之后再去看有向图、带权图、网络流这些概念会顺很多。1. 无向图到底在描述什么建模思维比代码更优先1.1 从现实问题到顶点与边无向图的定义一句话就能说清由一组顶点和一组连接这些顶点的边组成边没有方向。也就是说如果顶点 A 和顶点 B 之间有一条边那么从 A 能到 B从 B 也能到 A它们是平等的。我在一个内部项目里做过一个简单的“好友关系分析”用户就是顶点互关关系就是边。因为互关是对称的所以整个系统天然就是一张无向图。后来想给每个用户算“几度人脉”本质上就是在无向图上做无权最短路径也就是这篇笔记里要讲的广度优先搜索。建模的时候最关键的不是怎么存数据而是你能不能把现实问题映射成顶点和边。比如社交网络人 顶点好友关系 边。地图导航路口 顶点道路 边但不一定适合无向图因为单行道就有方向了。文章里的词语共现词 顶点出现在同一句话里 边。电路板焊点 顶点导线 边。一旦建模成功后面的事全是套路。建模失败后面怎么写都别扭。1.2 几个绕不开的术语无向图的术语不多但必须一次性记牢因为后面所有代码都在用这些词度数Degree一个顶点的度数就是连接它的边的数量。无向图里所有顶点的度数之和等于边数的两倍因为每条边会被两个端点各计一次。这个性质在排查数据错误时很有用我后面会讲。路径Path从一个顶点出发沿着边走到另一个顶点所经过的序列。环Cycle起点和终点是同一个顶点的路径。注意无向图里两个顶点之间来回走不算环得至少形成闭合回路。连通Connected如果两个顶点之间存在路径就叫连通。连通分量Connected Component把图中所有能互相到达的顶点各自抱成一团每一团就是一个连通分量。整个图是连通的等价于只有 1 个连通分量。这概念是很多业务里“分群”“分区”的依据。还有一个很实用的分类稀疏图和稠密图。顶点多但边少的叫稀疏图顶点少边极多的叫稠密图。不同的图选择的数据结构都不一样这也是下一节要说的。1.3 为什么先学无向图我刚开始接触图论时跳过无向图直接看有向图结果被边的对称性和不对称性搞得很晕。后来重新补无向图才发现深度优先搜索、广度优先搜索这些核心遍历算法在无向图里能更直观地理解因为边的对称性让“回头走”这件事变得自然。另外一个原因是很多进阶算法比如寻找桥、割点的那套都是建立在无向图基础之上的。先把无向图的基本操作练熟再学有向图就是同一个思路换个场景难度直接降一档。2. 邻接表表示无向图在计算机里的“长相”2.1 邻接矩阵与邻接表的取舍图的代码表示有几种常见方案最基础的两个是邻接矩阵和邻接表。邻接矩阵用 V×V 的二维布尔数组表示matrix[i][j] 为 true 就说明顶点 i 和 j 之间有边。它最大的好处是判断两个顶点是否相邻只要 O(1) 时间非常快。但坏处也很明显空间复杂度是 O(V²)。如果图有 100 万个顶点矩阵就是 100 万 × 100 万根本存不下。遍历一个顶点的所有邻居需要扫描一整行复杂度 O(V)哪怕这个顶点其实只连着 3 个点。邻接表则是为每个顶点维护一个列表列表里装的是它能直接到达的顶点。遍历邻居只花 O(1 该顶点度数) 的时间空间复杂度是 O(V E)。对实际中绝大多数的稀疏图来说邻接表几乎是唯一合理的选择。我在项目里测过一张 10 万顶点、约 30 万条边的图用邻接矩阵直接内存爆炸换成邻接表后只有几十 MB。如果你的问题规模很小或者对“判断是否相邻”有超高频率的需求邻接矩阵另说否则默认邻接表。2.2 无向图的邻接表实现在无向图中一条连接 v 和 w 的边要让 v 的邻接表里出现 w同时让 w 的邻接表里出现 v。这个“双向写入”是新手最容易漏的地方。我用 Java 写了这个类的核心部分风格上尽量贴近学习笔记的调性import java.util.ArrayList; import java.util.List; public class Graph { private final int V; // 顶点数量 private int E; // 边数量 private ListInteger[] adj; // 邻接表 SuppressWarnings(unchecked) 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]; } public int degree(int v) { return adj[v].size(); } }adj的类型是ListInteger[]数组里每一项是一个列表。构造时先创建V个空列表addEdge时双向添加。这个实现虽然简单但已经能支撑后面所有的遍历算法。2.3 自环、平行边和邻居顺序的坑无向图有两种特殊边需要你提前想清楚自环顶点连自己和平行边两个顶点之间有多条边。我在某个图数据清洗任务里遇到过一个顶点自己连自己导致度数统计异常一度以为是程序 bug后来发现是上游数据漏掉了过滤。书上的标准算法通常假设图里不包含自环和平行边。如果你的数据源可能含有这些必须在读入时做好清洗或者在算法里做特殊处理。否则度数总和与边数的两倍关系会被自环打破。并行边会在遍历时重复访问同一个邻居可能导致死循环或重复计数。有些图算法比如后面说的环检测会因为自环直接误判。还有一个很小的细节邻接表里每个顶点的邻居顺序取决于addEdge的调用顺序。这个顺序会影响遍历输出的顶点序列但不会影响正确性。有些场景下为了让输出稳定可复现我会把ArrayList换成TreeSet代价是插入从 O(1) 变成 O(log V)但遍历时邻居会按编号从小到大排列调试起来更省心。3. 深度优先搜索DFS无向图的第一把钥匙3.1 思路像走迷宫一样不撞南墙不回头DFS 的思路特别像一个人在迷宫里探路从起点出发沿着一条路一直走走不动了再往回退一步换一条没走过的路继续。为了防止在原地打转每到一个顶点就做个标记已经标记过的顶点不再进去。这个“标记”是 DFS 的灵魂。如果没有标记在有环图里就会陷入无限循环。有环图恰恰是现实中更常见的情况所以标记数组marked[V]是不可或缺的。用代码写出来可以非常短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); } } } public boolean marked(int w) { return marked[w]; } public int count() { return count; } }这段代码能回答一个最基础的问题从 s 出发能到达哪些顶点也就是无向图的单点可达性。3.2 用一个小例子走一遍假设图有 7 个顶点边是0-1, 0-2, 0-51-32-43-45-6从顶点 0 开始做 DFS标记 0依次看邻居 1、2、5。先到 1标记再看 1 的邻居 3。到 3标记再看 3 的邻居 1 和 4。1 已标记跳过到 4。到 4标记看邻居 2 和 3都跳过。回到 3、1没有新顶点回 0。从 0 继续看下一个邻居 2已标记。再看 5标记到 5 的邻居 6。到 6标记结束。最终标记了 0、1、2、3、4、5、6 全部顶点说明这张图是连通的。这个追踪过程我强烈建议你在纸上画一遍画过一遍之后 DFS 就不再是“背代码”而是真正理解了。3.3 时间复杂度为什么是 O(V E)DFS 会对每个顶点做一次标记也就是访问一次marked[v] true这部分是 O(V)。同时每个顶点的所有邻居都会被遍历一遍每个顶点的邻居数量加起来就是所有边的两倍无向图每条边贡献两次这部分是 O(E)。所以总时间复杂度是 O(V E)。这个结论比背下来更重要的是理解图算法的时间复杂度通常跟“点”和“边”两个维度都有关系。你优化的时候如果图是稀疏的E 约等于 V复杂度近似 O(V)如果是稠密图E 接近 V²复杂度就会偏高。3.4 用 DFS 找路径和连通分量DFS 能做的远不止可达性。给递归调用加一个edgeTo[]数组记录“我是从哪个顶点走到这里的”事后就能恢复出一条路径public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; 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; ListInteger path new ArrayList(); for (int x v; x ! s; x edgeTo[x]) { path.add(0, x); } path.add(0, s); return path; } }这里edgeTo[w] v的含义是“w 是在访问 v 的过程中第一次被发现的”。沿着edgeTo从目标顶点一路回溯就得到了从 s 到 v 的一条路径。不过要注意DFS 找到的路径不一定是最短路径。它更看重“有没有路”而不是“路有多短”。如果你需要最短路径得用下一节的 BFS。连通分量也可以用 DFS 一次算完。做法是从顶点 0 开始做一次 DFS能到达的所有顶点就是一个连通分量然后从下一个还没被标记的顶点再做一次 DFS得到第二个连通分量。每个连通分量给一个编号这样“任意两个顶点是否连通”的问题就变成了“两个顶点的分量编号是否相等”。4. 广度优先搜索BFS最短路径的直观解法4.1 思路像涟漪一样一圈圈扩散BFS 的思路和 DFS 正好相反。它是从起点出发先访问所有距离为 1 的邻居再访问所有距离为 2 的邻居一层一层往外扩散。这个扩散过程用队列实现最自然因为队列是先进先出正好能保证“先到的顶点先扩展”。我还是用上面那张图来做对比。同样从 0 开始0 入队标记 0。弹出 0邻居 1、2、5 全部入队并标记。弹出 1邻居 3 入队。弹出 2邻居 4 入队。弹出 5邻居 6 入队。依次弹出 3、4、6它们没有未标记的邻居。从 0 到每个顶点的路径就被“一层一层”地记录下来了。因为第 2 层是离起点最近的一批第 3 层是次近的一批所以第一次到达某个顶点的路径天然就是最短路径。4.2 BFS 的核心实现BFS 找最短路径的代码同样是配一个edgeTo[]数组import java.util.LinkedList; import java.util.Queue; public class BreadthFirstPaths { private boolean[] marked; private int[] edgeTo; private int[] distTo; private final int s; public BreadthFirstPaths(Graph G, int s) { marked new boolean[G.V()]; edgeTo new int[G.V()]; distTo new int[G.V()]; this.s s; bfs(G, s); } private void bfs(Graph G, int s) { QueueInteger queue new LinkedList(); for (int v 0; v G.V(); v) { distTo[v] -1; } distTo[s] 0; marked[s] true; queue.add(s); while (!queue.isEmpty()) { int v queue.poll(); for (int w : G.adj(v)) { if (!marked[w]) { marked[w] true; edgeTo[w] v; distTo[w] distTo[v] 1; queue.add(w); } } } } public boolean hasPathTo(int v) { return marked[v]; } public int distTo(int v) { return distTo[v]; } }我在代码里加了distTo[]数组它记录从起点到某个顶点的最短距离。这在社交网络的“几度人脉”里特别实用直接读distTo[v]就知道隔了几层。4.3 DFS 与 BFS 的对比选择用久了之后我对 DFS 和 BFS 形成了一个经验判断DFS 写起来快适合探索全貌BFS 适合求最短路径和层次信息。维度DFSBFS数据结构栈递归隐式使用队列路径性质任意一条路径最短路径空间复杂度最坏 O(V)递归深度最坏 O(V)典型应用连通分量、环检测、二分图无权最短路径、层次遍历实现难度更短递归天然适配略长但思路直白还有一个内存层面的细节DFS 用递归时系统栈深度可能达到顶点数 V如果图是一条长链递归就会很深。BFS 的队列在极端情况下也可能存很多顶点但它是显式的不容易触发系统栈溢出。4.4 实际业务里的 BFS我在某次做社交关系分析时要算“两个用户之间最少隔几层好友关系”。最开始我用了 DFS 去找路径结果出来的路径不稳定有时候 3 层有时候 5 层后来才发现问题不在数据而在算法选型。换成 BFS 之后每个用户只要跑一次预处理得到distTo[]后面任意两个用户的“度距”查询都变成 O(1) 读取数组下标。这种“预处理一次查询多次”的模式是图算法落地的常用套路。5. 环检测与二分图检测两个经典的图上判断5.1 无向图的环检测小心父节点这个坑判断一张无向图有没有环还是可以用 DFS。原理是如果在 DFS 过程中遇到一个已经标记过的邻居而且这个邻居不是上一个访问的顶点父节点那就说明存在一条回边图里有环。为什么排除父节点因为无向图的边是双向的从 v 走到 w遍历邻居时一定会看到 v。如果把这个 v 误判为环那所有连通的无向图都“有环”了这显然是错的。我第一次实现时犯的错就是把父节点也当成了环。代码看起来很简单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; } } } public boolean hasCycle() { return hasCycle; } }注意这里外层还有一个循环因为图可能不连通得对每个还没访问过的顶点分别做 DFS。还有一个容易被忽略的细节约定无向图中自环也算环但两个顶点之间来回走的平行边不算环。如果你的数据里有平行边这个实现可能会误判需要提前去重。5.2 二分图检测用双色标记法二分图Bipartite Graph是指能把所有顶点分成两组使得每条边的两个端点分别属于不同组。这个概念在“矛盾冲突”“资源分配”“匹配问题”里经常出现。比如某场景下有“用户”和“内容”两类对象用户只能操作某些内容这个关系天然就是二分图。检测二分图的两色法非常巧妙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; } }color[w] !color[v]这条语句是整个算法的核心它保证了任何边两端颜色相异。如果发现相邻顶点同色直接标记失败。BFS 版本只要把 DFS 换成队列逻辑一模一样。5.3 为什么这两个判断这么重要环检测在工程里最常见的应用是检测数据依赖是否有循环。比如任务 A 依赖 BB 又依赖 CC 又依赖 A这种循环依赖在调度系统里必须先发现否则永远无法执行。有向图的循环依赖检测更复杂一些但思路和判断依据相通。二分图则建议你记住这个结论如果一个图是二分图那么它一定不含奇环。换句话说图里存在长度为奇数的环就一定是非二分图。这个性质在面试里经常被拿来出判断推理题知道了底层原理之后这类题基本秒答。6. 大规模图中的工程实践与踩坑记录6.1 邻接表还是邻接矩阵得看数据规模我在处理一个约 20 万顶点的图时刚开始图方便用邻接矩阵结果直接内存溢出。后来切到邻接表才跑通。这个“跑通”不是简单换个数据结构就完事还要注意 Java 里ListInteger会有装箱开销。如果你对性能有要求可以有两个优化方向用TIntArrayList之类的原生类型集合避免 Integer 装箱。在读取图的时候边数多的情况下尽量用缓冲输入流而不是Scanner。Scanner逐行读在大数据量下会明显拖慢速度。我在做大规模图处理时的个人习惯是先确认 V 和 E 的量级。如果 V 小于 1000 且查询密集考虑邻接矩阵如果 V 在上万甚至百万级别无脑邻接表。6.2 递归深度DFS 在大图和链状图中的危险信号DFS 的递归实现虽然人畜无害但在某些图上会非常危险。比如一张图是 0-1, 1-2, 2-3 ... 的链条状从 0 开始 DFS 就会一路递归到顶点 V每次递归都占用系统栈空间。我在一次处理长链图时直接遇到StackOverflowError排查下来就是递归深度太高。解决办法有几个如果只是要遍历把 DFS 改成显式栈自己用DequeInteger模拟递归过程。如果必须用递归可以在启动参数里调大栈空间但这只是临时缓解。BFS 没有这个问题因为它用的是显式队列。显式栈的 DFS 写法大概长这样public void dfsIterative(Graph G, int s) { DequeInteger stack new ArrayDeque(); boolean[] marked new boolean[G.V()]; stack.push(s); marked[s] true; while (!stack.isEmpty()) { int v stack.pop(); for (int w : G.adj(v)) { if (!marked[w]) { marked[w] true; stack.push(w); } } } }注意这里我是在push之前就标记而不是弹出再标记。如果弹出再标记同一个顶点可能被多次压栈在大图里会造成重复计算。6.3 读取图数据时最容易犯的错我踩过的最典型的坑是读入一条边时把顶点编号搞错或者忘了处理无向图的“双向写边”。比如数据文件里的一行是“3 5”表示 3 和 5 之间有边正确的写法是adj[3].add(5); adj[5].add(3);两边都要少一边就会出现“有向图式”的错误结果。还有一个在实际数据中特别常见的问题顶点编号可能不连续或者从 1 开始而我们习惯从 0 开始。处理办法是读取时做一次减一映射或者在构造Graph时把编号规范化为0..V-1。如果你用的是带字符串标识的数据比如用户名那就需要一张符号表Map来做名字到编号的映射。这也引出下一个技巧。6.4 符号图让顶点不再是数字很多真实场景里的顶点不是 0、1、2 这种整数而是“A同学”“B同学”或者设备 ID。一个实用的做法是把字符串映射成整数图结构照旧查询时再用一个反向数组把整数映射回字符串。步骤很简单读数据时用MapString, Integer把第一次遇到的名称登记为编号。用ListString记录编号对应的名称。之后每次遇到名称查表换成编号再正常建图。我做过的一个模拟项目里用了这个方案处理用户间的“共同关注”关系建图部分极其顺畅。关键是调试的时候友好太多了你能直接看到“A同学”连到了“B同学”而不是盯着 1024 和 2048 两个数字发呆。6.5 数据校验用度数关系检查建图是否正确最后分享一个我很早学会但一直用着很爽的校验手段。无向图里所有顶点的度数之和等于边数的 2 倍。我每建完一张图都会写一行临时校验代码把所有degree(v)加起来对比2 * E是否相等。这个校验看起来简单但真能查出不少数据问题。比如数据文件里有重复边E 没跟着变度数之和不匹配。addEdge只写了一边度数之和不匹配。顶点编号越界会直接抛出数组越界异常。只要校验过这一条我基本上对建图逻辑放心一大半。比单测还方便适合所有图类项目的早期排查。无向图的笔记到这里就基本完整了。最后补充一句自己的体会图算法不像排序、查找那样有一个固定的“最优答案”它的魅力正在于“数据结构选择”和“算法选择”的组合非常多而把这些选择做对的前提是把底层原理吃透。邻接表、DFS、BFS、连通分量、环检测、二分图这些概念单独看都很简单组合在一起却能解决大量现实问题。我在实际项目处理中最大的心得是先建模再选结构最后才是写代码顺序错了就容易白干。
