算法分析与设计1.1Prim算法构造最小生成树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法分析与设计1.1Prim算法构造最小生成树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含840字，纯文字阅读大概需要2分钟。

内容图文

1. 问题

设G=(V,E)是无向联通带权图，E中的每一条边（u,v）的权为w(u,v);如果G的一个子图G1是一颗包含G中所有顶点的树，则称G1为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称之为最小生成树。

2. 解析

3. 设计

void Prime(int Vnum, int start){
	for(i = 1; i <= Vnum; i++){
		lowcost[i] = Vi到Vstart的权值；
		visited[i] = -1;//标记点的访问状态，-1为未访问，1为访问过
	}
	visited[start] = 1;
	for(剩下的点){
		minWg = 999;
		for(j = 0; j <= Vnum; j++){
			if(第j个点到已经标记点的集合的距离最小且这个点还没有被标记){
				minWg = lowcost[j];
				下一个要标记的点 = j;
			}
		}
		visited[下一个要标记的点] = 1;
		for(j = 0; j <= Vnum; j++)
		{
			更新lowcost[],使其存放各个点到已标记点的集合的最短距离；
		}
	}
}

4. 源码

https://github.com/tangsongbbb/AlgorithmsLearning/blob/master/作业一/1.1.c

• 点赞
• 收藏
• 分享
• • 文章举报

Godricccc 发布了8 篇原创文章 · 获赞 1 · 访问量 133 私信 关注

内容总结

以上是互联网集市为您收集整理的算法分析与设计1.1Prim算法构造最小生成树全部内容，希望文章能够帮你解决算法分析与设计1.1Prim算法构造最小生成树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---