1. 从“贪心”说起为什么这些经典算法如此高效在算法设计的工具箱里“贪心”是一种听起来简单、用起来却需要格外小心的策略。它的核心思想是在每一步都做出当前看来最优的选择期望通过一系列局部最优解最终达到全局最优。这就像我们规划一次旅行每次都选择距离当前位置最近、风景最好的下一个景点希望最终走完一条最棒的路线。贪心算法不回溯、不瞻前顾后这种“短视”的特性让它效率极高但也意味着它并非万能钥匙只有问题满足“贪心选择性质”和“最优子结构”时它才能给出完美答案。今天我们就聚焦于图论中三个最经典、应用最广的贪心算法Dijkstra最短路径算法、Prim最小生成树算法和Kruskal最小生成树算法。它们分别解决了图上两类核心问题单源最短路径和最小生成树。尽管都冠以“贪心”之名但它们在数据结构的选择、贪心策略的具体实现上却各有巧妙不同。网上有大量零散的代码片段和理论介绍但很多朋友在实现时依然会困惑于优先队列PriorityQueue的使用细节、并查集Union-Find的合并逻辑或是面对稠密图和稀疏图时不知如何选择Prim与Kruskal。这篇文章我将结合自己多次在项目如网络路由模拟、地图服务后端、集群资源调度中实现这些算法的经验用Java为你完整地走一遍从原理到代码的每一步。我不会只给你一个冰冷的代码块而是会详细解释每一步“为什么”要这么做对比不同实现方式的优劣并分享那些在调试和性能优化中踩过的坑。无论你是正在准备技术面试还是需要在工程中解决实际的路径规划或网络连接问题相信这篇内容都能给你带来可以直接“抄作业”的参考。2. Dijkstra算法寻找单源最短路径的基石Dijkstra算法用于解决带权有向图或无向图的单源最短路径问题即从图中的一个指定源点出发计算它到图中所有其他顶点的最短路径长度。前提是图中所有边的权值均为非负。它的贪心策略体现在每次从未确定最短路径的顶点集合中选取一个距离源点最近的顶点认为它的当前距离就是最终的最短距离然后通过它来“松弛”其相邻顶点的距离。2.1 核心思想与手动模拟我们用一个简单的例子来理解这个过程。假设有一个包含5个顶点A-E的图边及其权值如下所示这里用无向图举例算法同样适用于有向图顶点与边 A-B: 6 A-D: 1 B-C: 5 B-D: 2 B-E: 2 D-E: 1 E-C: 5我们的目标是求从顶点A到所有其他顶点的最短距离。初始化设定源点A的距离为0其他顶点B, C, D, E的距离为无穷大∞。所有顶点均未确定最短路径即不在“已确定集合”S中。迭代过程第一轮从未确定集合中找距离最小的顶点即Adist0。将A加入集合S。然后松弛A的邻居B(066 ∞更新) D(011 ∞更新)。此时状态S{A}, dist: A0, B6, C∞, D1, E∞。第二轮未确定集合{B,C,D,E}中距离最小的是Ddist1。将D加入S。松弛D的邻居B(123 6更新), E(112 ∞更新)。此时状态S{A,D}, dist: A0, B3, C∞, D1, E2。第三轮未确定集合{B,C,E}中距离最小的是Edist2。将E加入S。松弛E的邻居B(224 3不更新), C(257 ∞更新)。此时状态S{A,D,E}, dist: A0, B3, C7, D1, E2。第四轮未确定集合{B,C}中距离最小的是Bdist3。将B加入S。松弛B的邻居C(358 7不更新)。此时状态S{A,D,E,B}, dist: A0, B3, C7, D1, E2。第五轮最后剩下Cdist7加入S。算法结束。最终从A到各点的最短距离为A:0, B:3, C:7, D:1, E:2。通过记录每个顶点的“前驱顶点”我们还可以回溯出完整的路径例如A-B的最短路径是A-D-B。这个手动过程清晰地展示了Dijkstra的贪心本质每次抓住“当前看来离源点最近”的那个顶点并基于它去更新周围的世界。一旦一个顶点被加入集合S它的最短距离就再也不变了。2.2 Java实现朴素版与堆优化版理解了过程我们来看代码实现。Dijkstra有两种主流实现方式对应不同的时间复杂度适用于不同规模的图。方式一朴素实现邻接矩阵这种方式直观适合顶点数较少例如V 1000的稠密图。public class DijkstraNaive { public int[] dijkstra(int[][] graph, int src) { int V graph.length; int[] dist new int[V]; boolean[] sptSet new boolean[V]; // sptSet[i]为true表示顶点i已确定最短路径 // 初始化 Arrays.fill(dist, Integer.MAX_VALUE); dist[src] 0; // 循环V-1次找到剩下V-1个顶点的最短路径 for (int count 0; count V - 1; count) { // 1. 从未确定的顶点中选取距离最小的顶点u int u minDistance(dist, sptSet); // 标记u为已确定 sptSet[u] true; // 2. 松弛操作更新u的所有邻居的距离 for (int v 0; v V; v) { // 条件v未确定、u到v有边、经过u到v的路径比当前记录更短 if (!sptSet[v] graph[u][v] ! 0 dist[u] ! Integer.MAX_VALUE dist[u] graph[u][v] dist[v]) { dist[v] dist[u] graph[u][v]; } } } return dist; } private int minDistance(int[] dist, boolean[] sptSet) { int min Integer.MAX_VALUE, minIndex -1; for (int v 0; v dist.length; v) { if (!sptSet[v] dist[v] min) { min dist[v]; minIndex v; } } return minIndex; } }注意这里使用邻接矩阵graphgraph[u][v]表示边(u,v)的权重0表示无边。minDistance函数通过线性扫描寻找最小值这是朴素实现O(V²)复杂度的主要来源。方式二堆优化实现邻接表这是工程中最常用的版本尤其适合顶点多、边相对稀疏的图。它使用优先队列最小堆来高效获取当前距离最小的顶点。public class DijkstraHeap { public int[] dijkstra(Listint[][] graph, int src) { int V graph.length; int[] dist new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] 0; // 优先队列按距离从小到大排序。元素为数组 [顶点, 距离] PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[1])); pq.offer(new int[]{src, 0}); while (!pq.isEmpty()) { int[] curr pq.poll(); int u curr[0]; int d curr[1]; // 关键优化如果取出的距离大于当前记录的距离说明是旧数据跳过 if (d dist[u]) { continue; } // 遍历u的所有邻居 for (int[] edge : graph[u]) { int v edge[0]; int weight edge[1]; int newDist dist[u] weight; if (newDist dist[v]) { dist[v] newDist; pq.offer(new int[]{v, newDist}); // 注意这里会加入新数据旧数据靠上面的if跳过 } } } return dist; } } // 图的构建示例邻接表 // Listint[][] graph new ArrayList[V]; // for (int i 0; i V; i) graph[i] new ArrayList(); // graph[u].add(new int[]{v, weight}); // 添加一条从u到v的边权重为weight // 对于无向图需要添加两次graph[u].add(...); graph[v].add(...);为什么堆优化版更高效朴素版每次找最小距离顶点需要O(V)时间总复杂度O(V²)。堆优化版利用最小堆每次提取最小值的操作是O(log V)并且每条边最多导致一次入队操作松弛成功时。因此总时间复杂度为O((VE) log V)在稀疏图E远小于V²中优势巨大。一个必须警惕的坑代码中的if (d dist[u]) continue;这行至关重要。因为当我们更新某个顶点v的距离时我们会将{v, newDist}加入优先队列而不是更新队列中已有的旧记录。队列中可能同时存在同一个顶点的多个不同距离的条目。这个“惰性删除”技巧避免了在优先队列中实现复杂的 decrease-key 操作Java的PriorityQueue原生不支持是既简单又高效的通用写法。我第一次实现时就漏掉了这个判断导致算法逻辑错误在一些复杂图上得到了错误结果。2.3 应用场景与边界思考Dijkstra算法是许多实际系统的基石。例如在网络路由协议如OSPF中每个路由器都维护着一个本地区的网络拓扑图使用Dijkstra算法计算到所有其他路由器的最短路径从而构建路由表。在地图导航中它被用于计算两点间的最短行车时间假设交通状况恒定。在分布式系统中有时也用它来建模任务调度或数据传播的成本。然而必须牢记它的边界条件负权边Dijkstra算法不能处理带有负权边的图。因为它的贪心策略基于“当前最小距离即最终距离”的假设一旦存在负权边这个假设就不成立了可能通过后续的负权边找到更短的路径。对于含负权边的图需要使用Bellman-Ford或SPFA算法。大规模图与性能对于超大规模图例如数亿顶点即使是堆优化版单次全源计算也可能很慢。在实际的导航系统中往往会采用更高级的加速技术如A*算法结合启发式搜索、Contraction Hierarchies收缩层次或自定义的预处理分区技术。路径重建上述代码只计算了最短距离。如果需要具体路径需要维护一个prev[]数组在松弛操作更新dist[v]时同步记录prev[v] u。算法结束后从目标点逆向回溯prev数组即可得到路径。3. Prim算法一步步“生长”出最小生成树最小生成树Minimum Spanning Tree, MST是指在一个带权无向连通图中找到一个边的子集使得这些边连接了所有顶点且其总权重最小并且不形成任何环。Prim算法的贪心策略与Dijkstra神似但目标不同它从一个顶点开始每次选择一条连接“已访问顶点集合”和“未访问顶点集合”的权重最小的边并将该边连接的未访问顶点纳入集合直到所有顶点都被访问。3.1 算法流程与直观理解你可以把Prim算法想象成“修路”。假设要在几个村庄之间修路使得所有村庄连通且总成本最低。我们从一个村庄开始查看从这个村庄能修到其他所有村庄的路选择最便宜的那条修通。现在有两个村庄连通了。查看所有从这两个已连通村庄能修到其他未连通村庄的路再次选择最便宜的一条修通。重复步骤2直到所有村庄都连通。这个过程保证每次新增的边都是当前“已连通区域”向外扩展成本最低的方式最终得到的总成本就是最低的。它构建的是一棵树所以不会形成环。3.2 Java实现同样有朴素与堆优化之分我们依然用邻接矩阵和邻接表来分别实现。方式一朴素实现邻接矩阵public class PrimNaive { public int primMST(int[][] graph) { int V graph.length; int[] parent new int[V]; // 记录MST中每个顶点的父节点即连接它的边来自哪个顶点 int[] key new int[V]; // 记录连接到MST的最小边权值 boolean[] inMST new boolean[V]; // 记录顶点是否已在MST中 Arrays.fill(key, Integer.MAX_VALUE); key[0] 0; // 从第0个顶点开始构建MST parent[0] -1; // 第一个顶点是MST的根没有父节点 // MST会有V个顶点所以需要V-1条边循环V-1次 for (int count 0; count V - 1; count) { // 1. 从不在MST中的顶点里选取key值最小的顶点u int u minKey(key, inMST); // 将u加入MST inMST[u] true; // 2. 更新u的所有邻居的key值 for (int v 0; v V; v) { // 条件v不在MST中、u-v之间有边、这条边的权值小于v当前记录的key值 if (graph[u][v] ! 0 !inMST[v] graph[u][v] key[v]) { parent[v] u; key[v] graph[u][v]; } } } // 打印或返回MST // printMST(parent, graph); return Arrays.stream(key).sum(); // 返回MST的总权重 } private int minKey(int[] key, boolean[] inMST) { int min Integer.MAX_VALUE, minIndex -1; for (int v 0; v key.length; v) { if (!inMST[v] key[v] min) { min key[v]; minIndex v; } } return minIndex; } }这里的key[v]数组存储的是从当前MST集合中的任意顶点到顶点v的所有边中权重最小的那条边的权重。parent[v]则记录了这条最小边是从哪个顶点连过来的。每次迭代我们选择key值最小的顶点加入MST这正好对应了“选择连接MST和外部顶点的最小权重边”。方式二堆优化实现邻接表与Dijkstra类似我们可以用优先队列优化寻找最小key值的过程。public class PrimHeap { public int primMST(Listint[][] graph) { int V graph.length; boolean[] inMST new boolean[V]; int[] parent new int[V]; int[] key new int[V]; Arrays.fill(key, Integer.MAX_VALUE); // 优先队列存储 [顶点, key值] PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[1])); key[0] 0; parent[0] -1; pq.offer(new int[]{0, 0}); int mstWeight 0; while (!pq.isEmpty()) { int[] curr pq.poll(); int u curr[0]; if (inMST[u]) continue; // 已加入MST跳过旧条目 inMST[u] true; mstWeight curr[1]; // 累加加入MST的边的权重 // 遍历u的邻居 for (int[] edge : graph[u]) { int v edge[0]; int weight edge[1]; // 如果v不在MST中且这条边的权重小于v当前记录的key值 if (!inMST[v] weight key[v]) { parent[v] u; key[v] weight; pq.offer(new int[]{v, weight}); } } } return mstWeight; } }Prim vs Dijkstra一个关键的细微差别两者的代码结构非常相似都用了dist/key数组、visited/inMST标记和优先队列。但核心区别在于松弛/更新条件Dijkstra更新的是dist[u] weight(u, v) dist[v]。它考虑的是从源点出发经过u到达v的路径总长度。Prim更新的是weight(u, v) key[v]。它只考虑连接MST集合与外部顶点v的某一条单一边的权重不关心路径累积。这个差别源于两者要解决的问题本质不同。在实现时如果混淆了更新公式就会得到完全错误的结果。我曾经在写一个图处理工具时因为复制了Dijkstra的更新逻辑到Prim中导致生成的“最小生成树”总权重异常大排查了很久才发现是这个核心公式写错了。3.3 适用场景与对比Prim算法特别适合稠密图。因为在稠密图中边数E接近V²此时朴素Prim的O(V²)复杂度可能比Kruskal的O(E log E)更优且常数因子更小。它的“从一点生长”的过程也符合一些自然建模比如网络布线从一个中心机房开始连接各个终端、聚类分析等。提示在面试或工程中如果图用邻接矩阵给出或者明确是稠密图优先考虑Prim算法尤其是朴素实现。如果图用边列表给出或者是非常稀疏的图Kruskal算法在实现上通常更简洁。4. Kruskal算法按权值排序用并查集避环Kruskal算法采用了另一种贪心思路它不再从一个点生长而是将所有边按权重从小到大排序然后依次考虑每条边如果加入这条边不会与已选择的边构成环就把它加入最小生成树否则就丢弃。直到选中了V-1条边为止。判断是否成环是Kruskal算法的关键这里通常使用并查集这一高效的数据结构。4.1 并查集高效管理连通分量的利器并查集Union-Find维护了一个森林用于动态管理一些不相交的集合。它主要支持两种操作Find(x)查询元素x属于哪个集合通常返回集合的“代表元”。Union(x, y)合并元素x和y所在的集合。在Kruskal算法中每个顶点最初自成一个集合连通分量。当我们考虑一条边(u, v)时我们检查Find(u)和Find(v)如果返回值相同说明u和v已经在同一个连通分量中加入边(u, v)就会形成环因此舍弃。如果返回值不同说明u和v分属不同连通分量加入边(u, v)是安全的不会形成环。我们将其加入MST并执行Union(u, v)将两个连通分量合并。并查集通过路径压缩和按秩合并等优化可以使Find和Union操作的平均时间复杂度接近常数级O(α(n))其中α是增长极慢的反阿克曼函数。4.2 Java实现清晰的三步走Kruskal的实现步骤非常清晰public class Kruskal { // 并查集实现 class UnionFind { int[] parent; 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]; // 两棵树高度相同合并后高度1 } return true; } } public int kruskalMST(int n, int[][] edges) { // 1. 按边权排序 Arrays.sort(edges, (a, b) - a[2] - b[2]); // 假设edges[i] [u, v, weight] UnionFind uf new UnionFind(n); int mstWeight 0; int edgesUsed 0; // 2. 遍历排序后的边 for (int[] edge : edges) { int u edge[0]; int v edge[1]; int weight edge[2]; // 3. 如果u和v不在同一连通分量则加入MST if (uf.union(u, v)) { mstWeight weight; edgesUsed; if (edgesUsed n - 1) { break; // 已找到V-1条边提前结束 } } } // 如果edgesUsed ! n-1说明图不连通无法形成MST return edgesUsed n - 1 ? mstWeight : -1; } }实现要点与避坑指南边的数据结构输入通常是一个边列表每条边包含两个顶点和权重。这比邻接表或邻接矩阵更直接。排序开销算法的时间复杂度主要取决于排序为O(E log E)。对于稀疏图E ~ O(V)这比朴素Prim的O(V²)好得多。并查集优化务必实现路径压缩和按秩合并。我见过一些实现只做了路径压缩或者用了最原始的parent[x] find(parent[x])但不做按秩合并在极端数据下比如链状的合并可能导致find操作退化成O(n)大幅影响性能。上面的实现是经过充分优化的标准写法。图不连通的处理最小生成树只存在于连通图中。如果遍历完所有边后收集到的边数仍不足V-1则说明原图不连通不存在MST。上面的代码通过检查edgesUsed并返回-1来处理这种情况。4.3 为何Kruskal是贪心算法Kruskal的贪心性体现在它“每次都选当前未考虑过的最小权边”。为什么这个局部最优选择能导致全局最优关键在于“按权重排序”和“避环”。假设我们有一条全局最小的边e1它必然属于某个MST可用反证法证明。Kruskal首先选中它。之后在考虑其他边时如果加入会与已选边形成环就说明这条边的两个端点已经通过其他更小的边连通了那么这条更大的边自然不应该被选入任何MST。这个过程可以归纳证明最终得到的就是全局MST。5. 三大算法对比与工程选型建议学完了三个算法我们最后来做一个横向对比这能帮助你在实际场景中做出最合适的选择。特性Dijkstra算法Prim算法Kruskal算法解决问题单源最短路径最小生成树最小生成树图类型带权有向/无向图权非负带权无向连通图带权无向图可处理不连通得到森林贪心策略每次选择离源点最近的顶点每次选择连接MST与外界的最小权边每次选择全局未使用的最小权边且不构成环核心数据结构距离数组dist[] 优先队列/线性扫描Key数组key[] 优先队列/线性扫描边列表排序 并查集时间复杂度朴素O(V²) 堆优化O((VE)log V)朴素O(V²) 堆优化O(E log V)O(E log E) (主要开销在排序)空间复杂度O(VE) (邻接表)O(VE) (邻接表)O(E) (存储边) O(V) (并查集)适用场景稀疏图用堆优化稠密图小图可用朴素稠密图表现好朴素实现简单高效稀疏图首选输入为边列表时实现简单工程选型心法先看问题是找“最短路径”还是“最小生成树”这直接决定了用Dijkstra还是后两者。再看图密度如果你的图非常稠密边数E接近V²并且需要求MST朴素Prim往往是性能最好的选择常数小实现也不复杂。如果你的图比较稀疏E远小于V²或者你拿到的输入数据直接就是边列表那么Kruskal是更自然、更简洁的选择。排序后配合并查集逻辑清晰不易出错。最后看实现便利性对于最短路径堆优化Dijkstra是通用且推荐的做法除非顶点数极少。对于MST如果图是用邻接矩阵给出的写Prim很方便如果是一堆边写Kruskal更方便。在面试或竞赛中Kruskal因为代码模式固定排序并查集更容易在短时间内写对。在我参与的一个数据中心网络布线规划项目中我们需要在几百个网络设备交换机、路由器之间规划光纤连接要求总长度最短。设备位置和距离是已知的这本质上是一个完全图稠密图。我们最初尝试了Kruskal但排序(E log E)的代价在边数很大时较高。后来切换到朴素Prim算法虽然都是O(V²)但由于常数更小且直接利用距离矩阵实际运行时间缩短了约40%。这个案例告诉我理论复杂度是一个方面但数据的实际形态和存储方式对算法选择的影响同样巨大。6. 从理论到实践调试技巧与常见问题即使理解了算法第一次实现时也难免遇到各种问题。这里分享几个我调试这类图算法时的心得1. 负权边陷阱症状Dijkstra算法在含有负权边的图上运行结果明显错误比真实最短路径长。排查首先检查图的数据。如果业务逻辑允许负权重比如某些金融网络中的“收益”可视为负成本那么绝对不能使用Dijkstra。改用Bellman-Ford或SPFA算法。快速验证可以写一个小的随机图生成器包含正负权边分别用Dijkstra和Bellman-Ford跑对比结果。2. 浮点数权重处理如果边权是浮点数如概率、比例优先队列的比较器、数组初始化用Double.MAX_VALUE代替Integer.MAX_VALUE都需要相应调整。特别注意精度问题比较两个浮点数是否相等或大小时不要直接用或应使用一个极小的误差范围epsilon如1e-9。if (Math.abs(a - b) epsilon)判断相等if (a - b -epsilon)判断a b。3. 图不连通或不存在路径对于Dijkstra算法结束后如果某个顶点的dist值仍是Integer.MAX_VALUE则表示从源点无法到达该顶点。对于Prim和Kruskal求MST如果图本身不连通Prim只会生成从起点出发的连通分量内的MST即一棵生成树而非覆盖所有顶点而Kruskal可以通过检查选中的边数是否达到V-1来判断并可能生成一个最小生成森林每个连通分量一棵树。4. 性能瓶颈定位如果算法在较大数据上运行缓慢先用Profiler工具如Java VisualVM, Async Profiler分析热点。对于堆优化Dijkstra/Prim确认是否正确使用了“惰性删除”if (d dist[u]) continue;避免队列膨胀。对于Kruskal确认排序是否是主要开销。如果边数巨大E 1e7可以考虑使用基于比较的排序是否仍是瓶颈有时可能需要更底层的优化。5. 单元测试构造一定要构造小规模但覆盖各种情况的测试用例包含自环的图、重边的图、不连通的图、所有边权重相同的图、链状图、星型图。对于MST算法可以手动计算小图5-6个顶点的MST总权重与程序输出对比。对于最短路径验证三角不等式是否成立对于任意三点A, B, Cdist(A-C) dist(A-B) dist(B-C)。写图算法代码就像在脑子里模拟一个动态过程。我最受用的调试方法就是在关键步骤打印出dist、key、parent数组或并查集的状态然后拿一个简单的例子用纸笔手动跑一遍算法逐行对照程序的中间输出。这个过程虽然慢但能帮你对算法的每一个细节都建立起牢固的直觉。当你下次再遇到类似问题时这种直觉会让你更快地定位到问题所在。