👨🎓作者简介：一位喜欢写作，计科专业大二菜鸟
🏡个人主页：starry陆离
🕒首发日期：2022年5月31日星期二
🌌上期文章：动态规划:多重背包问题
📚订阅专栏：算法分析与设计
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
笔者前言
这是大一暑假的c笔记，再一次写prim算法笔记又有一点点进步
最小生成树（Prim普利姆算法和Kruskal算法）
1.问题引入
若要将n个城市之间原有的公路改造为 高速公路，这些城市之间原有公路网 如图所示，每条边上的数字表示高 速公路的改造成本（单位：10亿元）。 如何以最低的成本来构建高速公路网， 使得任意两个城市之间都有高速公路 相连？
2.最小生成树
Minimal Spanning Trees (MST)
- 任何只由图G的边构成，并包含G的所有顶点的树称为G的生成树
- 加权无向图G的生成树的权重是该生成树的所有边的权重之和
- 最小生成树是其所有生成树中权重最小的生成树
- N个顶点，选取N-1条边，构建一个连通图，且这N-1条边的权重之和最小
3.设计思路
-
任意选定一点s，设集合S={s} （Prim算法的特点从点出发）
-
从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则
(i，j)就是生成树上的一条边，同时将j点加入S -
转到(2)继续进行，直至所有点都己加入S集合，所以一棵有n个顶点的图构成的最小生成树有n-1条边
因此我们设计这个算法时需要保存的信息有：
- 数组
e[][]来记录图的各边权重 - 数组
visited[j]来保存当前节点j是否被访问（是否在集合s中） - 数组
dis[j]记录不在集合S的点中的节点j与S内的某点i的距离最短距离 - 数组
close[j]记录顶点j的最近邻接点
4.图解算法
首先我们要储存这张图，用一个二维数组e[][]即可，并且初始化时这个图上各点的距离应该为无穷大，表示各点没有连通
//初始化各边均不相邻
for(int i=0;i<n;++i) {
for(int j=0;j<n;++j) {
e[i][j]=Integer.MAX_VALUE;
}
}
//录入各边的信息
int x,y;
for(int i=0;i<m;++i) {
x=scanner.nextInt();
y=scanner.nextInt();
e[x][y]=scanner.nextInt();
e[y][x]=e[x][y];//可别忘了这一行哦，无向图的存储
}
其次我们任选一点，一般都是从最小的顶点开始，如0点；将其加入集合S中，这时要做的操作就多着，首先要获取其他顶点到第1个点(0)的距离，不直接相邻的顶点距离为无穷大；其次初始化所有点的最近邻接点都为第1个点(0)；最后还要将第1个点加到S中，更新visited[0]=1;
//初始化，S中只有第1个点(0)
for(int i=0;i<n;++i) {
dis[i]=e[0][i];//获取其他顶点到第1个点(0)的距离，不直接相邻的顶点距离为无穷大
close[i]=0;//初始情况下所有点的最近邻接点都为第1个点(0)
visited[i]=0;//初始情况下所有点都没有被访问过
}
visited[0]=1; //访问第1个点(0)，将第1个点加到S中
接下来要做的事就头大了。我们要遍历剩下的所有点，直到所有的点都加入到集合S中，慢慢来我们一个一个加。所要做的操作就是：
- 从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则
(i，j)就是生成树上的一条边，同时将j点加入S
这时集合S中只有一个点（0），那么遍历找到不再集合S中的其他点到点（0）的最小的距离，我们发现是点（0）和点（3）最近，距离为5；用一个遍历index记录这个点，并更新visited[3]=1表示将点（3）加入到集合S中
int index=0;
//如果顶点k没有被使用，且到S的距
//离小于k到S的距离，将k赋给index
for(int k=0;k<n;++k) {
if(visited[k]==0&&dis[k]<dis[index]) {
index=k;//记录到S距离最小的顶点
}
}
//将顶点index加入集合S并更新dis[]数组
visited[index]=1;
这可没完，我们把新的顶点（3）加入到了集合S中，那么不在集合S中的点到集合S中的点的距离就应该更新。举个例子：
- 在点（3）没加入集合S前，S={0}，点（5）到集合S的最小距离为无穷大，
dis[5]=MAX - 在点（3）加入集合S后，S={0,3}，点（5）到集合S的最小距离就是点（3）到点（5）的距离，
dis[5]=6
除此之外我们还应当记录下close[5]=3，表示点（3）作为点（5）到S中的最近邻点
//每一次循环用于在index加入S后，重新计算不在S中的顶点到S的距离，修改与index相邻的边
//到S的距离，即更新dis和close
for(int k=0;k<n;++k) {
//松弛操作，如果k没有被使用，且k到index的距离比原来k到S的距离小
if(visited[k]==0&&dis[k]>e[index][k]) {
dis[k]=e[index][k];//将k到index的距离作为新的k到S之间的距离
close[k]=index;//将index作为k在S中的最近邻点
}
}
然后就套用一个循环，从点（1）找到点（n）；不多说了直接看图
找到第四个点：
找到第五个点：
找到第六个点：
找到第七个点：找全啦，正好7-1=6条边
5.完整代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n,m;//点和边
int e[][];//储存权值
int dis[];//记录最小权值
int visited[];//记录当前点是否加入集合S
int close[];//记录邻接点
while(scanner.hasNext()) {
n=scanner.nextInt();//点
m=scanner.nextInt();//边
e=new int[n][n];
dis=new int[n];
visited=new int[n];
close=new int[n];
//初始化各边均不相邻
for(int i=0;i<n;++i) {
for(int j=0;j<n;++j) {
e[i][j]=Integer.MAX_VALUE;
}
}
//录入各边的信息
int x,y;
for(int i=0;i<m;++i) {
x=scanner.nextInt();
y=scanner.nextInt();
e[x][y]=scanner.nextInt();
e[y][x]=e[x][y];//可别忘了这一行哦，无向图的存储
}
//初始化，S中只有第1个点(0)
for(int i=0;i<n;++i) {
dis[i]=e[0][i];//获取其他顶点到第1个点(0)的距离，不直接相邻的顶点距离为无穷大
close[i]=0;//初始情况下所有点的最近邻接点都为第1个点(0)
visited[i]=0;//初始情况下所有点都没有被访问过
}
visited[0]=1; //访问第1个点(0)，将第1个点加到S中
for(int i=1;i<n;++i) {
int index=0;
//如果顶点k没有被使用，且到S的距
//离小于k到S的距离，将k赋给index
for(int k=0;k<n;++k) {
if(visited[k]==0&&dis[k]<dis[index]) {
index=k;//记录到S距离最小的顶点
}
}
//输出构成最小生成树的每条边
System.out.println(close[index]+" "+index+" "+dis[index]);
//将顶点index加入集合S并更新dis[]数组
visited[index]=1;
//每一次循环用于在index加入S后，重新计算不在S中的顶点到S的距离，修改与index相邻的边
//到S的距离，即更新dis和close
for(int k=0;k<n;++k) {
//松弛操作，如果k没有被使用，且k到index的距离比原来k到S的距离小
if(visited[k]==0&&dis[k]>e[index][k]) {
dis[k]=e[index][k];//将k到index的距离作为新的k到S之间的距离
close[k]=index;//将index作为k在S中的最近邻点
}
}
}
}
scanner.close();
}
}
测试案例：文章来源：https://www.toymoban.com/news/detail-789536.html
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
样例输出：文章来源地址https://www.toymoban.com/news/detail-789536.html
0 3 5
3 5 6
0 1 7
1 4 7
4 2 5
4 6 9
到了这里，关于贪心算法：最小生成树Prim算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
