知识点
最小生成树:一般都是针对无向图来说的,分为两种算法
- 普利姆算法算法(Prim)
- 朴素版Prim:O(n^2^)稠密图,用邻接矩阵来存
- 堆优化版Prim:O(mlogn)稀疏图,用邻接表来存
- 克鲁斯卡尔算法(Kruskal):O(mlogm):稀疏图
算法思想
1:for n ,迭代n次
2:for1 ~ n,在还未确定最短路的点中,寻找距离最小的点
3:判断是否为最小生成树,更新res
3:for1 ~ n,用t更新其他点到集合的距离
4:把t加入到集合中去
需要注意的问题
1:可以看出来,prim算法和Dijkstra算法是很像的,可以类比着去记忆
需要注意的是,Dijkstra算法更新的是所有点距离起点的最短距离,而prim更新的是所有点距离集合的最短距离
Dijkstra算法中的st[]表示的是该点是否已经确定最短距离了,而prim的st[]表示的是是否已经在最小生成树上了
2:i != 0 有什么含义
i != 0 代表的是不是第一次迭代,因为第一次迭代并不是所有点的距离都会进行初始化,初始化的是第一个点的所有出度,所以一定要加上这个条件
因此,if (i != 0 && dist[t] == INF) return INF;
这句话的含义就是不是第一次迭代,距离集合最近的点还没有初始化,说明就不是一个连通图,就可以返回结果了
3:第一次迭代
第一次迭代因为有条件i != 0的限制,并不会更新res的值,而是在以后的迭代中不断更新,况且d[1] = 0,更新了也没有用
代码
import java.util.Scanner;
import java.util.Arrays;
public class Main{
static int N = 510;
static int[][] g = new int[N][N];
static int[] d = new int[N];
static boolean[] st = new boolean[N];
static int n , m ,INF = 0x3f3f3f3f;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
for(int i = 0; i < N; i ++) Arrays.fill(g[i],INF);
for(int i = 0; i < m; i ++)
{
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
g[a][b] = g[b][a] = Math.min(g[a][b],c);
}
int t = prim();
if(t == INF) System.out.print("impossible");
else System.out.print(t);
}
private static int prim()
{
Arrays.fill(d,INF);
int res = 0;
for(int i = 0; i < n; i ++) //迭代的是点的个数
{
int t = -1;
for(int j = 1; j <= n; j ++) //循环的也是点的个数
{
if(!st[j] && (t == -1 || d[t] > d[j])) t = j;
}
if(i != 0 && d[t] == INF) return INF;
if(i != 0) res += d[t];
for(int j = 1; j <= n; j ++) d[j] = Math.min(d[j], g[t][j]);
st[t] = true;
}
return res;
}
}