prim算法
2026-01-17 11:58:45
发布于：四川
11阅读
0回复
0点赞
prim算法----从点着手 括点法 稠密图
核心思想：贪心
贪心策略：从任意顶点出发，每次将"到生成树的最短距离的点，且未被访问过"加入生成树，知道所有点全部纳入
关键工具：
邻接矩阵存图：邻接矩阵存图（权值图），所有权值要存入无穷大inf(0x3f3f3f3f),表示没有直接边
距离数组：重要的遍历准备数组，存储是每一个没纳入生成树的顶点到最小生成树的最小距离
标记数组：标记该点是否被访问
解题步骤：
1.邻接矩阵存图：
1.1邻接矩阵存图，存的权值，初始化为无穷大（03f3f3f3f）
1.2选择一个起点，假如选1，d[1]=0;※
2.循环n个点（每次都要纳入一个点）
2.1找到未被纳入生成树且d[j]最小的顶点x
2.2没有找未被纳入生成树且d[j]最小的点呢？？？
若x==0，则说明被找到点，表示该图未连通，返回false
2.3标记vis[x]=1，表示已经被纳入
2.4扫描x点的所有边，更新未被纳入顶点y的距离，d[y]=min(d[y],a[x][y]);
取当前距离和x-y边权值的最小值
3.计算结果：如果要计算权值，d[i]累加起来，就是最小生成树的权值和
prim算法时间复杂度：n^2,适用于顶点数较少且是稠密图，顶点数n<=5000
基础模板代码：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5005;
int a[N][N];
int vis[N],d[N];
int n,m;
//prim算法函数
bool prim(){
memset(d,inf,sizeof(d));//初始化距离数组为无穷大
memset(vis,0,sizeof(vis));//初始化标记数组为0
d[1]=0;//确定起点
for(int i=1;i<=n;++i){
int x=0;
for(int j=1;j<=n;++j){//找到未被纳入生成树且d[j]最小的顶点x
if(!vis[j]&&d[j]<d[x]){
x=j;
}
}
if(x==0)return false;//如果不能找到d[j]最小的顶点x 则无法连通 返回false
vis[x]=1;
for(int y=1;y<=n;++y){
if(!vis[y])d[y]=min(d[y],a[x][y]);
}
}
return true;
}
int main(){
cin>>n>>m;
memset(a,inf,sizeof(a));
for(int i=1;i<=m;++i){//邻接矩阵存图
int x,y,z;
cin>>x>>y>>z;
a[x][y]=a[y][x]=min(a[x][y],z);
}
int ans=0;
if(prim()==true){
for(int i=1;i<=n;++i)ans+=d[i];//计算的d[i]累加和，就是权值之和
cout<<ans;
}else{
cout<<"orz";
}
return 0;
}
有帮助，赞一个