决策树学习的生成算法有几种(数据结构图的最小生成树的算法和应用举例)

一、最小生成树介绍

图结构是一种非常重要的非线性数据结构,带权图的最小生成树在工程技术,科学管理的最优解问题中有着广泛的应用。

最小生成树:权值和最小的生成树

最小生成树的性质:假设G=(V,E)是个连通图,U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。

产生最小生成树必须解决下边两个问题:

(1) 尽可能选取权值小的边,但不能构成回路

(2) 选取n-1条恰当的边以连通n个顶点。

最小生成树的算法主要有Kruskal算法和Prim算法,他们都是贪心算法的应用。

二、最小生成树的算法

(1) Kruskal算法

过程描述:始终以边为主导地位,先选择权值最小的边,总是选择当前可用最小权值边,并且每次判断两点之间是否已经间接连通,如果已经间接连通,则跳过此边。

时间复杂度是O(n*logn),适用于求边稀疏连通网的最小生成树。

(2) Prim算法

决策树学习的生成算法有几种(数据结构图的最小生成树的算法和应用举例)(1)

图 2

谢谢大家可以添加关注或点赞,您的鼓励和支持是我们继续努力的最大动力!

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页