MENU

最小生成树之普利姆算法

• December 23, 2020 • Read: 34 • 贪心,

原题链接

题目描述

最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在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();
            }
        }
    }
}

运行结果

提交结果




作者:喻航

本文标题:最小生成树之普利姆算法

本文链接:https://onedawn.cn/greed/158.html

版权声明:如无特别声明,本文即为原创文章,仅代表个人观点,版权归 雾满拦江 所有,未经允许不得转载!
Archives Tip
QR Code for this page
Tipping QR Code