9-Prim算法

算法思想

1. 任选一个节点加入生成树
2. 选择一个最近的节点加入生成树
   1. 距离生成树最近的节点
3. 重复步骤2，直至所有连通的节点到被加入生成树

算法模板

import java.util.*;

public class Main {
    static int N = 510,
        INF = 0x3f3f3f3f;
    static int[][] g = new int[N][N];
    // dist[i]存储 i 号节点（到局部最小生成树）的最短距离
    static int[] dist = new int[N];
    // st[i]标记 i 号节点是否被加入到（局部）最小生成树
    static boolean[] st = new boolean[N];
    static int n, 
        m;
        
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        
        for(int i = 1; i <= n; i ++ ) Arrays.fill(g[i], INF);

        while(m -- > 0)
        {
            int from = in.nextInt(), to = in.nextInt(), weight = in.nextInt();
            g[from][to] = Math.min(g[from][to], weight);
            g[to][from] = g[from][to];
        }
        
        int t = prim();
        if(t == INF) System.out.println("impossible");
        else System.out.println(t);
    }
    
    static int prim()
    {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        
        // 执行 n 次，尝试将所有节点加入生成树        
        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 || dist[j] < dist[t]))
                    t = j;
            }
            
            // 存在无法到达的节点，
            // 说明当前图无法连通，不存在最小生成树
            if(dist[t] == INF) return INF;
            
            res += dist[t];
            st[t] = true;
            
            // 更新节点（到局部最小生成树）的最短距离
            for(int j = 1; j <= n; j ++ ) 
                dist[j] = Math.min(dist[j], g[t][j]);
        }
        
        return res;
    }
}