最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。
prim算法
图中有n个节点，那么一定可以用n-1条边将所有节点连接到一起。
==只适用于加权无向图==
那么如何选择这n-1条边就是最小生成树算法的任务所在。
在这个图中，如何选取n-1条边使得图中所有节点连接到一起，并且边的权值和最小呢？
（图中为n为7，即7个节点，那么只需要n-1即6条边就可以讲所有顶点连接到一起）
prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。
prim算法核心就是三步，我称为prim三部曲，大家一定要熟悉这三步，代码相对会好些很多：
- 第一步，选距离生成树最近节点
- 第二步，最近节点加入生成树
- 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
minDist数组的含义：记录每一个节点距离最小生成树的最近距离。
寻宝
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述 第一行包含两个整数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.
解题思路
最小生成树的模板题，这里使用prim算法解决
代码实现
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int e = scanner.nextInt();
int x,y,val;
//记录图的邻接矩阵
int[][] grid = new int[v+1][v+1];
while(e -- > 0) {
x = scanner.nextInt();
y = scanner.nextInt();
val = scanner.nextInt();
grid[x][y] = val;
grid[y][x] = val;
}
//minDist数组
int[] mindist = new int[v+1];
Arrays.fill(mindist, 10001);//初始化
//记录节点是否在最小生成树里
boolean[] isTree = new boolean[v+1];
mindist[1] = 0;
for(int i = 1; i < v ; i++) {
int cur = -1;
int minVal = Integer.MAX_VALUE;
//第一步
for(int j = 1; j <= v ; j++) {
if(!isTree[j] && mindist[j] < minVal) {
minVal = mindist[j];
cur = j;
}
}
//第二步
isTree[cur] = true;
//第三步
for(int j = 1 ; j <= v; j++) {
if(!isTree[j] && grid[cur][j] < mindist[j]) {
mindist[j] = grid[cur][j];
}
}
}
int result = 0;
for(int i = 2 ; i <= v; i++) {
result += mindist[i];
}
System.out.println(result);
}
kruskal算法
kruskal的思路：
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
寻宝
和上题同题
代码实现
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int e = scanner.nextInt();
int result = 0;
DisjointSet ds = new DisjointSet(v);
//使用并查集实现查看节点是否在同一集合
ds.init();
//存储节点和边权值的结构
List<Edge> edgeList = new ArrayList<Edge>();
for(int i = 0 ; i < e ; i++) {
int l = scanner.nextInt();
int r = scanner.nextInt();
int val = scanner.nextInt();
edgeList.add(new Edge(l, r, val));
}
// 执行对边权值的排序
edgeList.sort(Comparator.comparingInt(edge -> edge.val));
for(Edge edge : edgeList) {
//如果节点不在同一集合
if(!ds.isSame(edge.l, edge.r)) {
//结果加入当前权值
result += edge.val;
//节点加入集合
ds.join(edge.l, edge.r);
}
}
System.out.println(result);
}
}
class DisjointSet{
int n;
int[] father;
public DisjointSet(int n) {
this.n = n;
this.father = new int[n+1];
}
public void init() {
for(int i = 1 ;i < father.length; i++) {
father[i] = i;
}
}
public void join(int u, int v) {
u = find(u);
v = find(v);
if(u == v)return;
father[v] = u;
}
public int find(int u) {
return (u == father[u])? u: (father[u] = find(father[u]));
}
public boolean isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
//找到需要删除的那条边
public void getRemovedEdge(ArrayList<int[]> edge) {
init();//注意每次都要初始化并查集
for(int i = 0 ; i < edge.size() ; i++) {//遍历所有边
if(isSame(edge.get(i)[0], edge.get(i)[1])) {//并查集里有，说明这条边就是要删除的边
System.out.println(edge.get(i)[0]+" "+edge.get(i)[1]);
return;
}else {
join(edge.get(i)[0], edge.get(i)[1]);
}
}
}
public boolean isTreeAfterRemoveEdge(ArrayList<int[]> edge, int deleteEdge) {
init();//注意每次都要初始化并查集
for(int i = 0 ; i < n; i++) {
if(i == deleteEdge)continue;
if(isSame(edge.get(i)[0], edge.get(i)[1])) { //说明此时构成了环，不删deleteEdge而是删后一条
return false;
}
join(edge.get(i)[0], edge.get(i)[1]);
}
return true;
}
}
class Edge{
int l,r,val;
public Edge(int l, int r, int val) {
this.l = l;
this.r = r;
this.val = val;
}
}
拓展1
题目要求将最小生成树的边输出的话，应该怎么办呢？
Kruskal 算法 输出边的话，相对prim 要容易很多，因为 Kruskal 本来就是直接操作边，边的结构自然清晰，不用像 prim一样 需要再将节点连成线输出边 （因为prim是对节点操作，而 Kruskal是对边操作，这是本质区别）
当判断两个节点不在同一个集合的时候，这两个节点的边就加入到最小生成树
拓展2
什么情况用哪个算法更合适呢。
Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。 如果 一个图中，节点多，但边相对较少，那么使用Kruskal 更优。
在节点数量固定的情况下，图中的边越少，Kruskal 需要遍历的边也就越少。
而prim 算法是对节点进行操作的，节点数量越少，prim算法效率就越优。
所以在 稀疏图中，用Kruskal更优。 在稠密图中，用prim算法更优。
==边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图==
Prim 算法 时间复杂度为O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。
Kruskal算法 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图。
说些什么吧！