【数据结构】图的最小生成树

最小生成树

一个图中有N个顶点，边的数量一定是>=N-1，我们从中选取N-1条边，用来连接N个点，所形成的边权之和最小，就是最小生成树。

构成最小生成树的准则

1. 只能使用图中的边来构造最小生成树
2. 只能使用恰好n-1条边来连接图中的n个顶点
3. 选用的n-1条边不能构成回路

构成最小生成树的的方法：Kruskal(克鲁斯卡尔)算法和Prim(普里姆)算法

二者都是基于逐步贪心的算法

Kruskal算法

Kruskal算法的思路

1. 先构建出一个N个顶点的最小生成树图，其中不包含任何边，将原图的各个边按照权值进行排序
2. 在排序的边中，选出一条边，如果这条边不会与其它边构成环，就添加到最小生成树图里
3. 当选边数为N-1时，就构成最小生成树，否则不构成

描述这一过程，构成最小生成树

再选边时 都会构成环，此时已经是n-1条边，连接n个顶点，是最小生成树。

• 要做选取最小的边，就需要将边的关系放到优先级队列中。每一个取边，就是top pop的过程。
• 判断是否成环，需要一个集合，如果顶点A和B都在集合中，那么就构成环。
• 只要优先级队列还有边就要一直判断选边，直到队列为空，如果最后选取了n-1条边，那么就是最小生成树，反之不是，并返回所有的权和。

  		struct Edge
  		{
  			size_t _srci;
  			size_t _dsti;
  			W _w;
  			Edge(size_t srci, size_t dsti, const W& w)
  				:_srci(srci)
  				, _dsti(dsti)
  				, _w(w)
  			{}
  			bool operator>(const Edge& e) const
  			{
  				return _w > e._w;
  			}
  			bool operator