算法01-最小生成树prim算法

最小生成树prim算法
题源：代码随想录卡哥的题
链接：https://kamacoder.com/problempage.php?pid=1053
时间：2025-04-18
难度：4⭐
题目：

1. 题目描述：

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将所有岛屿联通起来。

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

输入描述：

第一行包含两个整数V和E，V代表顶点数，E代表边数。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。

接下来共有E行，每行三个整数v1，v2和val，v1和v2为边的起点和终点，val代表边的权值。

输出描述：

输出联通所有岛屿的最小路径总距离

输入示例：

7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1

输出示例：

6

2. 解题方法：

采用prim算法来求最小生成树的问题，使用贪心的思想，即在循环每一个顶点的过程中，寻找与当前生成树距离最近的顶点，然后将其加入进来，然后更新当前生成树到剩余顶点的最近距离。总共分为3个步骤：

1. 寻找初始起点(这里随机即可，选择第1个)
2. 然后判断剩余节点中与当前生成树距离最近的顶点，将其加入生成树；
3. 更新第2步新增节点到最小生成树后，当前其他节点到最小生成树的距离。

3. 代码如下：

import java.util.*;

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

    int v=scanner.nextInt();
    int e=scanner.nextInt();
    
    int[][] grid=new int[v+1][v+1];
    for(int i=0;i<=v;i++){
        Arrays.fill(grid[i],10001);
    }

    for(int i=0;i<e;i++){
        int a=scanner.nextInt();
        int b=scanner.nextInt();
        int c=scanner.nextInt();

        grid[a][b]=c;
        grid[b][a]=c;
        
    }

    int[] minDist=new int[v+1];
    Arrays.fill(minDist,10001);

    boolean[] inTree=new boolean[v+1];

    for(int i=1;i<v;i++){
        int cur=-1;
        int minVal=Integer.MAX_VALUE;

        for(int j=1;j<=v;j++){
            if(!inTree[j]&&minDist[j]<minVal){
                minVal=minDist[j];
                cur=j;
            }
        }

        inTree[cur]=true;

        for(int j=1;j<=v;j++){
            if(!inTree[j]&&grid[cur][j]<minDist[j]){
                minDist[j]=grid[cur][j];
            }
        }
    }

    int res=0;
    for(int i=2;i<=v;i++){
        res+=minDist[i];
    }

    System.out.println(res);

}

}

4. 心得体会

算法真的好难呀，555~
有没有路过的大佬分享一下怎么学算法呀~

5. 碎碎念

东b管院本科生->东b计科水硕-> 一名热爱技术但菜菜的女生，持续前进中~
如果有技术上的问题分享，或者生活中的碎碎念，愿意多一个互联网搭子的话: dd19898852196(weiChat)