最小生成树(Minimum Spanning Tree MST)用于解决最小代价问题，例如用N-1条边链接N个城市，求最小”花费”

定理1:N个点用N-1条边连成一个连通块，形成的图形只可能是树

1.Prim算法

最小生成树其实就是连接所有点的最短边权值和（好装逼啊） Prime算法采用类似dijkstra 和 ford算法一样的蓝白点思想，白点代表已经进入算法最小点的点，蓝点代表未进入最小生成树的点。 描述： 以1为起点生成最小数,min[v]表示蓝点v与白点相连的最小边权。 MST表示最小生成树的权值之和。

1. 初始化min[v]=$\infty$(v!=1);min[1] = 0;MST = 0;
2. for(int i = 1;i<=n;i++)//有n个点，所以要找n次，因为第一个点还未找，所以第一个点也要算上，就是n-1+1=n个点 in total 1寻找min[u]最小的蓝点u。 2将u标记为白点 3MST+=min[u] 4for与白点相连的所有蓝点V

    if(w[u][v]<min[v])
         min[v] = w[u][v]

算法结束 解析： 其实min[u]储存的是当前白点与其连接的蓝点的距离，mst才是最短权值和

Kruskal(克努斯卡尔)算法

Kruskal算法把一个连通块当做一个集合。Kruskal首先将说有的边按从小到大的顺序排序，并认为每一个点都是孤立的，分别属于m个集合。然后按顺序枚举每一条边，如果这两条边连接着不同的集合，那么就把这两条边加入最小生成树，这两个不同的集合就合并成了一个集合，如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。

算法描述：//超好理解的有没有 初始化并查集：father[x] = x; tot = 0; 将所有的边从小到大排序。 计数器k=0

for(int i = 1;i<=m;i++)循环所有从小到大的边
{
    if(这一条u，v不属于同一集合的边(u,v)//已经排序，所以必定为最小
    {
        1合并uv所在的集合，相当于把边(u,v)加入最小生成树
        2tot = tot+W(U,V0)
        3k++
        4如果k==n-1，说明最小生成树已经生成，则break；
    }
}