知识点

最小生成树：一般都是针对无向图来说的，分为两种算法

• 普利姆算法算法（Prim）
• 朴素版Prim：O（n^2^）稠密图，用邻接矩阵来存
• 堆优化版Prim：O（mlogn）稀疏图，用邻接表来存
• 克鲁斯卡尔算法（Kruskal）：O（mlogm）：稀疏图

算法思想

1：for n ，迭代n次

2：for1 ~ n，在还未确定最短路的点中，寻找距离最小的点

3：判断是否为最小生成树，更新res

3：for1 ~ n，用t更新其他点到集合的距离

4：把t加入到集合中去

需要注意的问题

1：可以看出来，prim算法和Dijkstra算法是很像的，可以类比着去记忆

需要注意的是，Dijkstra算法更新的是所有点距离起点的最短距离，而prim更新的是所有点距离集合的最短距离

Dijkstra算法中的st[]表示的是该点是否已经确定最短距离了，而prim的st[]表示的是是否已经在最小生成树上了

2：i != 0 有什么含义

i != 0 代表的是不是第一次迭代，因为第一次迭代并不是所有点的距离都会进行初始化，初始化的是第一个点的所有出度，所以一定要加上这个条件

因此，if (i != 0 && dist[t] == INF) return INF;这句话的含义就是不是第一次迭代，距离集合最近的点还没有初始化，说明就不是一个连通图，就可以返回结果了

3：第一次迭代

第一次迭代因为有条件i != 0的限制，并不会更新res的值，而是在以后的迭代中不断更新，况且d[1] = 0,更新了也没有用

代码

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    static int N = 510;
    static int[][] g = new int[N][N];
    static int[] d = new int[N];
    static boolean[] st = new boolean[N];
    static int n , m ,INF = 0x3f3f3f3f;

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        m = in.nextInt();

        for(int i = 0;  i < N; i ++) Arrays.fill(g[i],INF);

        for(int i = 0; i < m; i ++)
        {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            g[a][b] = g[b][a] = Math.min(g[a][b],c);
        }

        int t = prim();

        if(t == INF) System.out.print("impossible");
        else System.out.print(t);
    }

    private static int prim()
    {
        Arrays.fill(d,INF);

        int res = 0;
        for(int i = 0; i < n; i ++)          //迭代的是点的个数
        {
            int t = -1;
            for(int j = 1; j <= n; j ++)     //循环的也是点的个数
            {
                if(!st[j] && (t == -1 || d[t] > d[j])) t = j;
            }

            if(i != 0 && d[t] == INF) return INF;
            if(i != 0) res += d[t];

            for(int j = 1; j <= n; j ++) d[j] = Math.min(d[j], g[t][j]);
            st[t] = true;
        }
        return res;
    }
}