prim算法
和dijkstra算法有点类似，不过dijkstra算法在找寻最小路径是是找到已能到达点中最小的点，然后将然后以该点为中转站对路径进行更新，而prim算法是将已找到的点看作一个集合，然后再找到离这个集合最短的点，将这个点纳入这个集合，重复上述操作
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int N=10000;
int mp[N][N];
int f[N];//存储父节点
int d[N];//到生成树的最短距离
int vis[N];//标记是否已被找到
int n,m;
void prim()
{
? ? for(int i=1; i<=n; i++)
? ? {
? ? ? ? if(mp[1][i]!=inf)
? ? ? ? ? ? f[i]=1;
? ? ? ? d[i]=mp[1][i];
? ? }
? ? while(true)
? ? {
? ? ? ? int Min=inf;
? ? ? ? int t=-1;
? ? ? ? for(int i=1; i<=n; i++)
? ? ? ? {
? ? ? ? ? ? if(vis[i]==0&&d[i]<Min)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Min=d[i];
? ? ? ? ? ? ? ? t=i;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(t==-1)
? ? ? ? ? ? break;
? ? ? ? vis[t]=1;
? ? ? ? for(int i=1; i<=n; i++)
? ? ? ? {
? ? ? ? ? ? if(vis[i]==0&&d[i]>mp[t][i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? d[i]=mp[t][i];
? ? ? ? ? ? ? ? f[i]=t;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? int sum=0;
? ? for (int i=1; i<=n; i++)
? ? ? ? if(f[i]==-1)
? ? ? ? {
? ? ? ? ? ? printf("不存在最小生成树\n");
? ? ? ? ? ? return ;
? ? ? ? }
? ? ? ? else
? ? ? ? ? ? sum+=d[i];
? ? printf("最短生成树的长度为%d\n",sum);
}
int main()
{
? ? cin>>n>>m;
? ? for(int i=1; i<=n; i++)
? ? {
? ? ? ? for(int j=1; j<=n; j++)
? ? ? ? {
? ? ? ? ? ? if(i==j)
? ? ? ? ? ? ? ? mp[i][j]=0;
? ? ? ? ? ? else
? ? ? ? ? ? ? ? mp[i][j]=inf;
? ? ? ? }
? ? }
? ? memset(vis,0,sizeof(vis));
? ? memset(f,-1,sizeof(f));
? ? int a,b,c;
? ? for(int i=1; i<=m; i++)
? ? {
? ? ? ? cin>>a>>b>>c;
? ? ? ? mp[a][b]=c;
? ? ? ? mp[b][a]=c;
? ? }
? ? prim();
}
?
|