贪心算法实战：Dijkstra、Prim与Kruskal的Java实现与工程选型

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中）。

迭代过程：

1. 第一轮：从未确定集合中找距离最小的顶点，即A（dist=0）。将A加入集合S。然后松弛A的邻居：B(0+6=6 < ∞，更新)， D(0+1=1 < ∞，更新)。此时状态：S={A}, dist: A=0, B=6, C=∞, D=1, E=∞。
2. 第二轮：未确定集合{B,C,D,E}中，距离最小的是D（dist=1）。将D加入S。松弛D的邻居：B(1+2=3 < 6，更新！), E(1+1=2 < ∞，更新)。此时状态：S={A,D}, dist: A=0, B=3, C=∞, D=1, E=2。
3. 第三轮：未确定集合{B,C,E}中，距离最小的是E（dist=2）。将E加入S。松弛E的邻居：B(2+2=4 > 3，不更新), C(2+5=7 < ∞，更新)。此时状态：S={A,D,E}, dist: A=0, B=3, C=7, D=1, E=2。
4. 第四轮：未确定集合{B,C}中，距离最小的是B（dist=3）。将B加入S。松弛B的邻居：C(3+5=8 > 7，不更新)。此时状态：S={A,D,E,B}, dist: A=0, B=3, C=7, D=1, E=2。
5. 第五轮：最后剩下C（dist=7），加入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; } }

注意：这里使用邻接矩阵graph，graph[u][v]表示边(u,v)的权重，0表示无边。minDistance函数通过线性扫描寻找最小值，这是朴素实现O(V²)复杂度的主要来源。

方式二：堆优化实现（邻接表）这是工程中最常用的版本，尤其适合顶点多、边相对稀疏的图。它使用优先队列（最小堆）来高效获取当前距离最小的顶点。

public class DijkstraHeap { public int[] dijkstra(List<int[]>[] graph, int src) { int V = graph.length; int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; // 优先队列，按距离从小到大排序。元素为数组 [顶点, 距离] PriorityQueue<int[]> 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; } } // 图的构建示例（邻接表）： // List<int[]>[] 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((V+E) log V)，在稀疏图（E远小于V²）中优势巨大。

一个必须警惕的坑：代码中的if (d > dist[u]) continue;这行至关重要。因为当我们更新某个顶点v的距离时，我们会将{v, newDist}加入优先队列，而不是更新队列中已有的旧记录。队列中可能同时存在同一个顶点的多个不同距离的条目。这个“惰性删除”技巧避免了在优先队列中实现复杂的 decrease-key 操作（Java的PriorityQueue原生不支持），是既简单又高效的通用写法。我第一次实现时就漏掉了这个判断，导致算法逻辑错误，在一些复杂图上得到了错误结果。

2.3 应用场景与边界思考

Dijkstra算法是许多实际系统的基石。例如，在网络路由协议（如OSPF）中，每个路由器都维护着一个本地区的网络拓扑图，使用Dijkstra算法计算到所有其他路由器的最短路径，从而构建路由表。在地图导航中，它被用于计算两点间的最短行车时间（假设交通状况恒定）。在分布式系统中，有时也用它来建模任务调度或数据传播的成本。

然而，必须牢记它的边界条件：

1. 负权边：Dijkstra算法不能处理带有负权边的图。因为它的贪心策略基于“当前最小距离即最终距离”的假设，一旦存在负权边，这个假设就不成立了，可能通过后续的负权边找到更短的路径。对于含负权边的图，需要使用Bellman-Ford或SPFA算法。
2. 大规模图与性能：对于超大规模图（例如数亿顶点），即使是堆优化版，单次全源计算也可能很慢。在实际的导航系统中，往往会采用更高级的加速技术，如A*算法（结合启发式搜索）、Contraction Hierarchies（收缩层次）或自定义的预处理分区技术。
3. 路径重建：上述代码只计算了最短距离。如果需要具体路径，需要维护一个prev[]数组，在松弛操作更新dist[v]时，同步记录prev[v] = u。算法结束后，从目标点逆向回溯prev数组即可得到路径。

3. Prim算法：一步步“生长”出最小生成树

最小生成树（Minimum Spanning Tree, MST）是指在一个带权无向连通图中，找到一个边的子集，使得这些边连接了所有顶点，且其总权重最小，并且不形成任何环。Prim算法的贪心策略与Dijkstra神似，但目标不同：它从一个顶点开始，每次选择一条连接“已访问顶点集合”和“未访问顶点集合”的权重最小的边，并将该边连接的未访问顶点纳入集合，直到所有顶点都被访问。

3.1 算法流程与直观理解

你可以把Prim算法想象成“修路”。假设要在几个村庄之间修路，使得所有村庄连通且总成本最低。我们从一个村庄开始：

1. 查看从这个村庄能修到其他所有村庄的路，选择最便宜的那条修通。
2. 现在有两个村庄连通了。查看所有从这两个已连通村庄能修到其他未连通村庄的路，再次选择最便宜的一条修通。
3. 重复步骤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(List<int[]>[] 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值] PriorityQueue<int[]> 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; } }

实现要点与避坑指南：

1. 边的数据结构：输入通常是一个边列表，每条边包含两个顶点和权重。这比邻接表或邻接矩阵更直接。
2. 排序开销：算法的时间复杂度主要取决于排序，为O(E log E)。对于稀疏图（E ~ O(V)），这比朴素Prim的O(V²)好得多。
3. 并查集优化：务必实现路径压缩和按秩合并。我见过一些实现只做了路径压缩，或者用了最原始的parent[x] = find(parent[x])但不做按秩合并，在极端数据下（比如链状的合并）可能导致find操作退化成O(n)，大幅影响性能。上面的实现是经过充分优化的标准写法。
4. 图不连通的处理：最小生成树只存在于连通图中。如果遍历完所有边后，收集到的边数仍不足V-1，则说明原图不连通，不存在MST。上面的代码通过检查edgesUsed并返回-1来处理这种情况。

4.3 为何Kruskal是贪心算法？

Kruskal的贪心性体现在它“每次都选当前未考虑过的最小权边”。为什么这个局部最优选择能导致全局最优？关键在于“按权重排序”和“避环”。假设我们有一条全局最小的边e1，它必然属于某个MST（可用反证法证明）。Kruskal首先选中它。之后，在考虑其他边时，如果加入会与已选边形成环，就说明这条边的两个端点已经通过其他更小的边连通了，那么这条更大的边自然不应该被选入任何MST。这个过程可以归纳证明最终得到的就是全局MST。

5. 三大算法对比与工程选型建议

学完了三个算法，我们最后来做一个横向对比，这能帮助你在实际场景中做出最合适的选择。

工程选型心法：

1. 先看问题：是找“最短路径”还是“最小生成树”？这直接决定了用Dijkstra还是后两者。
2. 再看图密度：
   • 如果你的图非常稠密（边数E接近V²），并且需要求MST，朴素Prim往往是性能最好的选择，常数小，实现也不复杂。
   • 如果你的图比较稀疏（E远小于V²），或者你拿到的输入数据直接就是边列表，那么Kruskal是更自然、更简洁的选择。排序后配合并查集，逻辑清晰，不易出错。
3. 最后看实现便利性：
   • 对于最短路径，堆优化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, C，dist(A->C) <= dist(A->B) + dist(B->C)。

写图算法代码，就像在脑子里模拟一个动态过程。我最受用的调试方法，就是在关键步骤打印出dist、key、parent数组或并查集的状态，然后拿一个简单的例子，用纸笔手动跑一遍算法，逐行对照程序的中间输出。这个过程虽然慢，但能帮你对算法的每一个细节都建立起牢固的直觉。当你下次再遇到类似问题时，这种直觉会让你更快地定位到问题所在。