admin 
最小代价生成树
无向连通图的生成树是一个极小连通子图，它包括图中全部顶点，并且有尽可能少的边。
无向连通网络的最小代价生成树是所有生成树中边的权值之和最小的。
(1)普里姆算法：
首先，从n个顶点中任选一个顶点v加入到原来为空的生成树中;然后，重复执行下列操作：从一个顶点在生成树中，而另一个顶点不在生成树中的那些边中，选取一条权值最小的边，并将这条边以及它所关联的目前还不在生成树中的那个顶点加入到生成树中。当生成树中的顶点数达到n时，整个构造过程结束。
(2)克鲁斯卡尔算法
第五单元 第六单元 第七单元
以上是小编为大家整理分享的“2022考研计算机数据结构：最小代价生成树”相关内容，希望对大家有帮助。祝大家考上理想的院校!
评论列表 人参与