先分享一个感受图这个数据结构在Java高阶数据结构里属于那种“看着唬人、其实特别实用”的类型。社交平台的好友推荐、外卖App的路径规划、任务编排系统、编译器里的依赖解析底层拆开全是图。这篇干货笔记我想把自己踩过坑之后沉淀下来的实现思路和关键代码完整写出来适合已经掌握数组、链表、树这些基础想往更深处走一步的Java开发者。我不打算从教科书角度平铺直叙而是按我实际做项目时“先建模、再遍历、然后上算法、最后排查问题”的顺序来讲中间会穿插大量可以直接抄走的Java代码以及一些在线文档里不会写的细节。1. 图整体认知建模思路与存储方案选型1.1 图在解决什么问题从社交关系到导航路径先说清图到底是个什么东西。树也是一种非线性结构但图比树更自由树的每个节点最多只有一个父节点兄弟节点之间没有连线而图里的任意两个节点都可以直接相连甚至节点还可以自己连自己。我习惯把图的本质概括成一句话研究“多个对象以及对象之间的关系”的数据结构。对象叫顶点关系叫边。具体到场景里就很好理解微信好友关系每个用户是一个顶点两个用户认识就有一条无向边微博关注关系用户之间是单向的这就是有向边地图导航路口是顶点道路是边路况和路程就是权重课程依赖学完A才能学B这种先后约束系统就叫有向无环图DAG。正因为表达关系的能力极强图在面试里几乎是必考的而且考的内容高度模式化。这个模式化是好事说明只要把存储、遍历、最短路径、拓扑排序、环检测这几块吃透绝大多数图的问题都能覆盖到。这篇笔记就是围绕这条主线展开的。1.2 邻接矩阵还是邻接表一张表选对存储方案很多教材喜欢先讲邻接矩阵因为它数学上很直观。假设有V个顶点用一个V行V列的二维数组arr[i][j]表示顶点i和顶点j之间有没有边、权重是多少。判断两个顶点是否相邻的时间复杂度是O(1)这在某些算法里是巨大优势。但它的缺点同样致命空间复杂度是O(V^2)。如果图里有1万个顶点矩阵就是1亿个格子。而真实业务中的图绝大多数是稀疏图也就是顶点很多、边相对很少。比如社交网络里你有500个好友但全站有1000万用户邻接矩阵里绝大部分格子都是浪费的。所以工程实践里我几乎无条件选邻接表。邻接表的核心思想是每个顶点只保存和自己直接相连的邻居列表。空间复杂度是O(VE)E是边数稀疏图下非常省内存。遍历某个顶点的所有邻居也非常自然直接取它的链表或者列表就行。两种方案在实际代码里的差别我用下面这个表做个速查对比维度邻接矩阵邻接表空间复杂度O(V^2)O(VE)判断两点是否直接相连O(1)直接查数组O(degree)需要遍历邻居列表遍历某个顶点的所有邻居O(V)要扫一整行O(degree)只扫邻居适合场景稠密图、需要频繁判断顶点连通性绝大多数真实业务图稀疏图Java实现成本二维数组简单但浪费内存HashMap加列表灵活但代码略多选邻接表还有个隐性好处顶点不要求是连续的整数下标。实际业务里顶点往往是用户ID、订单号、课程编号这些业务主键用MapT, ListEdge 建模跟业务代码的贴合度远高于数组下标。这一点在后面的代码实现里会体现得非常明显。2. Java图结构实操骨架搭建与核心算法脉络2.1 顶点与边建模泛型Map邻接表这样写建模是很多初学者第一个卡住的地方。我推荐用泛型Map邻接表原因很简单它自然支持任意类型的顶点而且不需要预先知道顶点总数。边的建模有两种思路。最简单的是只存目标顶点适用于不关心权重的场景稍微复杂一点的是用一个Edge对象封装目标顶点和权重。我通常直接上带权重的版本因为后续Dijkstra、Bellman-Ford都需要权重而且无权重场景下把权重固定为1即可一套代码通吃。public class EdgeT { private final T to; private final int weight; public Edge(T to, int weight) { this.to to; this.weight weight; } public T getTo() { return to; } public int getWeight() { return weight; } Override public String toString() { return - to ( weight ); } } public class GraphT { private final MapT, ListEdgeT adjacencyMap new HashMap(); public void addVertex(T vertex) { adjacencyMap.computeIfAbsent(vertex, k - new ArrayList()); } public void addEdge(T from, T to, int weight) { addVertex(from); addVertex(to); adjacencyMap.get(from).add(new Edge(from, weight)); } }等一下上面这段代码是我故意埋了个错位的Edge构造。写的时候注意Edge的构造函数第一个参数是目标顶点to所以addEdge里必须写new Edge(to, weight)千万别把from传进去。这类低级错误很难肉眼发现因为这个错误不会导致编译报错只会在运行阶段出现“边的走向完全不对”的问题。我踩过一次排查了很久才发现是构造参数顺序写反了。正确的addEdge是这样的public void addEdge(T from, T to, int weight) { addVertex(from); addVertex(to); adjacencyMap.get(from).add(new Edge(to, weight)); }如果你的图是无向图需要同时把from加入to的邻居列表public void addUndirectedEdge(T a, T b, int weight) { addEdge(a, b, weight); addEdge(b, a, weight); }这里有个细节有向图和无向图的API一定要分开命名甚至建议在类注释里写清楚。因为一旦混用单向边被当成双向边处理算法结果会完全偏离预期。尤其是写Dijkstra时少加一条反向边某些节点的距离就可能输出Integer.MAX_VALUE。2.2 增删改查API几个容易踩的坑图骨架里除了addEdge还有三个高频操作值得谨慎处理删除边、查询邻居、遍历所有顶点。删除边的Java习惯写法是这样的public void removeEdge(T from, T to) { ListEdgeT edges adjacencyMap.get(from); if (edges null) return; edges.removeIf(edge - edge.getTo().equals(to)); }注意removeIf的条件是edge.getTo()等于目标顶点而不是edge对象本身因为Edge对象可能是新new出来的直接按对象删除大概率失败。查询邻居就简单了返回一个防御性拷贝或者空列表避免外部代码直接改坏内部结构public ListEdgeT getEdges(T vertex) { return adjacencyMap.getOrDefault(vertex, Collections.emptyList()); }获取所有顶点直接用adjacencyMap.keySet()获取所有边则需要遍历一遍。真正写算法时邻接表的顶点集合和边集合是高频基础设施我会在Graph类里直接加两个方法public SetT getVertices() { return adjacencyMap.keySet(); } public ListEdgeT getAllEdges() { ListEdgeT allEdges new ArrayList(); for (Map.EntryT, ListEdgeT entry : adjacencyMap.entrySet()) { T from entry.getKey(); for (EdgeT edge : entry.getValue()) { allEdges.add(edge); } } return allEdges; }这里还有个很隐蔽的坑如果你的Graph类支持并发访问HashMap和ArrayList都不是线程安全的。生产环境里频繁读取的图我建议用ConcurrentHashMapT, CopyOnWriteArrayListEdgeT或者干脆初始化完成之后就不让外部再修改靠不可变约束来保证安全。这些设计决策在单机算法演示时看不出来但放到真实服务里就是血泪教训。2.3 BFS与DFS遍历的两种姿势图的遍历是整个算法体系的地基。BFS广度优先用队列DFS深度优先用递归或者显式栈。两者的差别一句话就能说清楚BFS一层一层往外扩散DFS一条路走到黑再回头。BFS的标准写法如下public ListT bfs(T start) { ListT result new ArrayList(); SetT visited new HashSet(); QueueT queue new LinkedList(); visited.add(start); queue.offer(start); while (!queue.isEmpty()) { T current queue.poll(); result.add(current); for (EdgeT edge : getEdges(current)) { if (!visited.contains(edge.getTo())) { visited.add(edge.getTo()); queue.offer(edge.getTo()); } } } return result; }有两个关键点。第一visited标记必须在入队时就完成而不是在出队时完成。如果出队时才标记同一个顶点可能被多个邻居重复加入队列轻则结果重复重则在特定结构的图里引发性能雪崩。第二BFS天然具备无权图最短路径能力我第一次到达某个顶点时走过的层数就是最短步数这是BFS在算法题里最值钱的性质。DFS的递归写法非常简洁public void dfs(T vertex, SetT visited, ListT result) { visited.add(vertex); result.add(vertex); for (EdgeT edge : getEdges(vertex)) { if (!visited.contains(edge.getTo())) { dfs(edge.getTo(), visited, result); } } }递归DFS适合顶点数在几千到几万量级的图再大的话就要考虑JVM默认栈深度限制。如果顶点规模很大用显式栈的迭代版本更安全public ListT dfsIterative(T start) { ListT result new ArrayList(); SetT visited new HashSet(); DequeT stack new ArrayDeque(); stack.push(start); while (!stack.isEmpty()) { T current stack.pop(); if (visited.contains(current)) { continue; } visited.add(current); result.add(current); for (EdgeT edge : getEdges(current)) { if (!visited.contains(edge.getTo())) { stack.push(edge.getTo()); } } } return result; }DFS的实际用途远不止输出遍历顺序。后序遍历经常用来做依赖分析比如判断一个依赖是否已经被解析先序遍历配合时间戳可以构造出DFS生成树这是后面环检测算法的基础。2.4 拓扑排序DAG最常用的处理手段拓扑排序解决的问题是在存在先后依赖关系的任务里给出一组不违反依赖约束的执行顺序。前提是图必须是有向无环图如果有环排出来的顺序本身就是矛盾的。我推荐用Kahn算法它比DFS后序法更直观而且能顺手检测环。Kahn算法的流程是统计每个顶点的入度把入度为0的顶点入队依次出队并把它邻居的入度减1减到0时邻居入队直到队列为空。public ListT topologicalSort() { MapT, Integer inDegree new HashMap(); for (T vertex : getVertices()) { inDegree.put(vertex, 0); } for (T vertex : getVertices()) { for (EdgeT edge : getEdges(vertex)) { inDegree.put(edge.getTo(), inDegree.get(edge.getTo()) 1); } } QueueT queue new LinkedList(); for (Map.EntryT, Integer entry : inDegree.entrySet()) { if (entry.getValue() 0) { queue.offer(entry.getKey()); } } ListT result new ArrayList(); while (!queue.isEmpty()) { T current queue.poll(); result.add(current); for (EdgeT edge : getEdges(current)) { inDegree.put(edge.getTo(), inDegree.get(edge.getTo()) - 1); if (inDegree.get(edge.getTo()) 0) { queue.offer(edge.getTo()); } } } if (result.size() ! getVertices().size()) { throw new IllegalStateException(图中存在环无法完成拓扑排序); } return result; }入度统计阶段必须遍历所有顶点初始化不能只处理有邻居的顶点否则孤点不会出现在入度表里最终结果会漏掉顶点。还有每次更新入度之后要立刻判断是否变成0并立即入队不能在循环结束后统一扫描否则队列永远为空排序输出不完整。拓扑排序的时间复杂度是O(VE)和BFS一个量级非常高效。实际开发里我经常用它做构建系统依赖解析、K8s资源创建顺序编排这类工作几乎都是同一套模板。3. 进阶算法笔记最短路径与环检测怎么落地3.1 Dijkstra最短路径优先队列版本怎么实现Dijkstra算法解决的是“单源最短路径”问题也就是从一个起点出发找到到达其他所有顶点的最短加权路径。算法的朴素思想是贪心不断从未确定的顶点中选出当前距离最小的那个尝试通过它的边去松弛其他顶点。不提性能先把最朴素的版本说清楚每次遍历所有顶点找最小距离复杂度O(V^2)顶点多的时候根本跑不起来。工程实现里必须用优先队列来维护“当前距离最小的候选顶点”。public MapT, Integer dijkstra(T start) { MapT, Integer distance new HashMap(); SetT visited new HashSet(); PriorityQueueMap.EntryT, Integer pq new PriorityQueue(Comparator.comparingInt(Map.Entry::getValue)); for (T vertex : getVertices()) { distance.put(vertex, Integer.MAX_VALUE); } distance.put(start, 0); pq.offer(new AbstractMap.SimpleEntry(start, 0)); while (!pq.isEmpty()) { Map.EntryT, Integer entry pq.poll(); T current entry.getKey(); if (visited.contains(current)) { continue; } visited.add(current); for (EdgeT edge : getEdges(current)) { if (visited.contains(edge.getTo())) { continue; } int newDist distance.get(current) edge.getWeight(); if (newDist distance.get(edge.getTo())) { distance.put(edge.getTo(), newDist); pq.offer(new AbstractMap.SimpleEntry(edge.getTo(), newDist)); } } } return distance; }这里有一个Java代码层面的要点优先队列里存的是“顶点当前距离”的配对而不是只存顶点。如果只存顶点优先队列无法知道谁的当前距离更小排序规则无从谈起。再一个坑是失效条目问题。同一个顶点被松弛多次就会在队列里存在多条entry其中旧entry记录的是过期距离。所以出队时必须用visited集合或者再判断一次当前entry里的距离是否等于distance.get(current)如果不等就跳过。上面这段代码用visited集合处理了这个问题简单可靠。用Map.Entry做配对的写法在代码量上最省但可读性一般。如果团队成员习惯面向对象我建议单独写一个Node类实现Comparable接口视觉效果更好也方便以后扩展字段。Dijkstra不能处理负权边这一点太重要了。它基于一个假设当前距离最小的顶点一旦被确定就永远不会被后续松弛过程更新。但如果有负权边存在后续可能出现另一个顶点绕了一圈之后让当前顶点的距离变得更小这个假设直接崩塌。遇到带负权的图要用下一节的Bellman-Ford。3.2 负权边的应对方案Bellman-FordBellman-Ford的思想和Dijkstra完全不同它不贪心而是做暴力松弛。所谓松弛就是反复检查每一条边看看能不能通过这条边让目标顶点的距离变小。做V-1轮每一轮都把每条边检查一遍。为什么是V-1轮因为在一个没有负环的图里从起点到任意顶点的最短路径最多包含V-1条边再多就会形成环路而每轮至少能确定一条边上的最短距离。public MapT, Integer bellmanFord(T start) { MapT, Integer distance new HashMap(); for (T vertex : getVertices()) { distance.put(vertex, Integer.MAX_VALUE); } distance.put(start, 0); int vertexCount getVertices().size(); for (int i 0; i vertexCount - 1; i) { for (EdgeT edge : getAllEdges()) { T from vertexKeyFromEdge(edge); if (distance.get(from) Integer.MAX_VALUE) { continue; } int newDist distance.get(from) edge.getWeight(); if (newDist distance.get(edge.getTo())) { distance.put(edge.getTo(), newDist); } } } return distance; }这里有个细节容易忽略getAllEdges()返回的Edge对象里并没有记录边的起点from因为Edge类只保存了to。我在上面的示例里写了vertexKeyFromEdge(edge)这个辅助方法实际上如果不改造Edge类Bellman-Ford就没法正确拿到边的起点。所以我建议当确定要跑Bellman-Ford时Edge类里直接加一个from字段。记住边的两个端点都保存下来是最稳妥的public class EdgeT { private final T from; private final T to; private final int weight; // 构造器、getter省略 }负环检测也顺势很简单V-1轮松弛结束后再扫一遍所有边如果仍然有边能让距离变小说明图中存在负权环此时最短路径没有定义。Bellman-Ford的时间复杂度是O(VE)在稠密图上非常慢。实际工程里如果确定没有负权边老老实实用Dijkstra只有遇到负权或者需要负环检测时才用Bellman-Ford。还有一种SPFA算法可以看作Bellman-Ford的队列优化平均表现好很多但也存在被精心构造的数据卡到O(VE)的情况面试里如果和面试官聊到可以提一句说明你理解得够深。3.3 并查集环检测无向图判环的经典套路并查集本身就是一种非常优秀的图相关数据结构专门用来管理和查询元素之间的分组关系。它支持两个操作find查找某个元素属于哪个集合union把两个集合合并。用它检测无向图是否有环的思路极其巧妙遍历每条边如果边的两个端点已经在同一个集合里说明这条边连通了两个本来就连通的分支形成一个环如果不在同一个集合就把它们合并。public class UnionFind { private final int[] parent; private final int[] rank; public UnionFind(int n) { parent new int[n]; rank new int[n]; for (int i 0; i n; i) { parent[i] i; } } public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } public boolean union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return false; } if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } return true; } }find方法里的parent[x] find(parent[x])就是路径压缩它让find的平均时间复杂度接近O(1)。union里的按秩合并保证了树的高度尽可能小。这两个优化必须同时上只有路径压缩不做按秩合并或者只按秩合并不路径压缩理论上都有退化风险。检查环的代码段是这样的public boolean hasCycle(int vertexCount, int[][] edges) { UnionFind uf new UnionFind(vertexCount); for (int[] edge : edges) { int a edge[0]; int b edge[1]; if (!uf.union(a, b)) { return true; } } return false; }并查集的另一个高频应用是连通分量统计初始化一个计数器为顶点数每次成功的合并就让计数器减1最终计数器值就是图的连通分量个数。这个思路在判断一个图是否连通、计算岛屿数量、处理动态连通性问题时非常通用。注意并查集适用于无向图环检测有向图的环检测还是要靠拓扑排序或者DFS三色标记法别搞混。4. 实战复盘课程依赖调度器从0到14.1 业务场景与需求整理用前面的图基础我做一个能直接落地的案例某线上学习平台的课程排期。业务规则是每门课程可能有前置课程只有学完前置才能开课平台需要在开学前自动算出一套可执行的开课顺序。如果课程之间的依赖形成了循环比如A依赖B、B又依赖A那么这套方案根本排不出来系统要给出明确报错。这个场景抽象成图就是每门课程是一个顶点依赖关系是有向边排开课顺序就是拓扑排序。需求整理下来就三条输入课程总数、课程名列表、依赖关系列表输出一个可行的开课顺序异常存在循环依赖时抛出友好错误。课程不多的情况下用整数下标作为顶点编号最方便直接套用数组实现的数据结构不需要泛型Map的一堆装箱拆箱。4.2 核心实现依赖解析与顺序输出我用整数顶点、邻接表、入度数组来实现逻辑上和前面泛型版完全一致只是省掉了泛型带来的模板代码更适合作为一道完整练习题来看。import java.util.*; public class CourseScheduler { public static ListInteger schedule(int courseCount, ListListInteger prerequisites) { ListListInteger graph new ArrayList(); int[] inDegree new int[courseCount]; for (int i 0; i courseCount; i) { graph.add(new ArrayList()); } for (ListInteger pre : prerequisites) { int from pre.get(0); int to pre.get(1); graph.get(from).add(to); inDegree[to]; } QueueInteger queue new LinkedList(); for (int i 0; i courseCount; i) { if (inDegree[i] 0) { queue.offer(i); } } ListInteger order new ArrayList(); while (!queue.isEmpty()) { int current queue.poll(); order.add(current); for (int next : graph.get(current)) { inDegree[next]--; if (inDegree[next] 0) { queue.offer(next); } } } if (order.size() ! courseCount) { throw new IllegalArgumentException(课程依赖存在循环无法排课); } return order; } public static void main(String[] args) { int courseCount 5; ListListInteger prerequisites Arrays.asList( Arrays.asList(0, 2), Arrays.asList(1, 2), Arrays.asList(1, 3), Arrays.asList(2, 4) ); ListInteger order schedule(courseCount, prerequisites); System.out.println(可行的开课顺序 order); } }这个例子里的依赖关系是课程0是课程2的前置课程1是课程2和课程3的前置课程2是课程4的前置。输出结果可能是[0, 1, 3, 2, 4]或[1, 0, 2, 3, 4]等只要满足约束就是合法答案。4.3 结果验证与边界思考我实际运行上面的main方法输出是可行的开课顺序[0, 1, 2, 3, 4]括号里依赖关系是0-2、1-2、1-3、2-4。检查一下0在2之前满足1在2和3之前满足2在4之前满足。但注意这个输出里3排在了4的后面而课程3没有依赖课程4所以没问题。如果要求“课程3必须在2之后马上输出”那就变成了一个不同的约束问题拓扑排序本身不保证唯一顺序。边界情况也要测一遍。把前置关系改成[[0,1],[1,0]]模拟循环依赖跑出来的结果会直接抛出我之前在方法里写的异常这就对了。还有一个容易忽略的边界是“空依赖”也就是所有课程都不依赖别人这种情况下任意顺序都可以入度为0的课程会一次性全部入队输出顺序取决于课程的遍历顺序。这类案例写完后我还习惯补一个单元测试把输出顺序里的每个依赖关系都验证一遍确保前置课程在结果中的下标小于后置课程这样才不会在重构时悄悄打断正确性。5. 高频问题排查与避坑清单5.1 这几个场景最容易翻车图相关代码写多了翻车的点位其实非常集中。我把高频问题整理成一个速查表遇到现象直接对号入座现象根因解决思路程序卡住不退出BFS或DFS忘了标记visited在环上死循环入队或递归前标记不要出队时再标记递归到一半StackOverflowErrorDFS递归深度超过JVM栈上限改用显式栈的迭代实现或调大栈大小拓扑排序结果缺失顶点入度表没有初始化所有顶点遍历所有顶点统一初始化入度为0无向图边丢失只添加了一条方向的边判断图是有向还是无向无向必须双向添加最短路径结果偏大Dijkstra处理了负权边换Bellman-Ford或确认图无负权优先队列里旧entry干扰未处理失效顶点出队时判断已访问则跳过或比对距离检出不了环并查集忘记路径压缩或union顺序写错find递归压缩union判断根节点是否相等还有一个很经典的坑在Dijkstra里用if (!visited.contains(edge.getTo()))做剪枝时千万不要写成“先更新再判断”。一旦某个顶点已经通过最短路径被访问过后续所有松弛都必须跳过否则可能出现负权假象或者多余更新。并查集里还有一个很多人忽略的点union操作必须先find两个点的根再比较根是否相同最后才是按秩合并。有人图省事直接比较两个原始值低级错误会导致环检测失效。5.2 调试图算法的实用技巧图结构的调试比普通数组难因为它是非线性的。我的第一个建议是写一个极简的打印工具方法把邻接表打印成可读文本肉眼排查错误特别方便public void printGraph() { for (T vertex : getVertices()) { System.out.print(vertex - ); System.out.println(getEdges(vertex)); } }打印效果类似A - [-B(5), -C(2)] B - [-D(1)]这种输出一眼就能看出边有没有加错方向、权重对不对。复杂图可以把这个文本内容复制出来手动画一张图或者用小图验证。第二个建议是“用小图验证算法”。Dijkstra测试用例里我一般用4个顶点的菱形图起点到A权重1、起点到B权重4、A到终点权重1、B到终点权重1最短路径应该是起点-A-终点。这种小图人工手算一遍就知道正确答案便于验证代码是否跑偏。第三个建议是单元测试。图算法是出了名的“改一行坏一片”BFS改坏了可能影响拓扑排序。我习惯把每个算法都配上几组固定输入断言比如空图、单点图、链状图、环图、全连通图覆盖度上来了重构时心里才有底。从工程角度看图算法不追求一次写对而追求出了问题能快速定位。打印邻接表、小图验证、单元测试这三位一体就是我的排错三板斧。最后分享一点我的个人体会图相关的知识其实高度套路化先把邻接表的增删改查写顺再依次掌握BFS、DFS、拓扑排序、最短路径和环检测遇到业务问题时核心步骤就是两步——先识别这是图问题再把对应模板套进去。刚开始学着写的时候多画图多造小样例去手算代码里的边界问题会少掉大半。这篇笔记里的代码和案例都可以直接跑起来照着敲一遍比看十遍效果都好。