2022考研计算机知识点:最小代价生成树

2021年10月18日 来源: 运营部-闫老师

近几年的考研中,计算机考研慢慢的已是大热门,仅次于金融、医学和心理学。虽说计算机考研受到众多考生的喜爱,但是其中的相关知识却是很让人头疼。下面,小编为大家讲讲2022考研计算机知识点:最小代价生成树。

最小代价生成树

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

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

(1)普里姆算法:

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

(2)克鲁斯卡尔算法

以上就是总结“2022考研计算机知识点:最小代价生成树”全部内容,希望对大家有所帮助,更多的内容可关注湖南文都考研官网。

相关推荐

34所自主划线院校考研难度排行大揭秘!
历届考研人踩过的坑,你中招了吗?
22考研需不需要报考研辅导班?湖南文都考研怎么样?
2021考研调剂:哪些调剂的内容是考生需要知道的?
2021考研复试:英语常见的话题之你的家庭
2022考研数学线性代数必备考点:线性相关与无关的两套定理
2022考研翻译学硕士知识:开皇之治
2022法律硕士考研知识点:不具有行为能力实施的民事行为

热报课程

热点资讯

官方微博

Top
本页链接:https://hn.wendu.com/pc/detail/detail-information.php?nav=information&news_info_id=5662