最小生成树的概念和应用背景
最小生成树（Minimum Spanning Tree）各边权的总和最小的生成树
MST性质
假设N=(VE)是一个连通网U是顶点集V的一个非空子集若(UV)是一条具有最小权值的边其中u∈Uv∈VU则必存在一棵包含边(UV)的最小生成树
构造最小生成树的常用算法
普里姆（Prim）算法
基本思想设G=(VE)是连通网顶点集V={vv…vn}T=(UTE)是欲构造的最小生成树任选V中一顶点（不妨为v）初始化U={v}TE=Φ重复下列操作在所有u∈U中v∈VU的边（uv)∈E中选择一条权值最小的边(uv)并入TE同时将v并入U直到U=V为止这时产生的TE中具有n条边则上述过程求得的T=(UTE)是G的一棵最小生成树
普里姆算法的时间复杂度为O(n)与图中边数无关该算法适合于稠密图
克鲁斯卡尔（Kruskal）算法
基本思想设T是无向连通网G的最小生成树E(T)是其边集则令最小生成树的初始状态为n个顶点而无边的非连通图即E(T)为空集图中每个顶点自成一个连通分量在E中选择权值最小的边若该边依附的顶点落在T中不同的连通分量上则将此边加入到T中否则捨去此边而选择下一条权值最小的边依次类推直至T中所有顶点都在同一连通分量上为止（此时已选中n条边）
克鲁斯卡尔算法的时间复杂度为O(elge)时间主要取决于边数较适合于稀疏图
