最小生成树

最小生成树一般是无向图，有两个常用算法
    普利姆算法(Prim)
        朴素版（稀疏图）       O(n^2)
        堆优化版（稠密图）     O(mlogn)
    克鲁斯卡尔算法(Kruskal)    O(mlogm)

一般稀疏图用prim
稠密图用kruskal

算法原理：
①朴素prim
     首先把所有距离初始化为正无穷
     n次迭代
     {
          找到集合外距离最近的点；
          把该点加入到集合中；
          用该点更新其他点到集合的距离；//（如果先加入再更新，有自环问题）
     }
acwing 858

②堆优化版几乎不用，复杂。
③kruskal算法

    1、将所有边按权重从小到大排序    O(mlogm)    //可用stl快排
    2、枚举每条边，如a-b，权重是c       O(m)
        如果ab不连通
            将这一条边加入集合

acwing 859