最小生成树之普利姆算法

原题链接

题目描述

最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。
可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。

这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。
而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。

输入

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。

输出

只有一个整数，即最小生成树的总代价。请注意行尾输出换行。

样例输入

4
0 2 4 0
2 0 3 5
4 3 0 1
0 5 1 0

样例输出

6

解法：贪心

思路

1. 假设我先到城市1
2. 然后再基于我所到达的城市群中，依次看那些还没有到过（不出现回路）的城市哪个距离最近，将最近的城市加入到已到城市群中，result加上相应的距离
3. 循环步骤（2），直到所有的城市都已经到达

举个例子

代码

import java.util.Scanner;

public class Main {
    /* 顶点个数 */
    static int n;
    /* 邻接矩阵 */
    static int[][] G;
    /* 是否已经访问过该顶点 */
    static boolean[] visited;
    static int result;

    public static void main(String[] args) {
        // 出入顶点个数和邻接矩阵
        initiate();
        prim(1);
        System.out.println(result);
    }

    /* 普利姆算法 */
    private static void prim(int start) {
        visited[start] = true;
        // 已经访问过的顶点个数
        int visNum = 1;
        // 直到全部的顶点都被访问为止
        while (visNum < n){
            // 最短的边
            int min = Integer.MAX_VALUE;
            // 下一个要访问的顶点
            int next = 0;
            for (int i = 1; i <= n; i++) {
                if(visited[i]){
                    for (int j = 1; j <= n; j++) {
                        // 选取的边必须满足：终端顶点没有被访问过，且边的权值是最小的
                        if(!visited[j] && G[i][j] > 0 && min > G[i][j]){
                            min = G[i][j];
                            next = j;
                        }
                    }
                }
            }
            result += min;
            visited[next] = true;
            ++visNum;
        }
    }

    /* 初始化参数 */
    private static void initiate() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        G = new int[n + 1][n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                G[i][j] = scanner.nextInt();
            }
        }
    }
}

运行结果

提交结果