补上今天刚写完，并通过运行的最下生成树的类的实现，觉得数据结构很多的算法都是比划着简单，实现难啊...
共享一下我刚通过运行的程序，大家参考：
#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;
};
////////////////////////////////////<<友元重载结束
得慢慢看...
