【笔记】数据结构与算法之最小生成树（Prim算法）

QingYi.

[Java] 纯文本查看 复制代码

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

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bf.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        //init
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g[i][j] = INF;
            }
        }
        while (m-- > 0){
            String[] res = bf.readLine().split(" ");
            int a = Integer.parseInt(res[0]);
            int b = Integer.parseInt(res[1]);
            int c = Integer.parseInt(res[2]);
            //无向图 两边都可以指向，且重边，选最小值
            g[a][b] = g[b][a] = Math.min(g[a][b],c);
        }
        int t = prim();
        if (t==INF){
            System.out.println("impossible");
        }else {
            System.out.println(t);
        }
    }

    private static int prim() {
        //init
        Arrays.fill(dist,INF);
        int res = 0;
        //下面这部分和Dijkstra很相似
        for (int i = 0; i < n; i++) {
            int t = -1;
            for(int j = 1;j<=n;j++){
                if (!st[j] && (t==-1 || dist[t]>dist[j])){
                    t=j;
                }
            }
            //找不到 无连通，直接return
            if (i!=0 && dist[t]==INF){
                return INF;
            }
            //否则就累加距离
            if (i!=0){
                res+=dist[t];
            }
            //更新
            //注意这里和Dijkstra的不同，一个是起点需要加上dist[t]
            //一个是集合，直接g[t][j]
            for(int j = 1;j<=n;j++){
                dist[j] = Math.min(dist[j],g[t][j]);
            }
            //当前的点设置为用过了
            st[t] = true;
        }
        return res;
    }
}

w1100312

沙发。。。。。。。。。。。。。。。。。。。。。。。。。

一人之下123456

感谢楼主的分享，看着源码学习了