培训啦 学历 考研

2022考研计算机数据结构:最小代价生成树

发布时间: 2023-01-17 14:16:02
2022考研计算机数据结构:最小代价生成树

最小代价生成树

无向连通图的生成树是一个极小连通子图,它包括图中全部顶点,并且有尽可能少的边。

无向连通网络的最小代价生成树是所有生成树中边的权值之和最小的。

(1)普里姆算法:

首先,从n个顶点中任选一个顶点v加入到原来为空的生成树中;然后,重复执行下列操作:从一个顶点在生成树中,而另一个顶点不在生成树中的那些边中,选取一条权值最小的边,并将这条边以及它所关联的目前还不在生成树中的那个顶点加入到生成树中。当生成树中的顶点数达到n时,整个构造过程结束。

(2)克鲁斯卡尔算法

第五单元 第六单元 第七单元

以上是小编为大家整理分享的“2022考研计算机数据结构:最小代价生成树”相关内容,希望对大家有帮助。祝大家考上理想的院校!

.xqy_container .xqy_core .xqy_core_main .xqy_core_text{height:auto !important;} 2022考研计算机数据结构:最小代价生成树
温馨提示:
本文【2022考研计算机数据结构:最小代价生成树】由作者教培参考提供。该文观点仅代表作者本人,培训啦系信息发布平台,仅提供信息存储空间服务,若存在侵权问题,请及时联系管理员或作者进行删除。
我们采用的作品包括内容和图片部分来源于网络用户投稿,我们不确定投稿用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的权利,请联系我站将及时删除。
内容侵权、违法和不良信息举报
Copyright @ 2024 培训啦 All Rights Reserved 版权所有. 湘ICP备2022011548号