本次课程设计要求在n个城市之间架设n-1条线路，实现这几个城市之间的网络通信，要求网络经济代价最低。具体要求如下：
课程设计要求
根据设计要求，我们假设城市之间的距离越大架设网线的经济代价越大，因此可以用两个城市之间的距离作为边的权重。
n个城市之间最多可以生成 1+2+...+(n-1)条边，分别计算出每条边的长度然后对他们进行升序排序，利用并查集得到由n-1条边组成的最小生成树，问题便得到解决。
为了解决上述问题，需要构建一个城市结构体CITY来表示城市，并且还需要构建EDGE结构体来表示城市与城市的边，并利用随机函数生成城市的坐标。
本课程设计的全部代码如下：
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#define MaxSize (10000)//n的取值最大为MaxSize
/*---------------------结构体定义---------------------*/
typedef struct City{
//城市结构体
int id;//城市ID
int x, y;//城市的坐标
}CITY;
typedef struct edges{
//边结构体
int s, e;//s为起始顶点 e为终止顶点
double cost;//边的权值，即两个顶点之间的距离
}EDGE;
/*---------------------生成城市并显示---------------------*/
void CreateCityPos(CITY *& city, int n){
//随机生成城市坐标
city = (CITY*)malloc(sizeof(CITY)* n);
srand((unsigned)time(NULL));//设置随机数的种子
for (int i = 0; i < n; ++i)
{//随机生成n个城市的x,y坐标值
city[i].id = i + 1;
city[i].x = rand() % 100;
city[i].y = rand() % 100;
}
}
void ShowCityPos(CITY*city, int n)
{//显示城市信息，城市序号、x坐标和y坐标
printf("\n各城市的编号及坐标:\n");
for (int i = 0; i < n; ++i)
{
printf("%d:[%d, %d]\n", city[i].id, city[i].x, city[i].y);
}
}
/*---------------------计算城市两两之间的距离，生成边数组---------------------*/
int Sum(int n)
{//计算n的前n项和，用于根据顶点确定边的数目 当顶点为n时 则最多可以产生Sum(n-1)条边
int sum = 0;
for (int i = 1; i <= n; ++i)
sum += i;
return sum;
}
double CityDist(const CITY*a, const CITY*b)
{//计算两个城市之间的距离
return sqrt(double((a->x - b->x)*(a->x - b->x) + (a->y - b->y)*(a->y - b->y)));
}
void CreateEdges(EDGE* & e, CITY* city, int n)
{//根据城市信息生成城市之间的边
e = (EDGE*)malloc(sizeof(EDGE)*Sum(n - 1));//边的总数为Sum(n-1)
int cnt = 0;
for (int i = 0; i < n; ++i)
{
for (int k = i + 1; k < n; ++k)
{
(e + cnt)->s = city[i].id;//起始顶点
(e + cnt)->e = city[k].id;//终止顶点
(e + cnt)->cost = CityDist(&city[i], &city[k]);//边的权值
++cnt;
}
}
}
void ShowCityEdges(EDGE*edges, int n)
{//打印边信息
printf("\n各城市间的距离(城市1-城市2:边权值（距离）)\n");
//show edges:
for (int i = 0; i < Sum(n-1); ++i)
printf("%d-%d : %f\n", edges[i].s, edges[i].e, edges[i].cost);
}
/*--------------------KrusKal求最小生成树----------------------*/
int cmp(const void*a, const void *b)
{//比较函数 比较两条边的权值 用于排序
EDGE* aa, *bb;
aa = (EDGE*)a; bb = (EDGE*)b;
if ((aa->cost - bb->cost )> 0) return 1;
else return -1;
}
//最小生成树
int v[MaxSize];
int getRoot(int a)
{//找到根节点
while (a != v[a]) a = v[a];
return a;
}
void KrusKal(EDGE* edges, int n)
{//KrusKal算法生成最小生成树
int i;
int e, a, b;
double sum = 0.0;
e = Sum(n - 1);
for (i = 0; i < n; ++i) //初始化并查集
v[i] = i;
printf("\n最小生成树的边及权值:\n");
for (i = 0; i < e; ++i)
{
a = getRoot(edges[i].s);
b = getRoot(edges[i].e);
if (a != b)
{//将边并入生成树
v[a] = b;
printf("%d-%d: %f\n", edges[i].s, edges[i].e, edges[i].cost);//打印并入生成树的边的两个顶点和权值
sum += edges[i].cost;//计算生成树的总权值
}
}
printf("\n生成树总权值sum =%f\n", sum);
}
/*------------------------------KrusKal END-------------------------------------*/
void solve(int n)
{
CITY*city;
EDGE* edges;
CreateCityPos(city, n);//创建城市
ShowCityPos(city, n);//显示城市
CreateEdges(edges, city, n);//创建边（根据所有城市两两之间的距离来创建）
qsort(edges, Sum(n - 1), sizeof(EDGE), cmp);//对边按权值进行升序排序
ShowCityEdges(edges, n);//显示排序后的边
KrusKal(edges, n);//用KrusKal算法生成最小生成树
}
int main()
{
int n;
printf("请输入n:");
scanf("%d", &n);
if (n < 2)
return 1;
solve(n);
return 0;
}//运行成功 2019年5月21日10:53:07
/*程序说明：
基本思想：1、首先生成n个城市，每个城市的坐标随机生成，这部分由CreateCityPos（）函数实现；
2、计算n个城市两两之间的距离（距离计算由CityDist()完成），并保存到边数组中，这部分由CreateEdges（）函数实现；
3、由边数组(edges[])根据KrusKal算法求最小生成树，这部分由KrusKal（）函数实现，要注意的是进行KrusKal算法之前，需要对edges[]中的元素按照
权值进行升序排序，因此调用了stdlib.h头文件中的qsort()函数来进行排序。
*/
运行结果：
程序运行结果
n为城市的数量，需要有用户从终端输入。
网友评论