数据范围

2 <= V <= 10000;//表示节点数量范围

1 <= E <= 100000;//表示边的数量范围

0 <= val <= 10000;//表示权值范围

最小生成树之prim算法

最小生成树 是所有节点的 最小连通子图，即：以最小的成本（边的权值总和最小）将图中的所有节点连接在一起。

图中有n个节点，那么一定可以用n-1条边将所有节点连接到一起。

那么如何从题目给出的m条边中选出n-1条边（m > n-1）就是最小生成树算法的任务所在。

在该图中，一共有7个节点，只需要选择6条边就可以将所有节点连接到一起。

prim算法是从节点的角度采用贪心的策略每次寻找距离 最小生成树 最近的 节点，然后将该节点加入到这个 最小生成树 中。

prim算法三部曲如下：

1、第一步，选距离 最小生成树 最近 的 节点

2、第二步，将该 最近节点 加入 生成树

3、第三步，更新 非生成树 节点 到 生成树 的距离（即更新minDist数组）

minDist数组的作用是记录每一个节点距离最小生成树的最近距离。

初始状态：

minDist数组里的数值初始化为最大数，因为本题节点距离（也就是权值）不会超过10000，所以初始化最大数为10001就可以。

现在还没有最小生成树，默认每个节点距离最小生成树都是最大的，这样后面在比较的时候，发现更近的距离，才能更新到minDist数组上。

开始构造最小生成树：

prim三部曲第一步：选距离生成树最近节点

选择距离最小生成树最近的节点，加入到最小生成树。刚开始还没有最小生成树，所以随便选一个节点加入就好（因为每一个节点一定会在最小生成树里，所以随便选一个就好），所以我们就选节点1。

prim三部曲第二步：最近节点加入生成树

此时节点1已经算最小生成树的节点了

prim三部曲第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

更新过程如下图：

下标0就不用管了，因为我们是从下标1开始遍历，防止混淆

此时所有非生成树的节点距离 最小生成树（节点1） 的距离都已经更新了。

节点2与节点1的距离为1，比原先的距离值10001小，所以更新minDist[2]。

节点3和节点1的距离为1，比原先的距离值10001小，所以更新minDist[3]。

节点5和节点1的距离为2，比原先的距离值10001小，所以更新minDist[5]。

图中标记了minDist数组里更新的权值，并且还表明了哪两个节点之间的权值。例如minDist[2]=1，这个1是节点1与节点2之间的连线。

后面就是不断重复prim三部曲

最后生成了一个最小生成树，绿色的边将所有节点连接到一起，并且保证权值是最小的，因为我们在更新minDist数组的时候，都是选距离最小生成树最近的点加入到树中。

最后,minDist数组记录了最小生成树所有边的权值。

将最小生成树中的权值总和累加到一起就是最终结果。

import java.util.*;

//prim算法
//面向节点的
public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int v = scanner.nextInt();
        int e = scanner.nextInt();
        //minDist存放每一个节点距离最小生成树的最近距离
        int[] minDist = new int[v + 1];
        for(int i = 0; i < minDist.length; i++){
            minDist[i] = 10001;
        }
        //构建邻接矩阵 存放 图
        int[][] grid = new int[v + 1][v + 1];
        //初始化，所有权重值都设置为最大值，方便后续比较
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                grid[i][j] = 10001;
            }
        }
        //输入图
        for(int i = 0; i < e; i++){
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            int val = scanner.nextInt();
            //无向图，双方都要赋值
            grid[l][r] = val;
            grid[r][l] = val;
        }
        boolean[] isInTree = new boolean[v + 1];
        //开始prim的逻辑
        for(int i = 1; i < v; i++){//一共是v个节点，我们只需要v-1条边就可以，所以这里循环是从1到v-1，一共需要记录v-1条边，后面的两个for循环是遍历的全部v个节点，所以从1到v。
            int cur = -1;//记录放入生成树的节点
            int minVal = Integer.MAX_VALUE;//用于更新权值
            //第一步：选距离生成树最近的节点
            for(int j = 1; j <= v; j++){//见前面讲解
                if(!isInTree[j] && minDist[j] < minVal){
                    minVal = minDist[j];
                    cur = j;
                }
            }
            //第二步：将该节点加入到生成树
            isInTree[cur] = true;
            //第三步：更新非生成树节点到生成树的距离
            for(int j = 1; j <= v; j++){//见前面讲解
                if(!isInTree[j] && grid[cur][j] < minDist[j]){
                    minDist[j] = grid[cur][j];
                }
            } 
        }
//遍历minDist数组，累加结果
        int result = 0;
        for(int i = 2; i < minDist.length; i++){
            result += minDist[i];
        }
        System.out.print(result);
    }   
}

最小生成树之kruskal算法

prim算法是面向节点的，而kruskal算法是面向边的

思路：

1、按照边的权值进行排序，因为要优先选最小的边加入到生成树里

2、遍历排序后的边

（1）如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环

（2）如果边首尾的两个节点不在同一个集合（判断逻辑调用并查集find()方法），加入到最小生成树（体现在代码逻辑上就是累加这条边的权值），并把两个节点加入到同一个集合（调用并查集join方法）

对边的定义可以用一个类Edge来实现，设置三个属性，分别代表左节点、右节点、边权值

class Edge{
    int l;
    int r;
    int val;
    //构造函数初始化
    public Edge(int l, int r, int val){
      this.l = l;
      this.r = r;
      this.val = val;
    } 
}

整体可运行代码如下：

import java.util.*;

public class Main{
    //并查集的逻辑
    private static int[] father = new int[10001];
    //1.初始化
    public static void init(){
        for(int i =0; i < father.length; i++){
            father[i] = i;
        }
    }
    //2.节点u和v加入同一个集合
    public static void join(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v) return;
        father[v] = u;
    }
    //3.查找节点u的根节点
    public static int find(int u){
        return u == father[u] ? u : (father[u] = find(father[u]));
    }
    //4.判断u和v是否在同一个集合
    public static boolean isSame(int u, int v){
        u = find(u);
        v = find(v);
        return u == v;
    }
    //主函数入口
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int v = scanner.nextInt();
        int e = scanner.nextInt();
        //存放边的集合
        List<Edge> edgeList = new ArrayList<>();
        for(int i = 0; i < e; i++){
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            int val = scanner.nextInt();
            edgeList.add(new Edge(l, r, val));
        }
        int result = 0;
        //初始化并查集
        init();
        //Kruskal算法
        //先排序
        edgeList.sort(Comparator.comparingInt(edge -> edge.val));
        //遍历排序后的边
        for(Edge edge : edgeList){
            if(!isSame(edge.l, edge.r)){
            //说明不在同一集合，加入到最小生成树，
            //并把两个节点加入到同一个集合
               result += edge.val;
               join(edge.l, edge.r);
            }
        }
        System.out.print(result);    
    }   
}

class Edge{
    public int l;
    public int r;
    public int val;
    //构造函数初始化
    public Edge(int l, int r, int val){
      this.l = l;
      this.r = r;
      this.val = val;
    } 
}

时间复杂度分析：

nlogn（快排）+ logn（并查集），最后依然是nlogn。

总结：

Prim算法面向节点操作，时间复杂度是O(n^2)，其中n是节点的数量，适用于节点少，边多的图

Kruskal算法面向边操作，时间复杂度是O(nlogn)，其中n是边的数量，适用于边少，节点多的图。