贪心算法精讲：Dijkstra、Prim与Kruskal的Java实现与核心原理

1. 项目概述贪心算法在图论中的经典应用最近在整理算法笔记发现很多朋友对贪心算法在图论中的应用尤其是Dijkstra最短路径和Prim、Kruskal最小生成树这几个经典算法总是感觉“似懂非懂”。大家能看懂代码但一到自己动手实现或者面试被问到“为什么这里要用贪心策略”时就容易卡壳。这其实很正常因为这些算法不仅仅是几行代码其背后是“局部最优导致全局最优”这一贪心思想的精妙体现以及对图这种数据结构特性的深刻理解。今天我就结合自己这些年刷题和项目中的经验用Java把这三个算法从头到尾实现一遍。我们不止步于“实现”更要深挖每一步“为什么”要这么做。比如Dijkstra算法为什么不能处理负权边Prim和Kruskal看似都生成最小树核心区别和适用场景到底是什么我会把代码实现、原理解析、避坑心得以及一些教科书上不会讲的调试技巧都揉碎了分享给你。无论你是正在准备面试还是想在项目中优化网络路由或连接成本这篇文章都能给你提供可直接“抄作业”的扎实参考。2. 核心思路与算法选型背后的逻辑在动手写代码之前我们必须先搞清楚这三个算法解决的是什么问题以及为什么贪心策略在这里是有效的。这决定了我们后续数据结构的选择和代码的架构。2.1 问题定义与贪心策略的契合点我们面对的是“图”。图由顶点Vertex和边Edge组成。边可以有权重Weight代表距离、成本或时间。最短路径问题Dijkstra给定一个带权有向图或无向图和一个起点源点求该点到图中所有其他点的最短路径长度。贪心思想体现在每次从未确定最短路径的顶点中选择一个距离起点最近的顶点并“确认”它的最短距离。一旦确认就不再更改。这基于一个关键假设当前离起点最近的顶点其最短路径不可能通过其他未确认顶点而变得更短。这个假设在所有权重非负时才成立这就是Dijkstra处理不了负权边的根本原因。最小生成树问题Prim Kruskal给定一个带权无向连通图找出一棵包含所有顶点的树使得树上所有边的权重之和最小。这棵树就是最小生成树MST。贪心思想体现在通过逐步添加“当前看来最优”的边来构建这棵树。Prim算法的贪心是“从顶点出发”。它维护一个不断增长的子树集合每次选择连接该子树与外界顶点的权重最小的边。这保证了每一步都在扩大这棵“最小”的子树。Kruskal算法的贪心是“从边出发”。它不考虑顶点集合而是将所有边按权重从小到大排序然后依次尝试添加边如果加入这条边不会在已选边中形成环就加入。这保证了每次加入的都是当前可用的、不会破坏树结构的“最小”边。2.2 数据结构选型为什么是它们算法的效率很大程度上取决于数据结构。这里的选择是经过权衡的。图的存储我们采用邻接表。对于稀疏图边数远小于顶点数的平方邻接表在空间和时间上通常优于邻接矩阵。它用ListListint[]或ListEdge[]来表示每个顶点维护一个列表存储其邻接点及边权。注意在Prim和Kruskal中因为是无向图添加边时需要同时更新两个顶点的邻接表。Dijkstra算法的核心优先队列堆需求需要频繁地从“未确认顶点集合”中取出距离起点最近的那个顶点。选择朴素实现需要每次遍历所有未确认顶点时间复杂度为O(V²)。使用最小堆Min-Heap优化的优先队列可以将“取出最小值”和“更新距离后调整”的操作降到O(log V)。Java中直接使用PriorityQueue。Prim算法的核心优先队列堆需求需要频繁地从“连接已选顶点集合和未选顶点集合的边”中取出权重最小的那条边或者说取出通过这条边连接的、离当前生成树最近的未选顶点。选择同样使用PriorityQueue来维护一个“切边集合”cut存储所有一端在树内、一端在树外的边或其连接的顶点。Kruskal算法的核心并查集Union-Find需求需要高效地判断加入一条边后是否会形成环。即判断这条边连接的两个顶点是否已经连通。选择并查集是解决动态连通性问题的完美数据结构。它支持近乎O(1)时间的“查找”和“合并”操作远超使用DFS/BFS每次判断的O(VE)时间。把这些思路理清代码的骨架就出来了。接下来我们进入具体的实现环节。3. 代码实现与逐行解析我会先给出每个算法的完整、可运行的Java代码然后对关键行进行详细解释并附上我调试时常用的测试用例。3.1 基础结构图与并查集首先我们定义边Edge这个通用结构并实现并查集因为Kruskal会用到它。// 通用的边类用于Kruskal和邻接表表示 class Edge implements ComparableEdge { int from, to, weight; public Edge(int from, int to, int weight) { this.from from; this.to to; this.weight weight; } Override public int compareTo(Edge other) { return Integer.compare(this.weight, other.weight); } } // 并查集 (Union-Find) 实现 class UnionFind { private int[] parent; private 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; // 合并成功 } }关键点解析Edge类实现了Comparable接口方便在Kruskal中直接用Arrays.sort()或优先队列排序。并查集的优化find操作中的parent[x] find(parent[x])是路径压缩能将查找路径上的所有节点直接挂到根节点下极大加速后续查找。union操作中的rank比较是按秩合并总是将矮树合并到高树上避免树退化成链表。这两点是并查集高效近乎常数时间的核心务必理解。3.2 Dijkstra最短路径算法实现我们实现返回从源点src到所有点最短距离数组的版本。public class Dijkstra { // 使用邻接表表示图: graph.get(u) 返回一个列表每个元素是int[]{v, weight} public int[] dijkstra(ListListint[] graph, int src) { int n graph.size(); // 顶点数 int[] dist new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] 0; // 优先队列按距离排序 [顶点, 距离] PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[1])); pq.offer(new int[]{src, 0}); boolean[] visited new boolean[n]; // 可选的用于标记已确认的顶点 while (!pq.isEmpty()) { int[] curr pq.poll(); int u curr[0]; int d curr[1]; // 关键优化如果队列中取出的距离大于当前记录的距离说明是旧数据跳过 if (d dist[u]) { continue; } // visited[u] true; // 如果需要严格区分可以在这里标记 // 松弛操作遍历u的所有邻接边 for (int[] neighbor : graph.get(u)) { int v neighbor[0]; int w neighbor[1]; int newDist dist[u] w; if (newDist dist[v]) { dist[v] newDist; pq.offer(new int[]{v, newDist}); // 注意这里可能将同一个顶点多次加入队列 } } } return dist; } // 辅助方法构建邻接表图 public static ListListint[] buildGraph(int n, int[][] edges) { ListListint[] graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } for (int[] edge : edges) { int u edge[0], v edge[1], w edge[2]; graph.get(u).add(new int[]{v, w}); // 如果是无向图需要添加反向边 // graph.get(v).add(new int[]{u, w}); } return graph; } }关键点解析与避坑dist数组初始化起点距离为0其他点为无穷大Integer.MAX_VALUE。优先队列的使用存储[顶点, 当前计算出的距离]。队列中同一个顶点可能以不同距离出现多次当它被多次松弛时。if (d dist[u]) continue;这行至关重要这是处理队列中“过时”条目stale entry的标准做法。因为当我们发现顶点u的一条更短路径时我们会将[u, newDist]再次加入队列。之前加入的那个更长的[u, oldDist]就变成了无效数据。这行代码就是“懒惰删除”直接跳过它们。没有这行算法逻辑正确但效率会降低。松弛操作这是算法的核心。对于边u-v如果dist[u] w dist[v]说明找到了到v的更短路径更新dist[v]并将[v, newDist]入队。负权边问题想象一条负权边。假设我们已经“确认”了顶点A的最短距离但后来通过一个负权边从B到A使得dist[B] (-10) dist[A]这破坏了Dijkstra“已确认顶点距离不再改变”的前提。所以算法会出错。对于含负权边的图需要使用Bellman-Ford或SPFA算法。3.3 Prim最小生成树算法实现Prim算法返回最小生成树的所有边及其总权重。public class PrimMST { // 返回最小生成树的边列表和总权重 public int primMST(ListListint[] graph) { int n graph.size(); boolean[] inMST new boolean[n]; // 标记顶点是否已在MST中 PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[1])); // [顶点, 连接到该顶点的边权] int totalWeight 0; ListEdge mstEdges new ArrayList(); // 可选用于存储构成的边 // 从顶点0开始任意起点均可 pq.offer(new int[]{0, 0}); while (!pq.isEmpty()) { int[] curr pq.poll(); int u curr[0]; int weight curr[1]; // 如果该顶点已经在MST中跳过 if (inMST[u]) { continue; } // 将顶点u加入MST inMST[u] true; totalWeight weight; // 注意第一次弹出的weight是0起点不加入边列表 if (weight ! 0) { // 这里需要记录边但pq中只存了顶点和权不知道来自哪个顶点。 // 一种改进是存储Edge对象或三元组[from, to, weight] } // 将u的所有未在MST中的邻接边加入优先队列 for (int[] neighbor : graph.get(u)) { int v neighbor[0]; int w neighbor[1]; if (!inMST[v]) { pq.offer(new int[]{v, w}); } } } // 检查是否所有顶点都连通即MST包含所有顶点 for (boolean inTree : inMST) { if (!inTree) { return -1; // 图不连通无法形成MST } } return totalWeight; } // 改进版能记录生成树边的Prim实现 public static class PrimWithEdges { public ListEdge prim(ListListEdge graph) { int n graph.size(); boolean[] visited new boolean[n]; PriorityQueueEdge pq new PriorityQueue(); // 直接存边 ListEdge mst new ArrayList(); // 从顶点0开始添加所有从0出发的边 visited[0] true; for (Edge edge : graph.get(0)) { pq.offer(edge); } while (!pq.isEmpty() mst.size() n - 1) { Edge edge pq.poll(); if (visited[edge.to] visited[edge.from]) { continue; // 两端都在树内这条边会形成环跳过 } // 将边加入MST mst.add(edge); // 确定新加入的顶点是哪个 int newVertex visited[edge.from] ? edge.to : edge.from; visited[newVertex] true; // 将新顶点的所有连接未访问顶点的边加入队列 for (Edge nextEdge : graph.get(newVertex)) { int other (nextEdge.from newVertex) ? nextEdge.to : nextEdge.from; if (!visited[other]) { pq.offer(nextEdge); } } } return mst.size() n - 1 ? mst : new ArrayList(); // 返回边列表若不成树则返回空 } } }关键点解析与避坑inMST数组这是Prim算法的状态记录标记哪些顶点已经包含在生成树中。优先队列的内容第一个简单实现中队列存的是[顶点, 权值]这个权值是从当前MST到该顶点的最短边的权重。当我们弹出u时weight就是连接u到MST的那条边的权重。if (inMST[u]) continue;和Dijkstra一样同一个顶点可能因为多条边被多次加入队列只有第一次弹出对应连接它的最小边是有效的。起点选择与总权重从任意顶点开始都可以。第一次弹出的weight是0起点到自己的距离所以累加总权重时要从第二次开始。totalWeight初始为0第一次加0不影响。改进版记录边第一个实现无法记录具体是哪条边构成了MST。改进版使用Edge对象的优先队列并更精细地判断边的两端顶点状态从而能记录下所有被选中的边。这是更完整的实现。连通性检查最后遍历inMST数组如果存在false说明图不是连通的无法形成包含所有顶点的生成树。3.4 Kruskal最小生成树算法实现Kruskal的实现相对更简洁清晰。public class KruskalMST { public ListEdge kruskal(int n, Edge[] edges) { // 1. 按边权从小到大排序 Arrays.sort(edges); UnionFind uf new UnionFind(n); ListEdge mst new ArrayList(); int totalWeight 0; // 2. 遍历排序后的边 for (Edge edge : edges) { // 3. 使用并查集判断加入此边是否会形成环 if (uf.union(edge.from, edge.to)) { // 不会形成环加入MST mst.add(edge); totalWeight edge.weight; // 如果已经找到 n-1 条边可以提前结束 if (mst.size() n - 1) { break; } } } // 4. 检查是否成功生成MST if (mst.size() ! n - 1) { // 图不连通无法形成包含所有顶点的MST return new ArrayList(); } System.out.println(MST Total Weight: totalWeight); return mst; } // 使用示例 public static void main(String[] args) { int n 4; Edge[] edges new Edge[]{ new Edge(0, 1, 10), new Edge(0, 2, 6), new Edge(0, 3, 5), new Edge(1, 3, 15), new Edge(2, 3, 4) }; KruskalMST solver new KruskalMST(); ListEdge result solver.kruskal(n, edges); for (Edge e : result) { System.out.println(e.from - e.to : e.weight); } } }关键点解析与避坑排序这是Kruskal的第一步也是其时间复杂度主要部分O(E log E)。并查集判环uf.union(from, to)是关键。如果两个顶点已经在同一个集合中即已连通union返回false说明加入这条边会形成环舍弃。如果不在同一集合union将其合并并返回true边加入MST。提前终止一棵包含n个顶点的最小生成树有且仅有n-1条边。所以当mst中边数达到n-1时就可以立即结束循环这是一个有效的优化。连通性检查循环结束后如果MST中的边数小于n-1说明原图不是连通的。复杂度排序O(E log E)并查集操作近似O(E α(V))其中α是阿克曼函数的反函数增长极慢近乎常数。因此总复杂度约为O(E log E)适合稀疏图。4. 对比、应用场景与实战心得三个算法都实现了我们来做个横向对比并聊聊在什么情况下该用哪个。4.1 算法对比速查表特性Dijkstra (最短路径)Prim (最小生成树)Kruskal (最小生成树)解决问题单源最短路径最小生成树最小生成树贪心对象顶点离源点最近的未确认点顶点/边离当前MST最近的顶点边当前未使用的最小权边核心数据结构优先队列 (最小堆)优先队列 (最小堆)并查集 边排序时间复杂度O((VE) log V)O((VE) log V)O(E log E)适用图类型带权有向/无向图 (边权非负)带权无向连通图带权无向图可处理非连通图得到森林是否需要连通否求到各点距离不连通则为INF是必须连通图否非连通图得到的是最小生成森林结果形式从源点到所有点的距离数组一棵树边的集合一棵树或森林边的集合常用场景网络路由如OSPF、地图导航、资源分配网络布线、电路板设计、聚类分析网络设计、图像分割、稀疏图MST4.2 场景选择与实战心得Dijkstra vs Prim虽然都用优先队列但解决的问题截然不同。有一次面试我被要求“求一个无向图中所有点对的最短距离”。我第一反应是跑V次Dijkstra。面试官接着问“如果图非常稠密边权都是正数且需要多次查询有没有更优方案”这引出了Floyd-Warshall算法动态规划O(V³)适合预处理后快速查询。而Prim完全不适合解决路径问题。Prim vs Kruskal这是最常被比较的。图稠密时用Prim当图接近完全图E ≈ V²时Prim的复杂度O(V²)使用邻接矩阵和普通数组或O((VE)log V)使用邻接表和堆可能优于Kruskal的O(E log E)因为E很大log E也大。图稀疏时用Kruskal通常Kruskal更简单易实现且由于排序是主要开销在边数E相对较少时非常高效。更重要的是Kruskal天然支持并行排序在海量数据场景下有优势。需要边列表时用KruskalKruskal算法直接对边进行操作最终结果也是边列表非常直观。Prim的简单实现只计算总权重记录边需要额外处理如改进版所示。实战踩坑在实现Prim时我曾忘记处理“跳过已在MST中的顶点”的逻辑导致队列中无效边被重复累加结果权重远大于实际。务必记住那个continue判断。4.3 测试与调试技巧纸上得来终觉浅自己写测试用例跑一遍才能真正掌握。public class GraphAlgorithmTest { public static void main(String[] args) { // 测试用例1一个简单的无向连通图 int n 5; int[][] edges { {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {2, 4, 7}, {3, 4, 9} }; // 1. 测试Dijkstra (以0为源点) ListListint[] graphForDijkstra buildGraphForDijkstra(n, edges, false); // 构建无向图 Dijkstra dijkstra new Dijkstra(); int[] dist dijkstra.dijkstra(graphForDijkstra, 0); System.out.println(Dijkstra distances from node 0: Arrays.toString(dist)); // 预期: [0, 2, 5, 6, 7] // 2. 测试Prim ListListint[] graphForPrim buildGraphForDijkstra(n, edges, false); // 同样用无向图 PrimMST prim new PrimMST(); int mstWeightPrim prim.primMST(graphForPrim); System.out.println(Prim MST total weight: mstWeightPrim); // 预期: 16 (边: 0-1(2), 1-2(3), 0-3(6), 1-4(5)) // 3. 测试Kruskal Edge[] edgeArray new Edge[edges.length]; for (int i 0; i edges.length; i) { edgeArray[i] new Edge(edges[i][0], edges[i][1], edges[i][2]); } KruskalMST kruskal new KruskalMST(); ListEdge mstEdges kruskal.kruskal(n, edgeArray); System.out.println(Kruskal MST edges:); int totalWeight 0; for (Edge e : mstEdges) { System.out.println(e.from - e.to : e.weight); totalWeight e.weight; } System.out.println(Kruskal MST total weight: totalWeight); // 预期总权重也是16边可能顺序不同但集合相同 } static ListListint[] buildGraphForDijkstra(int n, int[][] edges, boolean directed) { ListListint[] graph new ArrayList(); for (int i 0; i n; i) graph.add(new ArrayList()); for (int[] e : edges) { graph.get(e[0]).add(new int[]{e[1], e[2]}); if (!directed) { graph.get(e[1]).add(new int[]{e[0], e[2]}); } } return graph; } }调试心得从小图开始先用3-5个顶点的小图手动算出预期结果再与程序输出对比。验证负权边构造一个带负权边的图给Dijkstra跑观察输出是否错误加深对算法前提的理解。可视化对于复杂的图可以手动画出来或者用简单的打印方式将邻接表、距离数组、MST边列表打印出来逐步跟踪算法状态。边界测试测试只有一个顶点的图、不连通的图、所有边权重相同的图等特殊情况。5. 常见问题与性能优化深度探讨在实际编码和面试中总会遇到一些典型问题。这里我总结几个高频的。5.1 Dijkstra算法中为什么优先队列里同一个顶点会出现多次如何正确理解这是Dijkstra优化实现中最让人困惑的点之一。根本原因在于我们采用的是“懒惰删除”策略。当首次发现到达顶点v的路径时我们将其[v, dist1]加入队列。后来如果通过另一个顶点u找到了到v的更短路径dist2dist2 dist1我们会更新dist[v] dist2并再次将[v, dist2]加入队列。此时队列中就有两个关于v的条目一个旧的距离大一个新的距离小。当旧条目被弹出时我们通过if (d dist[u]) continue;发现它已经过时直接跳过。只有最新的、距离最小的那个条目被弹出时d dist[v]才会执行后续的松弛操作。这种做法的好处是避免了在优先队列中实现复杂的“减少键”操作简化了代码。虽然可能让队列体积变大但在稀疏图中其时间复杂度依然是O((VE) log V)。5.2 Prim和Kruskal得到的MST一定唯一吗不一定。当图中存在多条权重相同的边时最小生成树可能不唯一。例如一个正方形的四条边权重都是1。Prim从某个角开始和Kruskal按顺序选边可能会得到不同的生成树比如一个是“Z”字形一个是“7”字形但它们的总权重是相同的。 在面试中如果被问到“如何得到所有MST”问题就变得复杂了通常需要回溯或使用更复杂的算法。5.3 如何选择邻接表还是邻接矩阵邻接表适合稀疏图。空间复杂度O(VE)遍历某个顶点的所有邻接边很快。我们上面的实现都基于邻接表。邻接矩阵适合稠密图或者需要频繁判断任意两个顶点间是否有边、边权是多少的场景。空间复杂度O(V²)。对于Prim算法如果图非常稠密使用邻接矩阵配合普通数组而非堆来实现时间复杂度是O(V²)有时比基于堆的O((VE)log V)更优因为常数因子小。5.4 算法变体与扩展思考Dijkstra求具体路径我们的实现只计算了最短距离。如果需要打印路径可以维护一个int[] prev数组在松弛操作更新dist[v]时同步记录prev[v] u。最后从终点反向回溯到起点即可。第K短路径这不是简单的Dijkstra变种通常需要使用A*算法或Yens算法。最小生成树次小边有时需要求“次小生成树”即权重第二小的生成树。一个经典做法是先求出MST然后尝试用非树边替换树中的某条边找到权重增加最小的那种替换。并行化Kruskal由于Kruskal的第一步是对所有边排序这个操作可以很容易地并行化例如使用并行排序算法。在超大规模图计算中这是一个显著优势。最后我个人的体会是理解这三个算法关键不在于背下代码而在于吃透其背后的贪心选择策略和数据结构如何支撑这一策略。Dijkstra的“当前最近即全局最近”、Prim的“不断扩大最小子树”、Kruskal的“从小到大加边且不构成环”这些思想才是精髓。下次当你遇到一个新的优化问题时不妨想想这个问题有没有“贪心”的选择性质能不能用堆或者并查集来高效维护这个选择过程这样你就真正把算法学活了。