最小生成树

生成树：连通图包含全部顶点的一个极小连通子图

最小生成树：对于带权无向连通图G=(V,E)，G的所有生成树当中边的权值之和最小的生成树为G的最小生成树（MST）

性质：
1）最小生成树不一定唯一，即最小生成树的树形不一定唯一，当带权无向连通图G的各边权值不等时或G只有结点数-1条边时，MST唯一
2）最小生成树的权值是唯一的，且是最小
3）最小生成树的边数为顶点数-1

Prim算法：

时间复杂度：O(|V|^2)，适用于稠密图

Kruskal算法：

时间复杂度：O(|E|log|E|)，适用于稀疏图