【课程设计】最小生成树应用

树

字数统计: 1.3k阅读时长: 5 min

 2021/03/31 

需求描述

本次课程设计要求在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()函数来进行排序。
*/