实验五最小生成树
一、需求分析
1、本程序の目の是要建设一个最经济の网，，输出相应の最小生成树。
在这里都用整型数来代替。
2、测试数据
见下程序。
二、概要设计
主程序：
int main()
{
初始化；
while (条件)
{
接受命令;
处理命令;
}
return 0;
}
三、详细设计
#include<iostream>//头文件
using namespace std;
#define MAX_VERTEX_NUM 20//最大结点数
#define MAX 200
typedef struct Close//结构体
{
char adjvex;
int lowcost;
}Close,close[MAX_VERTEX_NUM];
typedef struct ArcNode
{
int adjvex;
ArcNode *nextarc;
int info;
}ArcNode;
typedef struct VNode
{
char data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList verties;
int vexnum,arcnum;
}ALGraph;
ALGraph G;//对象G
int LocateVek(ALGraph ,char );//返回结点位置
int minimum(close);//返回最小数
void MinSpanTree_PRIM(ALGraph,char);//最小生成树
void Create(ALGraph &);//创建邻接表
int main()
{
char a;int i=1;
Create(G);
/*for(int i=1;i<=G.vexnum;i++)
{
for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc)
cout<<G.verties[i].data<<"---"<<G.verties[s->adjvex].data<<"===="<<s->info<<endl; }*/
while(i)
{
cout<<"输入起点 : ";
cin>>a;
MinSpanTree_PRIM(G,a);
cout<<"如果结束输入'0',否则输入'1':";
cin>>i;
}
return 0;
}
int LocateVek(ALGraph G,char u)
{
int i;
for(i=1;i<=G.vexnum;i++)
if(u==G.verties[i].data)
return i;
return -1;
}
int minimum(close m)//返回最小数
{
int i=0,j,n=200;
for(i=1;i<=G.vexnum;i++)
if(m[i].lowcost<n&&m[i].lowcost!=0)
{
n=m[i].lowcost;
j=i;
}
return j;
}
void MinSpanTree_PRIM(ALGraph G,char u)
{
int j,k,a;
close closedge;ArcNode *s,*p,*q;
for(j=1;j<=MAX_VERTEX_NUM;j++)
closedge[j].lowcost=MAX;//把所有值都赋为最大
k=LocateVek(G,u);
for(j=1;j<=G.vexnum;j++)
if(j!=k)
{
closedge[j].adjvex=u;
for(s=G.verties[k].firstarc;s!=NULL;s=s->nextarc)
if(j==s->adjvex)
{closedge[j].lowcost=s->info;
break;
}
}
closedge[k].lowcost=0;
cout<<"最小生成树 : "<<"{";//查找并输出最小生成树
for(j=1;j<G.vexnum;j++)
{
k=minimum(closedge);
cout<<"("<<closedge[k].adjvex<<","
<<G.verties[k].data<<")";
closedge[k].lowcost=0;
for(int i=1;i<=G.vexnum;i++)
{
for(p=G.verties[k].firstarc;p!=NULL;p=p->nextarc)
if(p->info<closedge[i].lowcost&&i==p->adjvex)
{
closedge[i].adjvex=G.verties[k].data;
closedge[i].lowcost=p->info;
}
}
}cout<<"}"<<endl;
cout<<"边及对应权值: "<<endl;//输出边及对应权值
for(j=G.vexnum;j>=1;j--)
{
if(closedge[j].lowcost==0&&G.verties[j].data!=u)
{ cout<<"("<<closedge[j].adjvex
<<","<<G.verties[j].data
<<") ==";
a=closedge[j].adjvex;
for(q=G.verties[j].firstarc;q!=NULL;q=q->nextarc)
if(a-64==q->adjvex)
cout<<q->info<<endl;
}
}
}
void Create(ALGraph &G)
{
int i,j,k,x;
char a,b;ArcNode *s;
cout<<"输入顶点数(1-20):";
cin>>G.vexnum;
cout<<"输入边数:";
cin>>G.arcnum;
cout<<"输入顶点信息:"<<endl;
for(i=1;i<=G.vexnum;i++)
{
cin>>G.verties[i].data;
G.verties[i].firstarc=NULL;
}
for(i=1;i<=G.arcnum;i++)
{
cout<<"输入相邻两结点和权值 ";
cin>>a>>b;cin>>x;
j=a-64;k=b-64;//将字符型转化成整数型
s=new ArcNode;
s->info=x;
s->adjvex=k;
s->nextarc=G.verties[j].firstarc;
G.verties[j].firstarc=s;
s=new ArcNode;
s->info=x;
s->adjvex=j;
s->nextarc=G.verties[k].firstarc;
G.verties[k].firstarc=s;
}
}
四、调试分析
1、在写程序时遇到很多有关专业名词のC语言编译，没有完全套用书上の固有解释，而是按照自己有限の英语词汇の理解去编译の。
2、通过求最小生成树，进一步掌握了图の含义。
五、运行结果
六、实验环境
（1）Windows XP系统下
（2）编程环境：VC6.0++ ，TC2.0
七、实验体会
通过此实验，通过求最小生成树，进一步掌握了图の含义。
知道了普里姆算法。
通过本次课程设计，锻炼了我们の实际操作能力，培养了我们严密の思维和严谨の态度。