day57

寻宝：求最小生成树（所有结点的最小连通子图）
//prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。

//prim算法求最小生成树（所有结点的最小连通子图）
//prim三部曲：
//1、选距离生成树最近结点
//2、最近节点加入最小生成树
//3、更新非生成树结点到生成树的最小距离（minDist数组）

//kruscal的思路：
//1、边的权值排序，因为要优先选最小的边加入到生成树里
//2、遍历排序后的边
//如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
//如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
//并查集来判断两个节点在不在同一个集合，不在则加入集合
个人认为Kruscal算法更简单！时间复杂度也更低！O(nlogn) < O(n^2)