最小生成树:
最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。
图中有n个节点，那么一定可以用 n - 1 条边将所有节点连接到一起。
那么如何选择 这 n-1 条边 就是 最小生成树算法的任务所在。
prim算法 是从节点的角度 采用贪心的策略 每次寻找距离 最小生成树最近的节点 并加入到最小生成树中。
prim算法核心的三部曲：
minDist数组 用来记录 每一个节点距离最小生成树的最近距离
最小生成树
最后我们就生成了一个 最小生成树， 绿色的边将所有节点链接到一起，并且 保证权值是最小的，因为我们在更新 minDist 数组的时候，都是选距离 最小生成树最近的点 加入到树中。
最后，minDist数组 也就是记录的是最小生成树所有边的权值。
kruskal算法:
Kruskal，同样可以求最小生成树。
prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
kruscal的思路：
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
图解 :
边的权值排序，因为要优先选最小的边加入到生成树里:
排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]
权值相同的边，先后顺序无所谓。
但在代码中，如果将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢？
这里就涉及到。
并查集主要就两个功能：
- 将两个元素添加到一个集合中
- 判断两个元素在不在同一个集合
53. 寻宝
时间：1.000S 空间：128MB
题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数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 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;
如下图，可见将所有的顶点都访问一遍，总距离最低是6.
使用prime算法解题:
这里并没有给min_dest[1]设置为0,而是设置为MAX_VALUE,并且在选最近不在生成树结点中的结点时,设置了1为初始结点,可以保证1号结点能被第一个选择,并且后续选择的结点都小于min_dest[1](MAX_VALUE) ,都是联通的
import java.util.*;
public class Main{
public static void main(String[] args){
int v,e;
Scanner in=new Scanner(System.in);
v=in.nextInt();
e=in.nextInt();
//初始化
int[] nodes=new int[v+1];
int[][]map =new int[v+1][v+1];
for(int i=0;i<map.length;i++){
Arrays.fill(map[i],-1);
}
List<Integer> tree=new LinkedList<>();
Arrays.fill(nodes,Integer.MAX_VALUE);
while(e-->0){
int x=in.nextInt();
int y=in.nextInt();
int val=in.nextInt();
map[x][y]=val;
map[y][x]=val;
}
for(int i=1;i<v;i++){
int index=getIndex0fMin(nodes,tree);
//加入生成树
tree.add(index);
//跟新到非生成树结点的距离
update(nodes,tree,map,index);
}
//计算路径总和
int sums=0;
for(int i=1;i<=v;i++){
if(nodes[i]!=Integer.MAX_VALUE)
sums+=nodes[i];
}
System.out.println(sums);
}
public static int getIndex0fMin(int[]nodes,List<Integer> tree){
int index=1;
for(int i=2;i<nodes.length;i++){
if(nodes[i]<nodes[index]&&!tree.contains(i)){
index=i;
}
}
return index;
}
public static void update(int[]nodes,List<Integer> tree,int[][]map,int index){
for(int i=1;i<nodes.length;i++){
if(map[index][i]>=0&&!tree.contains(i)){
nodes[i]=Math.min(nodes[i],map[index][i]);
}
}
}
}
使用Kruskal算法:
import java.util.*;
public class Main {
public static void main(String[] args) {
int v, e;
Scanner in = new Scanner(System.in);
v = in.nextInt();
e = in.nextInt();
M m = new M(v);
Edge[] edges = new Edge[e];
for (int i = 0; i < e; i++) {
int x = in.nextInt();
int y = in.nextInt();
int val = in.nextInt();
Edge edge = new Edge(x, y, val);
edges[i] = edge;
}
//排序
Arrays.sort(edges, new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.getVal() - o2.getVal();
}
});
int sums=0;
//遍历加入,并检测时候成环
for(Edge edge:edges){
if(!m.isSame(edge.getStart(),edge.getEnd())){
m.join(edge.getStart(),edge.getEnd());
sums+=edge.getVal();
}
}
System.out.println(sums);
}
}
class Edge {
int start;
int end;
int val;
public Edge(int start, int end, int val) {
this.start = start;
this.end = end;
this.val = val;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
public int getVal() {
return val;
}
@Override
public String toString() {
return "Edge{" +
"start=" + start +
", end=" + end +
", val=" + val +
'}';
}
}
class M {
int[] father;
public M(int n) {
father = new int[n + 1];
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
int find(int i) {
if (father[i] == i) {
return i;
}
father[i] = find(father[i]);
return father[i];
}
boolean isSame(int i, int j) {
i = find(i);
j = find(j);
if (i == j) return true;
return false;
}
void join(int i, int j) {
i = find(i);
j = find(j);
if (i == j) return;
father[j] = i;
}
}
