时间:2021-05-19
本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程。
1.什么是最小生成树算法?
简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小。这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法。
2.Prim算法的步骤是什么?
这就要涉及一些图论的知识了。
a.假定图的顶点集合为V,边集合为E.
b.初始化点集合U={u}.//u为V中的任意选定的一点
c.从u的邻接结点中选取一点v使这两点之间的权重最小,然后将v加入集合U中.
d.从结点v出发,重复c步骤,直到V={}.
3.举个例子来说明Prim算法的步骤:
一个简单的加权拓扑图如下所示
选取1为初始点,则按照上面所示的步骤访问结点的顺序依次次为:
则最终访问结点的顺序:1,3,4,2,5.
4.Prim算法的具体C语言编程实现:
5.程序运行后的结果截图
以上就是本文的全部内容,希望对大家的学习有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
很久以前就学过最小生成树之Kruskal和Prim算法,这两个算法很容易理解,但实现起来并不那么容易。最近学习了并查集算法,得知并查集可以用于实现上述两个算法后
最小生成树最小生成树(minimumspanningtree)是由n个顶点,n-1条边,将一个连通图连接起来,且使权值最小的结构。最小生成树可以用Prim(普里
之前都是看书,大部分也是c++的实现,但是搞前端不能忘了JS啊,所以JS实现一遍这两个经典的最小生成树算法。一、权重图和最小生成树权重图:图的边带权重最小生成树
最小生成树Prim算法朴素版有几点需要说明一下。1、2个for循环都是从2开始的,因为一般我们默认开始就把第一个节点加入生成树,因此之后不需要再次寻找它。2、l
Prim算法思想:从任意一顶点v0开始选择其最近顶点v1构成树T1,再连接与T1最近顶点v2构成树T2,如此重复直到所有顶点均在所构成树中为止。最小生成树(MS