补上今天刚写完，并通过运行的最下生成树的类的实现，觉得数据结构很多的算法都是比划着简单，实现难啊...
共享一下我刚通过运行的程序，大家参考：
#ifndef MINSPANHEAP_H
#define MINSPANHEAP_H
#include<iostream.h>
#include<stdlib.h>
#include"Graphlink.h"
#include"Graphmtx.h"
#include"MinHeap.h"
#include"UFSet.h"
const float maxValue=10000;
const int defaultsize=30;
//////////////////////////////////////////////////
//MSTEdgeNode结构 最小生成树边结点的声明
//本最小生成树采用边的集合进行表示
//////////////////////////////////////////////////
template<class T,class E>
struct MSTEdgeNode
{
int head; //边的一个端点
int tail; //边的另一个端点
E weight; //当前边权值
MSTEdgeNode() //默认构造函数
{head=-1;tail=-1;weight=0;};
/*以下重载关系运算符*/
bool operator>(MSTEdgeNode<T,E>& Node)
{return weight>Node.weight;};
bool operator>=(MSTEdgeNode<T,E>& Node)
{return weight>=Node.weight;};
bool operator<(MSTEdgeNode<T,E>& Node)
{return weight<Node.weight;};
bool operator<=(MSTEdgeNode<T,E>& Node)
{return weight<=Node.weight;};
bool operator==(MSTEdgeNode<T,E>& Node)
{return weight==Node.weight;};
};
///////////////////////////////MSTEdgeNode结构结束
//////////////////////////////////////////////////
//MinSpanTree类模 最小生成树的实现
//T是顶点数据域的类型,E是边的权值的数据类型
//////////////////////////////////////////////////
template<class T,class E>
class MinSpanTree
{
protected:
MSTEdgeNode<T,E>* EdgeValue; //边集合数组
int maxSize; //边集合数组
int currentSize; //当前数组的长度
public:
MinSpanTree(int sz=defaultsize) //构造函数
{
maxSize=sz;currentSize=0; //初始化数据成员
EdgeValue=new MSTEdgeNode<T,E>[maxSize];
if(EdgeValue==NULL)
{
cout<<"内存分配失败!"<<endl;
exit(1);
};
};
~MinSpanTree() //析构函数
{delete [] EdgeValue;};
bool Insert(MSTEdgeNode<T,E>& Node);//把一条边插入到当前的生成树中
void Cruskal(Graph<T,E>& G); //Cruskal算法:通过图G来构造当前的最小生成树
void Prim(Graph<T,E>& G,int start); //Prim算法:通过图G来构造当前的最小生成树
//友元重载<<输出运算符输出当前的最小生成树
friend ostream& operator<<(ostream& os,MinSpanTree<T,E>& MST);
};
/////////////////////////////////MinSpanTree类模板
//////////////////////////////////////////////////
//Insert()公有成员函数
//在当前的最小生成树中插入一条边,插入成功返回true
//////////////////////////////////////////////////
template<class T,class E>
bool MinSpanTree<T,E>::Insert(MSTEdgeNode<T,E>& Node)
{
if(currentSize==maxSize)
{
cout<<endl
<<"当前的最小生成树的空间已经满了!"
<<endl;
return false;
};
//把边插入其中
EdgeValue[currentSize]=Node;
currentSize++;
return true;
};
//////////////////////////Insert()公有成员函数结束
//////////////////////////////////////////////////
//Cruskal()公有成员函数
//利用克鲁斯卡尔算法通过当前图来构造一棵最小生成树
//即所谓的贪心算法,每次都取剩下的最大或者最小,但
//该边两个的顶点不能在同一连通分量中,反复迭代
//参数采用的是图的基类Graph<T,E>,在具体运行的
//时候可以实现基类动态向子类的类型转换
//////////////////////////////////////////////////
template<class T,class E>
void MinSpanTree<T,E>::Cruskal(Graph<T,E>& G)
{
/*首先把所有的边按照权值放入最小堆中*/
int numEdges=G.NumberOfEdges(); //得到图G的边的条数
MinHeap<int,MSTEdgeNode<T,E> >MH(numEdges);//依照图的边数定义最小堆
MSTEdgeNode<T,E> Edge; //边结点变量
for(int u=0;u<numEdges;u++) //无重复地遍历所有的边
{
for(int v=u+1;v<numEdges;v++) //把边压入最小堆
{
int cost=G.getWeight(u,v); //获取边(u,v)的权值
if(cost>0 && cost<maxWeight) //如果该边存在且有效
{
Edge.head=u; //初始化边结点内容
Edge.tail=v;
Edge.weight=cost;
MH.Insert(Edge); //把该边加入到最小堆中
};
};
};
/*从对中取出不在同一连通分量中的最小边插入堆中的迭代过程*/
int numVertices=G.NumberOfVertices(); //获得图中的当前顶点的个数
UFSet UF(numVertices); //用于判断是否在同一个连同分量的并查集
int count=1;
while(count<=numVertices-1) //从堆中逐个取出权值最小的边
{
MH.RemoveMin(Edge); //从最小堆中取出一条最小边
u=UF.findRoot(Edge.head); //找u所在集合的根结点
int v=UF.findRoot(Edge.tail); //找v所在集合的根结点
if(u!=v) //如果Edge的两个端点不在一个连通分量
{
Insert(Edge); //把该边插入到最小生成树中去
count++;
UF.Union(u,v); //把u,v两个集合合并,连接两个分裂的连通分量
};
};
};
/////////////////////////////Cruskal()公有函数结束
//////////////////////////////////////////////////
//Prim()公有成员函数
//通过Prim算法实现把图G得到相应的最小生成树
//每次从某个结点出发,把与最小生成树中结点相关联的
//权值最小的边找出来,并加入最小生成树,反复迭代
//其中start是起始结点
//////////////////////////////////////////////////
template<class T,class E>
void MinSpanTree<T,E>::Prim(Graph<T,E>& G,int start)
{
int numVertices=G.NumberOfVertices(); //得到图当前所有顶点数
bool* vmst=new bool[numVertices]; //用于标记已经加入生成树的结点
for(int i=0;i<numVertices;i++) //初始化为未加入
vmst[i]=false;
vmst[start]=true; //先把start加入最小生成树
MinHeap<int,MSTEdgeNode<T,E> >
MH(G.NumberOfEdges()); //迭代过程中用于求权值最小的边的堆栈
MSTEdgeNode<T,E> Edge; //一个最小生成树的结点变量
int p=start; //新加入最小生成树的那个顶点
int count=1; //迭代计数器,一共要迭代n-1次
do
{
/*把新结点加入生成树的顶点集合中*/
vmst[p]=true;
/*把与新结点相关的并且另一个顶点不
在生成树中的边加入最小堆*/
int n=G.getFirstNeighbor(p); //先获取结点p的第一个邻接
while(n!=-1) //遍历所有的邻接结点
{
if(vmst[n]!=true) //如果邻接点n不在生成树中
{ //把该边加入最小堆
Edge.head=p; //生成树内的结点
Edge.tail=n; //生成树外的结点
Edge.weight=G.getWeight(p,n);
MH.Insert(Edge); //把该边加入最小堆
};
n=G.getNextNeighbor(p,n); //获取下个邻接结点
};
/*从堆中取出权值最小的边加入到生成树中去*/
do
{
MH.RemoveMin(Edge); //取出最小边
if(vmst[Edge.tail]!=true) //如果另一个结点不在生成树中
{
Insert(Edge); //把该边插入生成树
count++; //加入边的条数的计数器
break;
};
}
while(!MH.IsEmpty());
p=Edge.tail;
}
while(count<=numVertices-1);
};
////////////////////////////Prim()公有成员函数结束
//////////////////////////////////////////////////
//友元重载<<输出运算符输出当前的最小生成树
//////////////////////////////////////////////////
template<class T,class E>
ostream& operator<<(ostream& os,MinSpanTree<T,E>& MST)
{
cout<<"当前的最小生成树的边集合是:"<<endl;
for(int i=0;i<MST.currentSize;i++)
{
cout<<"("<<MST.EdgeValue[i].head //输出边的一端
<<","<<MST.EdgeValue[i].tail //输出边的另一端
<<","<<MST.EdgeValue[i].weight
<<")"<<endl; //输出该边的权值
};
return os;
};
////////////////////////////////////<<友元重载结束
得慢慢看...
