对计算机考研感兴趣的同学赶紧看过来，这里是小编整理的有关2024计算机考研数据结构考点“最小代价生成树”的内容，快来看看吧！希望能对大家有所参考。
2024计算机考研数据结构高频考点“最小代价生成树”
　　无向连通图的生成树是一个极小连通子图，它包括图中全部顶点，并且有尽可能少的边。
　　无向连通网络的最小代价生成树是所有生成树中边的权值之和最小的。
　　(1)普里姆算法：
　　首先，从n个顶点中任选一个顶点v加入到原来为空的生成树中;然后，重复执行下列操作：从一个顶点在生成树中，而另一个顶点不在生成树中的那些边中，选取一条权值最小的边，并将这条边以及它所关联的目前还不在生成树中的那个顶点加入到生成树中。当生成树中的顶点数达到n时，整个构造过程结束。
　　(2)克鲁斯卡尔算法
　　克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。
　　克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自己成为一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。
　　本文内容整理于网络，仅供参考。
　　关于2024计算机考研数据结构高频考点“最小代价生成树”的内容，小编就给大家简单介绍到这里了。如果还有其他考研考试相关内容想要了解的，就请登录高顿考研频道看看吧。
　　小编为2024考研的小伙伴们准备了丰富的学习资料，点击下方蓝色图片即可领取哦~
考研备考资料
相关阅读
延伸阅读


展开全文