最小生成樹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個)
- 然后判斷剩余節點中與當前生成樹距離最近的頂點，將其加入生成樹；
- 更新第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)
)
