找人做网站要拿到源代码吗/友情链接也称为

求解最小生成树的算法主要有两种，prim算法和kruskal算法，下面分别介绍这两种算法：

1. prim算法：

算法思想：

一共有n个点，每次循环选择一个点加入（这个点肯定是最小代价的点的连线），为了可以更好的在每次循环的时候都能得到最小的代价，所以我引入一个最小代价数组，每次循环，都对这个数组进行维护，这样就可以求出最小生成树了。

下面给出代码及其具体注释：

#include <iostream>
#include <vector>
#include <string.h>
const int INF=0x3f3f3f3f;//这是设置一个最大值的好方法
using namespace std;
bool vis[11000];//vis数组，用来判断这个点是否访问过
int lowc[11000];//最小代价数组
int cost[10000][10000];//全部代价矩阵
int Prim(int n)
{memset(vis,false,sizeof(vis));//初始化int ans=0,p,i,Min,j;vis[0]=true;//将第一个点直接加入for(i=1;i<n;i++)lowc[i]=cost[0][i];//先将最小代价数组设置为以0为起点的值，因为第一步我们肯定是要找到与0相连的代价最小的点for(i=1;i<n;i++)//主循环{Min=INF;p=-1;//标记点，用来标记我们加入了那个点for(j=0;j<n;j++){if(!vis[j]&&Min>lowc[j])//在最小代价数组中找到最小的值{Min=lowc[j];p=j;//记录加入的点}}if(Min==INF){return -1;//表示找不到}ans+=Min;vis[p]=true;//将加入的点标记for(j=0;j<n;j++){if(!vis[j]&&lowc[j]>cost[p][j])//维护最小代价数组，因为当新加入一个点后,比如加入了1点，那么这时，如果1到2的代价比0到2的代价小，那么我们必须更新lowc数组{lowc[j]=cost[p][j];//如果以0为起点的代价不是最小，则立刻改变}}}return ans;
}
int main()
{int n,i,j;cin>>n;for(i=0;i<n;i++){for(j=0;j<n;j++){cin>>cost[i][j];}}cout<<Prim(n)<<endl;return 0;
}

最后给出一个题目的链接，可以去提交看看结果：

点击打开链接