---图的遍历和最小生成树

广度优先遍历   ---   针对的是顶点遍历

  深度优先遍历

如果给的图不是连通图？以某个点为起点就没有遍历完成。那么怎么保证遍历完剩下的点呢？？

在标记数组当中找没有遍历过的点，在进行遍历

最小生成树

生成树：一个连通图的最小连通子图称作该图的生成树，有n个顶点的连通图的生成树有n个顶点和n-1条边（最少的边连通起来）

最小生成树：构成生成树的这些边加起来权值是最小的！！

 Kruskal算法和Prim算法，这两个算法都采用了逐步求解的贪心策略

Kruskal算法

prim算法

我们可以发现prim的优势：不会构成环，永远是在X集合和Y集合当中条一条边，顶点永远不可能在一个集合当中，天然避环