最小生成树在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种求解算法多种

发布网友 发布时间：2022-05-29 07:47

我来回答

共1个回答

热心网友 时间：2023-10-11 14:59

//////////////////////////////////////////////////////////////////////////
// function: 最小生成树问题
// 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。(带权的树图)
// Auther:卢燕
// Date:2015-1-5
//////////////////////////////////////////////////////////////////////////
const float maxValue=FLOAT_MAX;
template<class T,class E>
struct MSTEdgeNode
{
int tail,head;E key;
MSTEdgeNode():tail(-1),head(-1),key(0){}
bool operator<=(MSTEdge Node<T,E>&R) {return key <= R.key;}
bool operator>(MSTEdge Node<T,E>&R) {return key > R.key;}
};
template<class T,class E>
class MinSpanTree
{
protected:
MSTEdgeNode<T,E> *edgevalue;
int maxSize,n;
public:
MinSpanTree(int sz=DefaultSize-1);MaxSize(sz),n(0)
{
edgevalue=new MSTEdgeNode<T,E>[sz];
}
int Insert(MSTEdgeNode & item);
};
//////////////////////////////////////////////////////
//Kruskal算法的实现
#include"heap.h"
#include"UFSets.h"
template<class T,class E>
void Kruskal(Graph<T,E> & G,MinSpanTree<T,E>& MST)
{
MSTEdgeNode<T,E>ed;
int u,v,count;
int n=G.NumberOfVertices();
int m=G.NumberOfEdges();
MinHeap<MSTEdgeNode<T,E>>H(m);
UFSets F(n);
for(u=0;u<n;u++)
for(v=u+1'v<n;v++)
if(G.getWeight(u,v)!=maxValue)
{
ed.tail=u;ed.head=v;
ed.key=G.getWeight(u,v);
H.Insert(ed);
}
count=1;
while(count<n)
{
H.RemoveMin(ed);
u=F.Find(ed.tail);
v=F.Find(ed.head);
if(u!=v)
{
F.Union(u,v);
MST.Insert(ed);
count++;
}
}
};
/////////////////////////////////////////////////////
///Prim的算法实现
#include"heap.h"
template<class T,class E>
void Prim(Graph<T,E> & G,const T u0,MinSpanTree<T,E>& MST)
{
MSTEdgeNode<T,E>ed;
int i,u,v,count;
int n=G.NumberOfVertices();
int m=G.NumberOfEdges();
int u=G.getVertexPos(u0);
MinHeap<MSTEdgeNode<T,E>>H(m);
bool Vmst=new bool[n];
for(i=0;i<n;i++) Vmst[i]=false;
Vmst[u]=true;
count=1;
do
{
v=G.getFirstNeighbor(u);
while(v!=-1)
{
if(Vmst[v]==false)
{
ed.tail=u;ed.head=v;
ed.key=G.getWeight(u,v);
H.Insert(ed);
}
v=G.getNextNeighbor(u,v);
}
while(H.IsEmpty()==false && count<n)
{
H.RemoveMin(ed);
if(Vmst[ed.head]==false)
{
MST.Insert(ed);
u=ed.head;Vmst[u]=true;
count++;break;
}
}
}while(count<n);
};