一、最小生成树介绍
图结构是一种非常重要的非线性数据结构，带权图的最小生成树在工程技术，科学管理的最优解问题中有着广泛的应用。
最小生成树：权值和最小的生成树
最小生成树的性质：假设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
谢谢大家可以添加关注或点赞，您的鼓励和支持是我们继续努力的最大动力！
,
