最小生成树.doc

6---最小生成树实现
姓名：赵成兵
学号：20062353
班级：软件工程2班
1、问题描述
数据结构中学过树这个概念，其实在实际应用中树的这种表现形式多是有权的。如一个连通网来表示两个城市之间的路线，赋予边的权值表示alues=100;//最大权值
const int MaxVertexNum=50;//最大顶点个数
typedef int VertexType;
typedef VertexType VertexList[MaxVertexNum];//存储顶点信息
typedef int AdjMatrix[MaxVertexNum][MaxVertexNum];//
AdjMatrix GA;
//定义边的存储结构
struct edge
{
int startvex;
int endvex;
int weight;
};
void GreatePrim(AdjMatrix &GA,int n,int e)//构造无向图
{
VertexList Gv;
int i,j,k,weight;
cout<<"输入"<<n<<"个顶点"<<endl;
for(i=0;i<n;i++ )
cin>>Gv[i];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i==j)GA[i][j]=0;
else GA[i][j]=MaxValues;
}

cout<<"输入"<<n<<"条边及其权值:"<<endl;
for(k =0;k<e;k++)
{ cout<<"输入第"<<k+1<<"条边及其权值:";
cin>>i>>j>>weight;
GA[i][j]=GA[j][i]=weight;
}
cout<<endl;
cout<<"邻接矩阵为:"<<endl;
for(int i0=0;i0<n;i0++)
{ for(int i1=0;i1<n;i1++)
cout<<GA[i0][i1]<<" ";
cout<<endl;
}
}
edge *Prim(AdjMatrix GA,int n)//用普里姆算法求最小生成树
{
int i,j,k,min,t,m,w;
edge *ct =new edge[n-1];
for(i=0;i<n-1;i++)
{
ct[i].startvex =0;
ct[i].endvex =i+1;
ct[i].weight =GA[0][i+1];
}
for(k=1;k<n;k++)
{
min =MaxValues;
m=k-1;
for(j=k-1;j<n-1;j++)
if(ct[j].weight<min)
{
min =ct[j].weight;
m =j;
}

edge temp;
temp =ct[k-1];
ct[k-1] =ct[m];
ct[m] =temp;
j =ct[k-