整理自《数据结构高分笔记》
1、普里姆算法
算法思想
普利姆算法的基本思想如下：从图中任意取出一个顶点，把它当成一棵树，然后从与这棵树相连接的变种选取一条最短（权值最小）的边，然后把这条边及其所连接的顶点也加入这棵树中，此时得到了一棵有两个顶点的树。然后从与这棵树相接的边中选取一条最短的边，并将这条边及其所连接的顶点加入这棵树中，得到一棵有三个顶点的树。以此类推，知道图中所有顶点都被并入树中为止。
用普利姆算法构造最小生成树的过程中，需要建立两个数组vset[] 和 lowcost[] 。vset[i]=1 表示顶点i已被并入生成树中，如果vset[i]=0则表示顶点i还未被并入生成树中，lowcost[]数组中存放当前生成树到剩余各顶点最短边的权值。
算法的执行过程如下：
从树中某一个顶点v0开始，构造生成树的算法执行过程如下：
1）将v0到其他顶点的所有边当作候选边。
2）重复以下步骤n-1次，使得其他n-1个顶点被并入生成树中：从候选边中挑选出权值最小的边输出，并将与该边另一端相接的顶点v并入生成树中。考查剩余顶点vi，如果(v,vi)的权值比lowcost[vi]小，则用(v,vi)的权值更新lowcost[vi]。
例子解析
比如下面的图中，我们首先从v1开始，与v1相连的顶点有v2，v3，v4，对应的边的权值分别为6，1，5，所以选择v1-v3，将v3并入生成树中，在所有与v1或者v3相连的边中，权值最小的是v3-v6，权值为4，所以将v6并入生成树中，重复上面的过程，直到所有的顶点都被并入最小生成树中。
时间复杂度
普利姆算法的时间复杂度只与图中的顶点数有关系，而与边数没有关系，所以适用于稠密图。
2、克鲁思卡尔算法
基本思想
克鲁斯卡尔算法的思想比较简单，首先将图中按边权值从小到大排序，然后从最小边开始扫描各边，并检测当前边是否为候选边，即是否该边的并入会构成回路，如果不构成回路，则将该边并入生成树中，直到所有边都被检测完为止。
例子解析
我们仍然用上面用到的图来解释克鲁斯卡尔算法的基本思想：
1）所有边中权值最小的边为v1-v3，所以将该边加入生成树中。
2）剩余最小的边为v4-v6，不构成回路，将该边加入生成树中。
3）剩余最小的边为v2-v5，不构成回路，将该边加入生成树中。
4）剩余最小的边为v3-v6，不构成回路，将该边加入生成树中。
5）剩余最小的边为v2-v3、v3-v4和v1-v4，v3-v4和v1-v4的加入都会构成回路，v2-v3加入不构成回路，将该边加入生成树中。
此时所有的点都已联通，最小生成树生成结束。
时间复杂度
克鲁斯卡尔算法的时间复杂度与边数e相关，而与顶点数基本无关，所以适用于稀疏图。
