#include"stdio.h"
#include"string.h"
#include"malloc.h"
#include"iostream.h"
#include "iomanip.h"
#define MAX 10 //最多顶点个数
#define large 32768//表示极大值，即∞ typedef struct
{
int adj; //adj是权值类型
}ArcNode; typedef struct
{
int vexs[MAX]; //vexs表示顶点编号
int vexnum; //顶点个数
int arcnum; //边的个数
ArcNode arcs[MAX][MAX]; /*邻接矩阵*/
}T; typedef struct
{
int adjvex; //存放顶点编号
int lowcost; //存放顶点权值
}Node;
Node close[MAX];//求最小生成树时的辅助数组
int flag=0; int Locate(T *G,int V) //求顶点位置函数
{
int j=-1,k;
for(k=0;k<G->vexnum;k++)
if(G->vexs[k]==V) {j=k;break;}
return j;
}
T *creat(T *G) //创建无向网
{
int i,j,k,v1,v2,weight,m=1;
printf("请输入网中的顶点数：");
scanf("%d",&G->vexnum);
if(G->vexnum<=1)
{
cout<<"\n****************最小生成树不存在!****************** ***"<<endl;
flag=1;
return G;
}
else
{
printf("请输入网中的边数：");
scanf("%d",&G->arcnum);
for(i=0;i<G->vexnum;i++) //初始化邻接矩阵
for(j=0;j<G->vexnum;j++)
if(i==j)
G->arcs[i][j].adj=0;
else
G->arcs[i][j].adj=large;
printf("请输入网中的顶点编号："); //输入网中的顶点编号
for(i=0;i<G->vexnum;i++)
scanf("%d",&G->vexs[i]);
printf("输入每条弧所对应的两个顶点及权值<格式：起点 终点 权值>!\n");
for(k=0;k<G->arcnum;k++)
{
cout<<"请输入第"<<m++<<"条弧：";
cin>>v1>>v2>>weight; //输入一条弧的两个顶点及权值
i=Locate(G,v1);
j=Locate(G,v2);
G->arcs[i][j].adj=weight;
G->arcs[j][i].adj=weight;
}
return(G);
}}
int Minium(T *G,Node close[])//close[]中权值最小的边
{
int i,min,k;
min=large;//置最小权值为large
for(i=0;i<G->vexnum;i++)
if(close[i].lowcost<min&&close[i].lowcost!=0)
{
min=close[i].lowcost;k=i;
}
return k;//返回权值最小的边在辅助数组中的位置
}
void prim(T *G,int u)//普里姆算法
{
int i,j,k,k0,u0,v0,s=0,n=0; //从顶点u出发,按普里姆算法构造连通网G的最小生成树，并输出生成树的每条边
T *p;
p=(T *)malloc(sizeof(T));
k=Locate(G,u);//k为顶点u的位置
p->vexs[n++]=u;
close[k].lowcost=0;//初始化U={u}
for(i=0;i<G->vexnum;i++)
if(i!=k) //对V-U中的顶点i,初始化close[i]
{
close[i].adjvex=u;
close[i].lowcost=G->arcs[k][i].adj;
}
for(j=1;j<=G->vexnum-1;j++)//找n-1条边(n=G->vexnum)
{
k0=Minium(G,close);//close[k0]中存有当前最小边(u0, v0)的信息
u0=close[k0].adjvex;//u0∈U
v0=G->vexs[k0]; //v0∈V-U
p->vexs[n++]=v0;//将终点放入数组中
s+=close[k0].lowcost;//求最小生成树的权值之和
cout<<" <"<<u0<<"->"<<v0<<">"<<"\t"<<close[k0].lowcost<<endl; //输出最小生成树的路径
close[k0].lowcost=0;//将顶点v0纳入U集合
for(i=0;i<G->vexnum;i++)//在顶点v0并入U之后,更新closedge[i]
if(G->arcs[k0][i].adj<close[i].lowcost)
{
close[i].lowcost=G->arcs[k0][i].adj;
close[i].adjvex=v0;
}
}
cout<<"\n最小生成树中的顶点序列为：[";
for(i=0;i<G->vexnum;i++) cout<<" "<<p->vexs[i]<<" ";
cout<<"]"<<endl;
cout<<"\n最小生成树的权值之和为："<<s<<endl;
}
void display(T *G) //输出邻接矩阵算法
{
int i,j;
for(i=0;i<G->vexnum;i++)
cout<<"\t"<<G->vexs[i];
cout<<endl;
cout<<"——│";
for(i=0;i<G->vexnum;i++)
cout<<"————";
cout<<endl;
for(i=0;i<G->vexnum;i++)
{
cout<<" "<<G->vexs[i]<<" "<<"│";
for(j=0;j<G->vexnum;j++)
if(G->arcs[i][j].adj==large) cout<<"\t"<<"∞";
else cout<<"\t"<<G->arcs[i][j].adj;
cout<<endl;
}
for(i=0;i<G->vexnum;i++)
cout<<"—————";
cout<<endl;
} void main() //主函数
{ char ch;
int st;
T *G,*p;
p=(T *)malloc(sizeof(T)); cout<<"*******************************************************"<<endl;
cout<<setw(46)<<"普里姆最小生成树算法!"<<endl;
cout<<"\n*****************************************************"<<endl;
cout<<" 设 计 者：王正飞"<<endl;
cout<<" 班 级：11计本1"<<endl;
cout<<" 指导老师：张贯宏老师"<<endl;
cout<<" 设计时间：2013年6月27日"<<endl; cout<<"\n****************************************************"<<endl;
cout<<"\n*******************若创建无向网请输入'Y',否则按任意键!**************************"<<endl;
cin>>ch;
while(1)
if(ch=='Y'||ch=='y')
{ G=creat(p);
if(flag==0)
{ cout<<"\n************该无向网所对应的邻接矩阵如下***********"<<endl;
display(G);
cout<<endl<<"请输入起点:";
cin>>st;
while(1)
{
if(st==0) break;
else if(st>G->vexnum)
cout<<"-------------------------输入起点有错，请重新输入!------------------------------"<<endl;
else
{
cout<<endl<<"----------------利用普里姆算法从起点 ["<<st<<"] 出发,最小生成树的路径如下--------------"<<endl<<endl;
cout<<"\n*****************************************************"<<endl;
cout<<"<起点->终点> 权值"<<endl<<endl;
prim(G,st); cout<<"\n*************************************************"<<endl;
}
cout<<endl<<"请继续输入起点,否则输入0退出!"<<endl;
cin>>st;
}
}
cout<<"\n*****************继续创建无向网请输入'Y',否则按任意键!**************************"<<endl;
cin>>ch;
flag=0;
}
else break;
}

渣