最小生成树----Kruscal算法（从边入手找顶点）

找的方法：
贪心，先找最小的权值的边。
用并查集，看两个顶点是否有加入。

贪心的方法
先找最小的权值的边，再加上

#include"Graph.h"
#include"UFsets.h"
#include"Queue.h"
#include 

const double maxValue = 99999999.0;  	//机器可表示的、问题中不可能出现的大数
const int DefaultSize2 = 50;

//最小生成树边结点的类声明
template 
struct MSTEdgeNode {//T为顶点类型，其实在生成树中未用
	int tail, head;					//两顶点位置
	E key;							//边上的权值,为结点关键码
	MSTEdgeNode() {					//构造函数	
		tail = -1;
		head = -1;
		key = 0;
	}
	
	friend bool operator < (MSTEdgeNode& n1, MSTEdgeNode& n2);//类模板的友元函数必须是函数模板
	friend bool operator > (MSTEdgeNode& n1, MSTEdgeNode& n2);//所以必须在这里声明，在类外定义
	friend bool operator == (MSTEdgeNode& n1, MSTEdgeNode& n2);
	friend bool operator <= (MSTEdgeNode& n1, MSTEdgeNode& n2);
};
template  bool operator < (MSTEdgeNode& n1, MSTEdgeNode& n2) {//只有在类外才能定义为函数模板
	return n1.key < n2.key;
}
template  bool operator > (MSTEdgeNode& n1, MSTEdgeNode& n2) {
	return n1.key > n2.key;
}
template  bool operator == (MSTEdgeNode& n1, MSTEdgeNode& n2) {
	return n1.key == n2.key;
}
template  bool operator <= (MSTEdgeNode& n1, MSTEdgeNode& n2) {
	return n1.key <= n2.key;
}


//最小生成树的类定义
template 
class MinSpanTree {
protected:
	MSTEdgeNode* edgevalue;			//用边值数组表示树
	int maxSize, n;							//数组的最大元素个数和当前个数
public:
	MinSpanTree(int sz = DefaultSize2 ) {
		maxSize = sz;
		n = 0;
		edgevalue = new MSTEdgeNode[sz];
		//assert(edgevalue);
	}
	bool Kruscal(Graphmtx& G); // Kruscal算法
	bool Insert(MSTEdgeNode& item);	//将边item插入到树中，若树中节点已满，则返回false;
	void output();							//自定义函数，顺序输出所有边
	void printMST(Graphmtx& G);
};


template
bool MinSpanTree::Insert(MSTEdgeNode& item) {
	if (n == maxSize) {
		return false;
	}
	edgevalue[n] = item;
	n++;
	return true;
}


template
void MinSpanTree::output() {
	for (int i = 1; i <= n; i++) {
		cout << "Edge " << i << " : " << "head = " << edgevalue[i - 1].head << " ; tail = " << edgevalue[i - 1].tail << " ; key = " << edgevalue[i - 1].key << endl;
	}
}

template
bool MinSpanTree::Kruscal(Graphmtx& G)
{
	MSTEdgeNode ed; // 边结点辅助单元
	int u=0, v=0, count=0;
	int n = G.numberOfVertices(); // 图的顶点数
	E weight; // 权值
	MinHeap> H(n);       //最小堆存边集及权重信息
	UnionFindSets F(n);  //并查集
	//把图的已知数据输入到最小堆中，插入之后就容易找到最小的数据
	for (u = 0; u < n; u++)
	{
		for (v = u + 1; v < n; v++)  //找该顶点的下一个与之有边的顶点
		{
			weight = G.getWeight(v,u);  //获得权重
			if (weight > 0 && weight < G.maxWeightG)
			{
				ed.head = u;
				ed.tail = v;
				ed.key = weight;
				H.Insert(ed);
			}
		}
	}
	count = 1;
	while (count < n && !H.IsEmpty())
	{
		H.RemoveMin(ed);   //找出最小的边
		u = F.Find(ed.tail);
		v = F.Find(ed.head);
		if (u != v)
		{
			F.Union(u, v);  //集合合并，连通
			Insert(ed);  //插入到最小生成树中
		  //cout<
void MinSpanTree::printMST(Graphmtx& G) {
	int tail, head; // 顶点所在位置
	T e1, e2; // 两顶点
	E weight; //  权值

	for (int i = 0; i < currentSize; i++) {
		tail = edgevalue[i].tail; // 顶点所在位置
		head = edgevalue[i].head;
		e1 = G.getValue(tail); // 根据位置，取顶点对应的值
		e2 = G.getValue(head);
		weight = G.getWeight(tail, head); // 取权值
		cout << "(" << e1 << "," << e2 << "," << weight << ")" << endl;
	}
}

执行结果 ：

template
bool MinSpanTree::Kruscal(Graphmtx& G)
{
	MSTEdgeNode ed; // 边结点辅助单元
	int u=0, v=0, count=0;
	int n = G.NumberofVertices(); // 图的顶点数
	E weight; // 权值
	MinHeap> H(n);       //最小堆存边集及权重信息
	UFSets F(n);  //并查集
	//把图的已知数据输入到最小堆中，插入之后就容易找到最小的数据
	for (u = 0; u < n; u++)
	{
		for (v = u + 1; v < n; v++)  //找该顶点的下一个与之有边的顶点
		{
			weight = G.getWeight(v,u);  //获得权重
			if (weight > 0 && weight < G.maxWeightG)
			{
				ed.head = u;
				ed.tail = v;
				ed.key = weight;
				H.Insert(ed);
			}
		}
	}
	count = 1;
	while (count < n && !H.IsEmpty())
	{
		H.RemoveMin(ed);   //找出最小的边
		u = F.Find(ed.tail);//在找的第一遍，是父节点就是自己，就返回自己数组下标。
		v = F.Find(ed.head);
		if (u != v) //当两个根不同时，进行合并。
		{
			F.SimpleUnion(u, v);  //集合合并，连通,连n-1次
			Insert(ed);  //插入到最小生成树中
		    cout<<" 点"<