找到一条能够把所有点连接起来的最短路径
prim算法
用一个数组minDist来记录每一个节点距离最小生成树的最近距离，
用一个boolean数组visited记录节点是否加入最小生成树
算法流程：
选择离最小生成树最近的（minDist值最小），还没有加入最小生成树（visited为false）的节点
标记节点加入最小生成树（visited为true）
-
更新minDist中还没有加入最小生成树的节点的值
用什么更新？ --因为刚刚加入新的节点，用新节点到这些节点的距离更新
(
minDist[不是生成树的节点] = Math.min(graph[刚加入的节点][不是生成树的节点], minDist[不是生成树的节点]))
import java.util.*;
public class Main{
public static int V;
public static int E;
public static int[][] graph;
public static boolean[] visited;
//minDist数组 用来记录 每一个节点距离最小生成树的最近距离
public static int[] minDist;
public static void main (String[] args) {
/* code */
Scanner in = new Scanner(System.in);
V = in.nextInt();
E = in.nextInt();
graph = new int[V+1][V+1];
visited = new boolean[V+1];
minDist = new int[V+1];
Arrays.fill(minDist, 10001);
//因为val>=0,所以要做一个二维数组的初始化
for(int i=1; i<=V; i++){
Arrays.fill(graph[i], -1);
}
for(int i=0; i<E; i++){
int start = in.nextInt();
int end = in.nextInt();
int val = in.nextInt();
graph[start][end] = val;
//注意是无向图
graph[end][start] = val;
}
prim();
int result = 0;
for(int i=2; i<=V; i++){
result+=minDist[i];
}
System.out.println(result);
}
public static void prim(){
// i循环的是次数，一共要做V次（把v个节点加入生成树）
for(int i=0; i<V; i++){
int min_val = Integer.MAX_VALUE;
int cur = -1;
//选择距离最小生成树最近的点加入最小生成树
for(int j=1; j<=V; j++){
if(!visited[j]&&minDist[j]<min_val){
min_val = minDist[j];
cur = j;
}
}
//加入
visited[cur]=true;
//更新没加入最小生成树的节点到达最小生成树的距离
for(int j=1; j<=V; j++){
if(!visited[j]&&graph[cur][j]>=0)
minDist[j] = Math.min(graph[cur][j], minDist[j]);
}
}
}
}
Kruskal
用到并查集的知识
用LinkedList记录所有的边，并按照权值排序
-
遍历有序（升序）的边：
- 如果边的两个点不在同一个集合，则加入最小生成树（用result记录树的长度，所以result要+边长，且要把两个点并为同一个集合）
- 如果在同一个集合，直接跳过这个边，看下一条边
import java.util.*;
public class Main{
public static int V;
public static int E;
public static LinkedList<int[]> edges;
public static int[] father;
public static int result;
public static void main (String[] args) {
/* code */
Scanner in = new Scanner(System.in);
V = in.nextInt();
E = in.nextInt();
edges = new LinkedList<>();
father = new int[V+1];
result = 0;
for(int i=1; i<=V; i++){
father[i] = i;
}
for(int i=0; i<E; i++){
int start = in.nextInt();
int end = in.nextInt();
int val = in.nextInt();
edges.add(new int[]{start, end, val});
}
//List自定义排序规则！！！
edges.sort(Comparator.comparingInt(o -> o[2]));
kruskal();
System.out.println(result);
}
public static int find(int u){
if(u==father[u]) return u;
else return father[u] = find(father[u]);
}
public static boolean isSame(int u, int v){
u = find(u);
v = find(v);
return u==v;
}
public static void join(int u, int v) {
u = find(u);
v = find(v);
father[v] = u;
}
public static void kruskal(){
//V个节点，加V-1条边就行了，所以需要重复V-1次
for(int i=1; i<V; i++){
int[] edge = edges.removeFirst();
while(isSame(edge[0], edge[1])){
edge = edges.removeFirst();
}
result += edge[2];
join(edge[0], edge[1]);
}
}
}
