首页 / 算法 / 最小生成树之Prim算法
最小生成树之Prim算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了最小生成树之Prim算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1603字，纯文字阅读大概需要3分钟。
内容图文
描述
最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod，在这个Mod中，玩家可以拥有不止一个城市了！
但是，问题也接踵而来——小Hi现在手上拥有N座城市，且已知这N座城市中任意两座城市之间建造道路所需要的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。
输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为1个整数N，表示小Hi拥有的城市数量。
接下来的N行，为一个N*N的矩阵A，描述任意两座城市之间建造道路所需要的费用，其中第i行第j个数为Aij，表示第i座城市和第j座城市之间建造道路所需要的费用。
对于100%的数据，满足N<=10^3，对于任意i，满足Aii=0，对于任意i, j满足Aij=Aji, 0<Aij<10^4.
输出
对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
Sample Input
5 0 1005 6963 392 1182 1005 0 1599 4213 1451 6963 1599 0 9780 2789 392 4213 9780 0 5236 1182 1451 2789 5236 0
Sample Output
4178
题意描述：
输入城市的个数及N*N的矩阵
计算并输出使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用
解题思路：
典型的求最小生成树，根据数据的格式，使用Prim算法即可。Prim算法主要的思路就是每次选择距离生成树最近的结点添加，再更新新结点到尚未加入到树的各个结点的距离，便于下次查找距离生成树最近的结点。
代码实现：
1 #include<stdio.h>
2 #include<string.h>
3int e[1100][1100],book[1100],dis[1100];
4constint inf=99999999;
5int main()
6{
7int n,i,j,k,c,sum,min;
8while(scanf("%d",&n) != EOF)
9 {
10for(i=1;i<=n;i++)
11for(j=1;j<=n;j++)
12 scanf("%d",&e[i][j]);
13for(i=1;i<=n;i++)
14 dis[i]=e[1][i];
1516 memset(book,0,sizeof(book));
17 book[1]=1;
18 c=1;
19 sum=0;
20while(c < n)
21 {
22 min=inf;
23for(j=0,i=1;i<=n;i++)
24 {
25if(!book[i] && dis[i] < min)//注意是且的关系 26 {
27 min=dis[i];
28 j=i;
29 }
30 }
31 book[j]=1;
32 c++;
33 sum += dis[j];
34for(k=1;k<=n;k++)
35 {
36if(!book[k] && dis[k] > e[j][k])
37 dis[k]=e[j][k];
38 }
39 }
40 printf("%d\n",sum);
41 }
42return0;
43 }
易错分析：
1、注意在寻找距离生成树最近的结点时，判断条件是且
原文：http://www.cnblogs.com/wenzhixin/p/7277759.html
内容总结
以上是互联网集市为您收集整理的最小生成树之Prim算法全部内容，希望文章能够帮你解决最小生成树之Prim算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。