高分求 数据结构课程设计

Question

构造可以使n个城市连接的最小生成树
问题描述：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
基本要求：
（1）、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
（2）、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）
（3）、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
对所编写的源程序的要求：
①能够达到系统功能的基本要求，鼓励自行增加新功能；
②要有可视化用户界面。尽可能的使界面友好、直观、易操作；
③开发工具任选，源程序要有适当的注释，使程序容易阅读。

我的邮箱是[email protected] 哪位大哥或大姐帮帮忙 不胜感激！

Answer 1

浪费积分干嘛？

prim算法的实现
/************************************************************
作者: 黄位富 04281190 记科0407.
工具: VC++ 6.0.
题目:
创建时间: 2006年11月26日.
修改时间: 2006年11月30日.
/**********************************************************/
#include <stdio.h>
#define MAXVEVERTEXNUM 6//图的点数
#define MAXIMUMCOST 100 //两点间不相邻距离为100
int truev[MAXVEVERTEXNUM];
//truev[v]=1代表v是V集合的点 truev[v]=0是S-V集合的点

initadjmatrix(int Matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM],int truev[MAXVEVERTEXNUM])
//初始化邻接矩阵 不相邻边的权为MAXIMUMCOST
{
int matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM]=
{
{MAXIMUMCOST,6,1,5,MAXIMUMCOST,MAXIMUMCOST},//v1到其他点的距离
{6,MAXIMUMCOST,5,MAXIMUMCOST,3,MAXIMUMCOST},//v2到其他点的距离
{1,5,MAXIMUMCOST,5,6,4}, //v3到其他点的距离
{5,MAXIMUMCOST,5,MAXIMUMCOST,MAXIMUMCOST,2},//v4到其他点的距离
{MAXIMUMCOST,3,6,MAXIMUMCOST,MAXIMUMCOST,6},//v5到其他点的距离
{MAXIMUMCOST,MAXIMUMCOST,4,2,6,MAXIMUMCOST} //v6到其他点的距离
};
//图的初始化
int i=0,j;
while(i<MAXVEVERTEXNUM)
{
truev[i]=0;//初始时V集合为空
i++;
}
for( i=0;i<MAXVEVERTEXNUM;i++)
for ( j=0;j<MAXVEVERTEXNUM;j++)
{
Matrix[i][j]=matrix[i][j];
printf("%4d",matrix[i][j]);
if(j!=0&&j%(MAXVEVERTEXNUM-1)==0)
printf("\n");
}
//打印邻接矩阵
return 1;
}

int minimum(int truve[MAXVEVERTEXNUM],int temp1[MAXVEVERTEXNUM],int temp2[MAXVEVERTEXNUM],int N)
{
//找出权最小的边并把对应的结点放到V集合中
int Temp1,Temp2;
int i,min;
min=temp1[0];
Temp2=temp2[0];//默认为第一个
for (i=0;i<=N;i++)
{
if(temp1[i]<min)
{
Temp1=min;min=temp1[i];temp1[i]=Temp1;
Temp2=temp2[i];//最小权的下标
}
}
printf("%d!!\n",Temp2+1);
truev[Temp2]=1;//放入V集合中
return 1;
}

prim(int count,int matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM],int truve[MAXVEVERTEXNUM])
{
int temp1[(MAXVEVERTEXNUM/2)*((MAXVEVERTEXNUM+1)/2)];
int temp2[(MAXVEVERTEXNUM/2)*((MAXVEVERTEXNUM+1)/2)];
int i,j;
int N=0;
if(count==MAXVEVERTEXNUM-1) return 1;
for(i=0;i<MAXVEVERTEXNUM;i++)
{
for(j=0;j<MAXVEVERTEXNUM;j++)
{
if(truev[i]==1&&truev[j]==0&&matrix[i][j]<MAXIMUMCOST)
{
temp1[N]=matrix[i][j];
//V中的点和S-V中的点如果相邻依此保存其权
temp2[N]=j; //在S-V中找出与V中相连的点并保存
N++;
}
}
}
minimum(truve,temp1,temp2,N-1);
//求得V与S-V之间的最短路径及其所对应的结点
count++;
prim(count,matrix,truve);
}

void main()
{
int Map[MAXVEVERTEXNUM][MAXVEVERTEXNUM];//图
int v0,count=0; //当count=MAXVEVERTEXNUM时结束递归
initadjmatrix(Map,truev);//图的初始化
printf("图的结点是从1开始.\n");
printf("请输入开始结点:");
scanf("%d",&v0); //取v0
if(v0<1||v0>MAXVEVERTEXNUM) printf("v0<1或者v0>MAXVEVERTEXNUM!!ERROR\n");//数据不对
else
{
v0--; //图的结点从1开始
truev[v0]=1; //v0进V集合
printf("过程:\n");
printf("%d!!\n",v0+1);//v0
prim(count,Map,truev);
}//主要算法
}
http://tieba.baidu.com/f?kz=152476970

kruskal算法实现
//给出kruskal球联通网络的最小生成树的算法实现
//调试成功
#include<iostream>
#include<stack>
using namespace std;
int main()
{
stack<int> travstack;
int i,j,k,n=5;
cout<<"以矩阵形式表示"<<endl;
int a[5][5],b[5][5],c[5][5],d[5];
cout<<"请输入各路径权值";
for( i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
cout<<"a[i][j]="<<endl;
cin>>a[i][j];
}
int biggest=0,big=1000;
for(k=0;k<n*n-n;k++)
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i][j]>biggest&&a[i][j]<big)
{
biggest=a[i][j];
travstack.push(i);
travstack.push(j);
}
big=a[i][j];
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
int p1,p2;
p1=travstack.top();//p1=j
travstack.pop();
p2=travstack.top();//p2=i
travstack.pop();
if(b[p1][p2]==0)
{
b[p1][p2]=1;
b[p2][p1]=1;
c[p2][p1]=a[p2][p1];
if(d[p1]==0&&d[p2]==0)
d[p1]=d[p2]=1;

else if(d[p1]==0)
{
d[p1]=1;
for( i=0;i<n;i++)
{
if(b[p2][i]==1)
{
b[p1][i]=1;
b[i][p1]=1;
}
}
}
else if(d[p2]==0)
{
d[p2]=1;
for(i=0;i<n;i++)
{
if(b[p1][i]==1)
{
b[p2][i]=1;
b[i][p2]=1;
}
}
}
}
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
cout<<"c[i][j]="<<c[i][j];
cout<<endl;
for(int k=0;k<n;k++)
cout<<"*";
}
return 0;
}

http://www.cppblog.com/xingkong178/archive/2008/06/03/52045.aspx

参考资料：网络搜索