在图论的众多算法中，Kruskal 算法以其简洁高效的特性，成为求解最小生成树（Minimum Spanning Tree，MST）的经典方法。无论是在通信网络的优化设计、电路布线的成本控制，还是在计算机考研 408 的备考过程中，Kruskal 算法都占据着重要的地位。

Kruskal 算法的基本概念

在介绍 Kruskal 算法之前，我们需要先明确几个关键概念：

图：由顶点（节点）集合和边集合组成，边可以有权值，用于表示顶点之间的关系和连接代价。

生成树：对于一个连通图，它的生成树是包含图中所有顶点的无环连通子图。

最小生成树：在带权连通图的所有生成树中，边的权值之和最小的生成树称为最小生成树。

Kruskal 算法的目标，就是在给定的带权连通图中，找到这样一棵最小生成树。例如，在一个城市间的通信网络建设中，每个城市是图的顶点，城市间铺设通信线路的成本是边的权值，Kruskal 算法可以帮助我们找到成本最低的网络连接方案。

Kruskal 算法的思想

Kruskal 算法基于贪心策略，其核心思想是：在图中选取权值最小的边，若该边加入已选边集合后不会形成环，则将其加入；不断重复这个过程，直到选取的边构成一棵包含图中所有顶点的树，此时得到的树就是最小生成树。

具体执行过程如下：

初始化：将图中的所有边按照权值从小到大进行排序，并初始化一个空的边集合用于存储最小生成树的边，同时将每个顶点看作一个独立的集合（利用并查集数据结构实现）。

遍历边集：依次遍历排序后的边集合，对于每条边，检查其两个端点是否属于不同的集合（即是否会形成环）。如果属于不同集合，则将该边加入最小生成树的边集合中，并合并两个端点所在的集合；如果属于相同集合，则跳过该边，因为加入后会形成环。

结束条件：当最小生成树的边集合中包含n - 1条边时（n为图中顶点的数量），停止遍历，此时得到的边集合构成的树即为最小生成树。

Kruskal 算法的解题思路

利用 Kruskal 算法解决实际问题时，一般遵循以下步骤：

构建图模型：根据题目描述，将问题抽象为带权连通图，确定顶点集合、边集合以及每条边的权值。

初始化并查集：为图中的每个顶点创建一个独立的集合，用于后续判断边加入后是否会形成环。

边排序：将图中的所有边按照权值从小到大进行排序。

执行 Kruskal 算法：遍历排序后的边集合，按照算法规则选取边加入最小生成树的边集合中，同时使用并查集维护顶点集合的连通性。

处理结果：根据题目要求，返回最小生成树的边集合、边的权值之和，或者进行其他相关处理。

LeetCode 例题及 Java 代码实现

例题：网络延迟时间（LeetCode 1135）

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n - 1。线缆用 connections 表示，其中 connections[i] = [a_i, b_i, cost_i] 连接计算机 a_i 和 b_i ，费用为 cost_i。请你计算将所有计算机连接成一个网络的最低成本。如果无法将所有计算机连接成一个网络，则返回 -1 。

解题思路

本题可以将计算机看作图的顶点，线缆连接看作边，连接费用看作边的权值，问题转化为求图的最小生成树的权值之和。使用 Kruskal 算法，先对边按权值排序，然后通过并查集判断边加入后是否成环，逐步构建最小生成树，最后计算最小生成树的权值之和。如果最终选取的边数小于n - 1，则说明无法连接所有计算机，返回 -1 。

代码实现

import java.util.Arrays;import java.util.Comparator;public class MinimumCostToConnectSticks {// 并查集的父节点数组private int[] parent;// 初始化并查集private void init(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}// 查找节点的根节点private int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}// 合并两个节点所在的集合private boolean union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY;return true;}return false;}public int minimumCost(int n, int[][] connections) {init(n);// 按边的权值从小到大排序Arrays.sort(connections, Comparator.comparingInt(c -> c[2]));int cost = 0;int count = 0;for (int[] connection : connections) {int a = connection[0] - 1;int b = connection[1] - 1;int weight = connection[2];if (union(a, b)) {cost += weight;count++;if (count == n - 1) {break;}}}return count == n - 1 ? cost : -1;}}

例题：重新安排行程（LeetCode 332）

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

如果存在多种有效的行程，请你按字典排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

所有的机场都用三个大写字母表示（机场代码）。

假定所有机票至少存在一种合理的行程。

所有的机票必须都用一次且只能用一次。

解题思路

本题可以将机场看作顶点，机票看作边，构建一个图。由于要求按字典序最小的行程，我们可以先对边（机票）进行排序，然后利用类似 Kruskal 算法的思想，从JFK出发，逐步选取边构建路径。在构建过程中，使用深度优先搜索（DFS）来遍历图，确保所有边都被使用一次且仅一次。

代码实现

import java.util .*;public class ReconstructItinerary {private Map<String, PriorityQueue<String>> graph;private List<String> result;private void dfs(String airport) {PriorityQueue<String> nextAirports = graph.get(airport);while (nextAirports != null && !nextAirports.isEmpty()) {dfs(nextAirports.poll());}result.add(0, airport);}public List<String> findItinerary(List<List<String>> tickets) {graph = new HashMap<>();for (List<String> ticket : tickets) {String from = ticket.get(0);String to = ticket.get(1);graph.putIfAbsent(from, new PriorityQueue<>());graph.get(from).offer(to);}result = new ArrayList<>();dfs("JFK");return result;}}

Kruskal 算法与考研 408

在计算机考研 408 中，Kruskal 算法是数据结构和算法部分的重要考点，主要涉及以下几个方面：

算法原理与实现：考生需要熟练掌握 Kruskal 算法的基本原理、执行步骤和代码实现。常考查算法的初始化过程、边的排序方法、并查集的使用，以及如何通过贪心策略构建最小生成树。例如，要求考生分析算法在给定图上的执行过程，或者写出算法的伪代码或具体实现代码。

时间复杂度与空间复杂度：Kruskal 算法的时间复杂度主要由边的排序和并查集操作决定。边排序的时间复杂度为\(O(E \log E)\)（\(E\)为边的数量），并查集操作的时间复杂度近似为\(O(E \alpha(V))\)（\(V\)为顶点数量，\(\alpha(V)\)是一个增长极其缓慢的函数，可近似看作常数），因此整体时间复杂度为\(O(E \log E)\)。空间复杂度主要用于存储边集合和并查集，为\(O(E + V)\)。考研 408 中可能会考查对这些复杂度的分析和理解。

与其他最小生成树算法的对比：Prim 算法也是求解最小生成树的常用算法，考研 408 中可能会考查 Kruskal 算法与 Prim 算法的对比。例如，分析它们的适用场景（Kruskal 算法适用于稀疏图，Prim 算法适用于稠密图）、时间复杂度和空间复杂度的差异等。

算法的应用与变形：考研 408 中可能会出现基于 Kruskal 算法的变形题目，结合实际问题进行考查。例如，在最小生成树的基础上增加限制条件（如限制某些边必须包含或不能包含），要求考生灵活运用 Kruskal 算法的思想进行求解。这需要考生深入理解算法本质，能够将算法原理应用到不同的场景中。

在备考过程中，建议考生通过做大量的练习题来加深对 Kruskal 算法的理解，熟练掌握算法的各种细节。同时，对比学习 Prim 算法等相关内容，形成系统的知识体系，提高在考试中的解题能力。