Day63_20250211_图论part7 prim算法|kruskal算法精讲
prim算法 【维护节点的集合】
题目
题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数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.
思路
- 思路
问题：最小生成树是所有节点的最小连通子图(以最小的成本(边的权值))将图中所有节点链接到一起。
- 图中有n个节点，一定可以用n-1条边将所有节点连接到一起。
prim算法 【从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中】
- 1.选距离生成树最近节点
- 2.最近节点加入生成树
- 3.更新非生成树节点到生成树的距离(更新minDist数组)
细节
- minDist数组用来记录每个节点距离最小生成树的最近距离(最小生成树所有边的权值)
- 0.初始状态
- minDist数组初始化为最大数(10001)
- 原因:默认每个节点距离最小生成树是最大的，之后在比较的时候，发现更近的距离，才能更新到minDist数组上。
- 1.选距离生成树最近节点
- 刚开始还没有最小生成树，随便选择一个，按照习惯选择节点1
- 2.最近节点加入生成树
- 节点1加入
- 3.更新非生成树节点到生成树的距离(更新minDist数组)
- 更新所有非生成树的节点距离最小生成树(节点1)的距离
- 4.遍历
- (1) 选距离最小生成树(节点1)最近的非生成树里的节点，节点2，3都可以(默认为2)，5不可以，权值大
- (2)加入节点2
- (3)更新非生成树节点到生成树的距离(更新minDist数组)
怎么画最小生成树，打印出来最小生成树的每条边？
- 用什么结构来记录？如何记录？
- 使用一维数组(有向边)，parent[节点编号] = 节点编号，如果编号很大，考虑map。
- 在更新minDist数组(最小生成树)的时候，去更新parent数组来记录一下对应的边。
- 代码
import java.util.*; public class Main{ public static void main(String[] args){ //输入 Scanner scanner=new Scanner(System.in); int v=scanner.nextInt();//顶点vertex int e=scanner.nextInt();//边edge int[][] grid=new int[v+1][v+1];//网格 //grid数组[] 存放所有节点(为了区分生成树节点(有距离)和非生成树节点) for(int i=0;i<=v;i++){ Arrays.fill(grid[i],10001); } //邻接矩阵，读取边的信息 for(int i=0;i<e;i++){ int x=scanner.nextInt(); int y=scanner.nextInt(); int k=scanner.nextInt(); //有向边 grid[x][y]=k; grid[y][x]=k; } //所有节点到最小生成树的最小距离 int[] minDist=new int[v+1]; Arrays.fill(minDist,10001); //记录节点是否在最小生成树里？ boolean[] isInTree=new boolean[v+1]; //Prim算法主循环 ?为什么从1开始，而不是0，少了一个节点，还是数组多了一个节点 //1.选距离生成树最近节点 //在生成树1下 for(int i=1;i<v;i++){ int cur=-1;//为什么默认为-1 int minVal=Integer.MAX_VALUE;//？为什么这里有写最大值了，minDist不是已经写好了吗 //选择距离生成树最近的节点 for(int j=1;j<=v;j++){ if(!isInTree[j]&&minDist[j]<minVal){ //非生成树中&&候选的中间节点 minVal=minDist[j];//更新可用节点的最小值 cur=j;//当前距离 } } //2.将最近的节点加入生成树 isInTree[cur]=true; //3.更新非生成树节点到生成树的距离 for(int j=1;j<=v;j++){ //非生成树节点&&更新从当前节点cur到节点j的边权重(其他权重不更新) if(!isInTree[j]&&grid[cur][j]<minDist[j]){ minDist[j]=grid[cur][j]; } } } //统计结果 int result=0; //从1出发 for(int i=2;i<=v;i++){ result+=minDist[i]; } System.out.println(result); scanner.close(); } }
总结
为什么要用2个数组(grid数组和minDist数组)?
- grid数组: 存放所有节点的权值(区分生成树节点(有最小距离)和非生成树节点)，中间数组，存放下一个被选中的生成树节点if(!isInTree[j]&&grid[cur][j]<minDist[j]){
- minDist数组：
- 1.存放最小生成树的最近距离(最小生成树所有边的权值), 最后保存距离 2.更新从当前节点cur到节点j的边权重(其他权重不更新)
- //非生成树节点&&更新从当前节点cur到节点j的边权重(其他权重不更新)
if(!isInTree[j]&&grid[cur][j]<minDist[j]){
minDist[j]=grid[cur][j];
}
kruskal算法 【维护边的集合】
题目
【同上】
思路
思路
维护边的集合
过程
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 将图中的边按照权值从小到大排序，优先选权值小的边加入到最小生成树中。
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边后图中会出现环。例如，root0-2,root0-1在同一个集合。
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合。例如，root0-1,root2-3，那么1和3连起来
伪代码
- 排序好数组后
- 边首尾的节点在同一个集合，不做计算
- 边首尾的节点不在同一个集合，加上到最小生成树，加入到最小生成树，并把两个节点加入到同一集合中。
代码细节
- 如何将2个节点加入到同一个集合，又如何判断2个节点是否在同一个集合里？
- 并查集
- 拓展1，怎么将最小生成树的边输出？
- struct Edge{ int l,r,val;}
- 拓展2，用哪个算法更合适呢？
Kruskal和prim的关键区别在于：prim维护的是节点的集合，而Kruskal维护的是边的集合。
如果一个图中节点多(稀疏图)，但边相对较少，用KrusKal。
- 边少，遍历操作的次数就少。
如果一个图中边多，但节点少，用prim
节点越少(稠密图)，prim算法更优。
两者复杂度
- prim，时间复杂度O(n^2)，n是节点数量，运行效率和图中边树无关，适用稠密图
- KrusKal，时间复杂度O(nlogn)，其中n为边的数量，适用稀疏图
- 如何将2个节点加入到同一个集合，又如何判断2个节点是否在同一个集合里？
代码
import java.util.*; public class Main{ public static void main(String[] args){ //输入 Scanner scanner=new Scanner(System.in); int v=scanner.nextInt();//vertex顶点 int e=scanner.nextInt();//edge边 List<Edge> edges=new ArrayList<>();//初始化 int result_val=0; //读取所有边的信息 for(int i=0;i<e;i++){ int v1=scanner.nextInt(); int v2=scanner.nextInt(); int val=scanner.nextInt(); edges.add(new Edge(v1,v2,val)); } //KruaKal算法 //1.排序 edges.sort(Comparator.comparingInt(edge->edge.val)); //2.创建并查集 判断2个节点是否在1个集合中，将2个节点加到1个集合中 DisJoint disjointSet=new DisJoint(v+1); //3.从边中选择最小的并加入生成树 for(Edge edge:edges){ int x=disjointSet.find(edge.l); int y=disjointSet.find(edge.r); //如果2个边不在同一个集合中，合并 if(x!=y){ result_val+=edge.val;// disjointSet.join(x,y);//加入到集合中 } //如果2个边在一个集合中，不做计算 } //输出最小生成树的权重 System.out.println(result_val); scanner.close(); } //Edge边 static class Edge{ int l,r,val; Edge(int l,int r, int val){ this.l=l; this.r=r; this.val=val; } } //DisJoint static class DisJoint{ private int[] father; public DisJoint(int n){ father=new int[n];//自己是自己的根节点 for(int i=0;i<father.length;i++){ father[i]=i; } } //寻找根节点 public int find(int n){ return n==father[n]?n:(father[n]=find(father[n])); } //将2个节点加入到集合中 public void join(int u,int v){ u=find(u); v=find(v); if(u==v) return; father[v]=u; } } }
总结
- 这里的三元运算符是== return n==father[n]?n:(father[n]=find(father[n]));