1. 先理清图的存储不把这块搞明白算法全白搭图这种数据结构在很多初学者眼里是玄学。树好歹有个层次关系图上来就是一堆顶点和边没有明确的“入口”写代码时第一步就卡住了。我从标题里提到的“图代码实现”说起这个算是后续最小生成树和最短路径算法的地基一共只需要掌握两种主流存储方式邻接矩阵和邻接表加上一个辅助的边集数组。1.1 邻接矩阵简单直观适合稠密图邻接矩阵就是一个二维数组adj[i][j]存的是从顶点i到顶点j的边权。如果是无权图存 0 或 1如果是带权图存权值。public class GraphMatrix { private int[][] adj; private int vertexCount; private static final int INF Integer.MAX_VALUE / 2; public GraphMatrix(int vertexCount) { this.vertexCount vertexCount; adj new int[vertexCount][vertexCount]; for (int i 0; i vertexCount; i) { for (int j 0; j vertexCount; j) { if (i j) adj[i][j] 0; else adj[i][j] INF; } } } public void addEdge(int from, int to, int weight) { adj[from][to] weight; } public void addUndirectedEdge(int from, int to, int weight) { adj[from][to] weight; adj[to][from] weight; } public int getWeight(int from, int to) { return adj[from][to]; } }注意我将无穷大设成了Integer.MAX_VALUE / 2而不是直接取Integer.MAX_VALUE。原因是算法里免不了执行类似dist[i] weight的操作如果两个大数相加直接溢出了。除以 2 之后留出缓冲这是处理图算法时非常实用的习惯。邻接矩阵的最大优点判断两个顶点是否直接相连时间复杂度 O(1)代码写起来几乎不用动脑。最大缺点是空间占用 O(V²)一个 10000 个顶点的图矩阵大小就是 1 亿个整数约 400MB直接内存爆炸。所以邻接矩阵只适合稠密图或者顶点数很少的情况。1.2 邻接表稀疏图的首选出边遍历是强项绝大多数实际场景是稀疏图顶点很多但每个顶点的邻居很少此时用邻接表。每个顶点维护一条链表或列表存放它指向的顶点和边权。import java.util.*; public class GraphList { private ListListEdge adj; private int vertexCount; static class Edge { int to; int weight; Edge(int to, int weight) { this.to to; this.weight weight; } } public GraphList(int vertexCount) { this.vertexCount vertexCount; adj new ArrayList(vertexCount); for (int i 0; i vertexCount; i) { adj.add(new ArrayList()); } } public void addEdge(int from, int to, int weight) { adj.get(from).add(new Edge(to, weight)); } public void addUndirectedEdge(int from, int to, int weight) { adj.get(from).add(new Edge(to, weight)); adj.get(to).add(new Edge(from, weight)); } public ListEdge getNeighbors(int vertex) { return adj.get(vertex); } }写邻接表时有个小细节如果确定图运行过程中不会再改变结构可以提前指定ArrayList的初始容量减少扩容开销。我在某个项目的模拟系统里测试过容量从默认 10 提到vertexCount / 2之后建图时间缩短了约 15%虽然不算夸张但处理大图时积少成多。邻接表遍历一个顶点的所有邻居代价等于该顶点的度这是 Dijkstra 和 Prim 的堆优化版能够跑得快的基础。很多同学喜欢问“到底用哪个”我的经验是面试题里如果图顶点几百到几千用邻接矩阵方便快速讲思路OJ 或真实项目里无脑邻接表基本不会错。1.3 边集数组不是存储主体但两个算法离不开它边集数组就是单纯把每条边记录成一个对象扔到一个数组里。Kruskal 算法需要全局按权值排序Bellman-Ford 需要反复松弛所有边这两种场景下边集数组比邻接表和矩阵都方便。public class EdgeSet { static class Edge implements ComparableEdge { int from; int to; int weight; Edge(int from, int to, int weight) { this.from from; this.to to; this.weight weight; } Override public int compareTo(Edge other) { return this.weight - other.weight; } } ListEdge edges new ArrayList(); public void addEdge(int from, int to, int weight) { edges.add(new Edge(from, to, weight)); } }我在整理模板的时候喜欢把三种存储方式都备好需要哪个拿哪个。图算法这东西很多时候不是不会而是存储结构没选对导致算法代码写起来异常别扭。这个点特别值得记住。2. 最小生成树Prim 算法代码实战最小生成树解决的是带权无向图中用 n-1 条边把所有顶点连起来并且总权值最小的方案。现实里的场景包括通信网络布线、低成本道路规划、电力网络设计这些都能直接套最小生成树模型。2.1 Prim 的核心思路和实现细节Prim 算法思想是“从一个顶点开始让树慢慢长大”。维护一个inTree数组标记顶点是否已经加入生成树维护一个dist数组记录每个未加入顶点到当前生成树的最小距离。每次选择距离最小的顶点加入然后更新它所有邻居的距离。为什么这个贪心策略是对的因为生成树最终要连成一个整体每一步扩展时离“现有树”最近的顶点加入后一定不会破坏已生成部分的性质这个数学归纳法的证明比较绕但代码落实后就清爽多了。public class Prim { private int[][] graph; private int vertexCount; private static final int INF Integer.MAX_VALUE / 2; public Prim(int[][] graph) { this.graph graph; this.vertexCount graph.length; } public int primMST() { boolean[] inTree new boolean[vertexCount]; int[] dist new int[vertexCount]; Arrays.fill(dist, INF); dist[0] 0; int totalWeight 0; for (int i 0; i vertexCount; i) { int u -1; int minDist INF; for (int v 0; v vertexCount; v) { if (!inTree[v] dist[v] minDist) { minDist dist[v]; u v; } } if (u -1) return -1; // 图不连通 inTree[u] true; totalWeight minDist; for (int v 0; v vertexCount; v) { if (!inTree[v] graph[u][v] dist[v]) { dist[v] graph[u][v]; } } } return totalWeight; } }这段代码有几个坑要特别提醒第一个选最小距离顶点时u初始化为-1后如果图不连通minDist会一直是INF此时应该提前返回或者抛异常否则后续逻辑会出问题。很多模板代码没有这层判断导致不连通图里出现诡异结果。第二个graph[u][v] dist[v]这里不能加等号没有意义而且如果dist和graph相等时频繁赋值白白浪费操作。第三个初始化dist[0] 0意味着从 0 号顶点开始构建。如果 0 号顶点孤立会发现最小距离顶点选不出来最后返回 -1。这个行为其实是合理的说明图本身不连通不存在生成树。我用一段实际测试数据验证一下。假设有 5 个顶点边分别为0-1 权值 20-3 权值 61-2 权值 31-3 权值 81-4 权值 52-4 权值 73-4 权值 9。运行这段 Prim 代码从顶点 0 开始依次加入次序是 0、1、2、4、3总权值为 2 3 5 6 16。这个结果与手工推演一致。2.2 Prim 的朴素版与堆优化版选哪个上面是朴素版时间 O(V²)空间 O(V)。适合顶点数不超过几千的稠密图。但如果图的边数很少、顶点很多朴素版扫一遍找最小顶点的操作就显得很蠢。堆优化版用优先队列维护“顶点到树的距离”每次从堆顶弹出最小元素配合visited数组跳过已处理的陈旧记录。时间复杂度降为 O(E log V)。一开始会觉得堆优化版更高级但注意优先队列里会存在大量陈旧元素内存占用可能达到 O(E)稀疏图没问题稠密图反而更费内存。我给一个保守建议如果边数和顶点数差不多稀疏图用堆优化如果边数接近 V²/2稠密图用朴素版因为 O(V²) 扫一遍反而比维护堆更快。实际测试中稠密图用堆优化版经常表现不如朴素版原因就是堆操作常数较大。3. 最小生成树Kruskal 算法代码实战3.1 并查集是 Kruskal 的幕后功臣Kruskal 的思路比 Prim 更直观把边按权值从小到大排序依次加入只要加入后不形成环就保留直到加入 n-1 条边为止。判断是否形成环靠并查集。最开始每个顶点都是独立的集合边两端顶点如果属于不同集合说明这条边可以安全连接两个连通分量如果已经属于同一集合说明再加就成环了。public class Kruskal { private int[] parent; private int[] rank; public int kruskalMST(ListEdgeSet.Edge edges, int vertexCount) { parent new int[vertexCount]; rank new int[vertexCount]; for (int i 0; i vertexCount; i) { parent[i] i; rank[i] 0; } Collections.sort(edges); int totalWeight 0; int edgeCount 0; for (EdgeSet.Edge edge : edges) { if (edgeCount vertexCount - 1) break; int rootFrom find(edge.from); int rootTo find(edge.to); if (rootFrom ! rootTo) { union(rootFrom, rootTo); totalWeight edge.weight; edgeCount; } } return edgeCount vertexCount - 1 ? totalWeight : -1; } private int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } private void union(int x, int y) { if (rank[x] rank[y]) { parent[x] y; } else if (rank[x] rank[y]) { parent[y] x; } else { parent[y] x; rank[x]; } } }并查集这里建议加路径压缩和按秩合并。路径压缩是递归里那行parent[x] find(parent[x])它让查询复杂度趋近 O(1)。按秩合并则在 union 时把矮的树接到高的树上防止并查集退化成链表。两个技巧加起来整个 Kruskal 的瓶颈就只剩排序了也就是 O(E log E)。3.2 Kruskal 在稀疏图和大图中的优势Kruskal 的时间和顶点数几乎无关主要受边数影响。Prim 的朴素版要遍历顶点边多了不慌、顶点多了就慢Kruskal 则完全相反顶点再多也不影响它的排序成本。所以实际选型时可以这样记忆稠密图找 Prim稀疏图找 Kruskal。稀疏图中边数和顶点数接近E log E 和 E log V 差不多但 Kruskal 不用实现复杂的邻接表堆优化代码结构更直观出错概率更小。我还遇到过一类题所有边权都相同。此时排序后的顺序无所谓Kruskal 随便选但 Prim 会因为“第一个顶点选谁”而影响边加入顺序结果依然是最小生成树只是中间过程不同。这个概念值得记一下面试时偶尔会被问到。4. 最短路径Dijkstra 算法代码实战4.1 Dijkstra 只适用于非负权图Dijkstra 应该是五个算法里最常用的。思路和 Prim 有点神似但语义不同Prim 的dist记录到“生成树”的距离Dijkstra 的dist记录到“源点”的距离。每次选中一个距离源点最近的未确定顶点然后尝试用它去更新邻居的距离。为什么它不能处理负权因为 Dijkstra 的贪心假设是“一旦某个顶点被确定为最短路就不会再被其他顶点更新”。如果存在负权边可能有一条路径通过一个“当前看起来比较远”的顶点再走一条负权边反而让某个已经确定的顶点距离更短直接推翻贪心假设。我用 Java 实现了一个邻接表 优先队列的版本这个版本在实战中使用频率最高public class Dijkstra { private static final int INF Integer.MAX_VALUE / 2; public int[] dijkstra(GraphList graph, int source) { int n graph.vertexCount; int[] dist new int[n]; Arrays.fill(dist, INF); dist[source] 0; PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[1])); pq.offer(new int[]{source, 0}); while (!pq.isEmpty()) { int[] current pq.poll(); int u current[0]; int d current[1]; if (d dist[u]) continue; for (GraphList.Edge edge : graph.getNeighbors(u)) { int v edge.to; int nd d edge.weight; if (nd dist[v]) { dist[v] nd; pq.offer(new int[]{v, nd}); } } } return dist; } }优先队列里我存的是int[]{顶点编号, 当前距离}。每次弹出一个元素时如果d dist[u]说明这个元素是某个顶点被更新之前留下的陈旧记录直接跳过。这个跳过操作很重要不然会出现莫名其妙多出来的耗时。4.2 代码里容易踩的两个细节第一个graph.getNeighbors(u)拿到的边对象不要在循环里修改它的to或weight因为邻接表是共享对象一旦改动会影响后续遍历。这看似是常识但不少人图方便直接改边结果跑第二次算法就全乱了。第二个如果源点本身无法到达某个顶点那个顶点的dist会一直是INF。输出结果时建议约定一个规则比如输出 -1 或者Integer.MAX_VALUE / 2本身不要在算法内部擅自更改否则后续逻辑反而难以判断。我在某次模拟网络拓扑最短路径的项目里源点有将近 3 万个顶点使用邻接表加堆优化Dijkstra 完成一次全量最短路计算大约几十毫秒。如果是邻接矩阵的朴素版光初始化矩阵就要遍历 9 亿次差距非常明显。5. 最短路径Bellman-Ford 算法代码实战5.1 负权边和负环检测Bellman-Ford 的存在理由只有一个处理带负权边的图。它的思路谈不上巧妙就是暴力。对所有的边重复松弛 V-1 轮每轮都尝试用当前已知的最短距离去更新邻居。由于一条最短路最多包含 V-1 条边所以 V-1 轮后必然收敛。如果第 V 轮还能更新距离说明图里存在负权环。所谓负权环就是某个环上所有边权之和小于零绕圈可以让路径总长无限变小最短路不存在。public class BellmanFord { private static final int INF Integer.MAX_VALUE / 2; public boolean bellmanFord(ListEdgeSet.Edge edges, int vertexCount, int source, int[] dist) { Arrays.fill(dist, INF); dist[source] 0; for (int i 0; i vertexCount - 1; i) { boolean updated false; for (EdgeSet.Edge edge : edges) { if (dist[edge.from] ! INF dist[edge.from] edge.weight dist[edge.to]) { dist[edge.to] dist[edge.from] edge.weight; updated true; } } if (!updated) break; } for (EdgeSet.Edge edge : edges) { if (dist[edge.from] ! INF dist[edge.from] edge.weight dist[edge.to]) { return false; } } return true; } }有个细节dist[edge.from] ! INF这个判断不能省。如果源点根本到不了from那么dist[from]是无穷大加上权值依然很大虽然不会影响最终结果但如果不做判断可能出现INF 负数比INF小的情况导致把不可达顶点错当成可达。5.2 优化技巧提前退出和 SPFA代码里加了一个updated标志如果某一轮没有任何更新说明当前所有 dist 已经收敛可以提前退出循环。这在稀疏图里能省下不少时间尤其是接近最短路已经求出的情况下。SPFA 是 Bellman-Ford 的队列优化版。它只把“距离发生变化的顶点”重新加入队列需要更新它的出边。最坏情况时间复杂度依然是 O(VE)但实际运行时通常比朴素 Bellman-Ford 快很多。不过要注意SPFA 对负环检测有一套额外的入队次数计数逻辑一个顶点入队超过 V 次就认为存在负环这个判断必须严谨。我在工程里通常不用 SPFA 处理正权图因为正权图直接用 Dijkstra 更快。SPFA 的价值集中在负权边场景尤其是题目明确说没有负环时。6. 最短路径Floyd 算法代码实战6.1 三重循环的背后是动态规划Floyd 可能是五个算法里代码量最小的三行就完事。它的原理是动态规划设dist[k][i][j]表示只允许经过前 k 个中间顶点时从 i 到 j 的最短路。状态转移就是“经过第 k 个顶点”或者“不经过第 k 个顶点”三维状态可以直接压成二维在循环里原地更新。public class Floyd { private static final int INF Integer.MAX_VALUE / 2; public int[][] floyd(int[][] graph) { int n graph.length; int[][] dist new int[n][n]; for (int i 0; i n; i) { dist[i] Arrays.copyOf(graph[i], n); } for (int k 0; k n; k) { for (int i 0; i n; i) { for (int j 0; j n; j) { if (dist[i][k] ! INF dist[k][j] ! INF dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } return dist; } }这里必须把中间顶点k放在最外层循环。如果k放在最内层就会破坏动态规划的无后效性得到的结果大概率是错的。这个坑在面试里经常被拿出来问原理就是二维状态压缩后必须先枚举阶段再枚举状态转移。Floyd 能处理负权边但不能处理负权环。检测方法和 Bellman-Ford 类似跑完之后看对角线上dist[i][i]是否为负数如果是说明存在从 i 出发又回到 i 的负环此时最短路无意义。6.2 路径记录与多源场景很多应用不仅要知道最短距离还想知道完整路径。Floyd 也可以记录路径步骤是维护一个next[i][j]初始为j每当dist[i][j]被更新时让next[i][j] next[i][k]这样最后可以顺着next数组一路找到路径经过的顶点。Floyd 最大的问题是 O(V³)2000 个顶点就是 80 亿次迭代跑起来非常吃力。所以它适合顶点数几百左右的多源最短路场景。例如我要算一个城市交通网中所有地点两两之间的最短距离顶点 200 个Floyd 就很合适顶点 5000 个就必须换成跑 V 次 Dijkstra用堆优化大概 V × E log V稀疏图反而效率更高。7. 五个算法的横向对比与选型速查很多同学学完这五个算法后脑子里是一团浆糊因为每个算法模板长得差不多但适用场景又微妙地不同。我做了一个简单对比表建议收藏算法解决的问题时间复杂度能否处理负权典型存储结构应用场景Prim最小生成树朴素 O(V²) / 堆优化 O(E log V)不适用邻接矩阵 / 邻接表稠密图、网络布线Kruskal最小生成树O(E log E)不适用边集数组稀疏图、大顶点数Dijkstra单源最短路径朴素 O(V²) / 堆优化 O(E log V)不能处理负权邻接表优先正权稀疏图Bellman-Ford单源最短路径O(VE)可处理负权、可检测负环边集数组负权边、负环判断Floyd多源最短路径O(V³)可处理负权、不能有负环邻接矩阵小规模多源查询从另一个维度理解最小生成树是“让全图连通的最便宜方案”最短路径是“从一个点到另一个点的最短路”。前者关注的是全局收益后者关注的是单点效率。如果你的应用关心“所有城市连通总布线费用最低”那就是最小生成树问题如果你的应用关心“从A城市开车到B城市最快”那就是最短路径问题。我在实际工作中见过一个比较典型的误用场景某个同事要规划园区管网上来就用 Dijkstra 跑跑半天出来一个奇怪结果。其实他要的是每个片区都能通水属于典型的最小生成树问题。所以遇到实际问题先判别“目标函数是全局连通还是单点最短”比马上写代码重要得多。8. 实战排坑与学习路径建议8.1 必看的三个高频坑第一个坑是 INF 溢出。处理距离更新时如果初始化用Integer.MAX_VALUE一旦发生INF weight就会得到负数导致后续判断全乱。我建议统一使用Integer.MAX_VALUE / 2或者在计算前判断是否为 INF两种方式选一个固定执行。第二个坑是图不连通。Kruskal 在结束时判断edgeCount vertexCount - 1就能发现不连通Prim 通过返回 -1 提示Dijkstra 和 Floyd 会留下无穷大距离。不要假装连通图数据显示有多少个可达分量就按多少个处理否则结果完全没意义。第三个坑是邻接表本身的方向。有向图和无向图的 addEdge 实现不同很多人只写了一个方法导致无向图忘加反向边最小生成树直接变成有向树结果自然是错的。建议把addUndirectedEdge单独实现代码语义清晰也不容易忘。8.2 建议的练习路径如果是第一次系统学这块建议顺序是先手写邻接表和邻接矩阵 → 用 Prim 跑通一个 6 顶点小图 → 用 Kruskal 跑通同一个图对比结果 → 用 Dijkstra 求单源最短路 → 引入负权边再用 Bellman-Ford → 最后用 Floyd 验证多源结果。不要一上来就刷题。小图手算一遍再用代码跑一遍两个结果对得上才算真正掌握。很多同学考试时算法能默写但题目稍微变化就不会了根本原因是缺少“手算对照”这个环节。8.3 最后分享一个个人经验我在刚开始学习这几个算法时曾经连续三天在 Bellman-Ford 上栽跟头后来发现问题是初始化时忘了把源点的 dist 设为 0。这种低级错误其实特别常见因为它藏在一个看起来人畜无害的Arrays.fill(dist, INF)后面。后来我把所有算法模板都封装成统一的接口每次跑之前先打印初始 dist核对一遍源点、邻接表、边集数组的完整性基本能把 80% 的低级错误挡在运行之前。写图算法最忌讳“背模板但不理解”。我的习惯是每个模板后面都跟着一份小数据的手算过程代码写完之后跑一遍和手算结果对比。这样调试一次远比刷十道题更有用。后续遇到变种题目时只需要在这个理解基础上加条件不会慌。
