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

一、最小生成树介绍

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

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

最小生成树的性质：假设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算法

图 2

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