最近做大题目主要运用的都是数据结构方面的题，既有之前的最短路径的相关的算法，也有现在的最小生成树，这里先讲解Kruskal算法，主要是我先在刚会这个，prim算法，明天再看。 Kruskal算法算法其实和之前的djs算法有点类似，主要还是每次循环找出局部最优解，也就是最小权重的那条路，一次寻找即可，这里作者一开始俊德实现起来并不麻烦，但之后发现，循环找出最优解不是最麻烦的，大不了每次排序 如果只是单纯的按照权重来选择，肯定是这样选择的1—>2,1—>4,2—>4，这样的话会出现两个问题，第一个就是出现了环即1—>2—>4—>1这样显然是不行的，第二问题就是，这样选择出来的点事不全的，缺少了 3这个点，所以选择路径的时候不仅是要看权重，还应该看选择的路径是否会构成环这种不允许出现的情况，其实重点就是这里，为了防止出现这种情况，我们又需要了解并查集这个概念，就是简单的如果两个数是一类的，那么我们就将它们合并 接下来就是最简单的最小生成树以及并查集的代码了： import java.util.Arrays; import java.util.HashSet; import java.util.Scanner;