本次課程設(shè)計(jì)要求在n個(gè)城市之間架設(shè)n-1條線路，實(shí)現(xiàn)這幾個(gè)城市之間的網(wǎng)絡(luò)通信，要求網(wǎng)絡(luò)經(jīng)濟(jì)代價(jià)最低。具體要求如下：

課程設(shè)計(jì)要求

根據(jù)設(shè)計(jì)要求，我們假設(shè)城市之間的距離越大架設(shè)網(wǎng)線的經(jīng)濟(jì)代價(jià)越大，因此可以用兩個(gè)城市之間的距離作為邊的權(quán)重。

n個(gè)城市之間最多可以生成 1+2+...+(n-1)條邊，分別計(jì)算出每條邊的長度然后對他們進(jìn)行升序排序，利用并查集得到由n-1條邊組成的最小生成樹，問題便得到解決。

為了解決上述問題，需要構(gòu)建一個(gè)城市結(jié)構(gòu)體CITY來表示城市，并且還需要構(gòu)建EDGE結(jié)構(gòu)體來表示城市與城市的邊，并利用隨機(jī)函數(shù)生成城市的坐標(biāo)。

本課程設(shè)計(jì)的全部代碼如下：

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#define MaxSize (10000)//n的取值最大為MaxSize
/*---------------------結(jié)構(gòu)體定義---------------------*/
typedef struct City{
    //城市結(jié)構(gòu)體
    int id;//城市ID
    int x, y;//城市的坐標(biāo)
}CITY;

typedef struct edges{
    //邊結(jié)構(gòu)體
    int s, e;//s為起始頂點(diǎn) e為終止頂點(diǎn)
    double cost;//邊的權(quán)值，即兩個(gè)頂點(diǎn)之間的距離
}EDGE;

/*---------------------生成城市并顯示---------------------*/
void CreateCityPos(CITY *& city, int n){
    //隨機(jī)生成城市坐標(biāo)
    city = (CITY*)malloc(sizeof(CITY)* n);
    srand((unsigned)time(NULL));//設(shè)置隨機(jī)數(shù)的種子
    for (int i = 0; i < n; ++i)
    {//隨機(jī)生成n個(gè)城市的x,y坐標(biāo)值
        city[i].id = i + 1;
        city[i].x = rand() % 100;
        city[i].y = rand() % 100;
    }
}
void ShowCityPos(CITY*city, int n)
{//顯示城市信息，城市序號、x坐標(biāo)和y坐標(biāo)
    printf("\n各城市的編號及坐標(biāo):\n");
    for (int i = 0; i < n; ++i)
    {
        printf("%d:[%d, %d]\n", city[i].id, city[i].x, city[i].y);
    }
}

/*---------------------計(jì)算城市兩兩之間的距離，生成邊數(shù)組---------------------*/
int Sum(int n)
{//計(jì)算n的前n項(xiàng)和，用于根據(jù)頂點(diǎn)確定邊的數(shù)目 當(dāng)頂點(diǎn)為n時(shí) 則最多可以產(chǎ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)
{//計(jì)算兩個(gè)城市之間的距離
    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)
{//根據(jù)城市信息生成城市之間的邊
    e = (EDGE*)malloc(sizeof(EDGE)*Sum(n - 1));//邊的總數(shù)為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;//起始頂點(diǎn)
            (e + cnt)->e = city[k].id;//終止頂點(diǎn)
            (e + cnt)->cost = CityDist(&city[i], &city[k]);//邊的權(quán)值
            ++cnt;
        }
    }
}
void ShowCityEdges(EDGE*edges, int n)
{//打印邊信息
    printf("\n各城市間的距離(城市1-城市2:邊權(quán)值（距離）)\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)
{//比較函數(shù) 比較兩條邊的權(quán)值 用于排序
    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)
{//找到根節(jié)點(diǎn)
    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最小生成樹的邊及權(quá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);//打印并入生成樹的邊的兩個(gè)頂點(diǎn)和權(quán)值
            sum += edges[i].cost;//計(jì)算生成樹的總權(quán)值
        }
    }
    printf("\n生成樹總權(quán)值sum =%f\n", sum);
}

/*------------------------------KrusKal END-------------------------------------*/

void solve(int n)
{
    CITY*city;
    EDGE* edges;
    CreateCityPos(city, n);//創(chuàng)建城市
    ShowCityPos(city, n);//顯示城市

    CreateEdges(edges, city, n);//創(chuàng)建邊（根據(jù)所有城市兩兩之間的距離來創(chuàng)建）
    qsort(edges, Sum(n - 1), sizeof(EDGE), cmp);//對邊按權(quán)值進(jìn)行升序排序
    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;
}//運(yùn)行成功 2019年5月21日10:53:07

/*程序說明：

基本思想：1、首先生成n個(gè)城市，每個(gè)城市的坐標(biāo)隨機(jī)生成，這部分由CreateCityPos（）函數(shù)實(shí)現(xiàn)；
    
         2、計(jì)算n個(gè)城市兩兩之間的距離（距離計(jì)算由CityDist()完成），并保存到邊數(shù)組中，這部分由CreateEdges（）函數(shù)實(shí)現(xiàn)；

         3、由邊數(shù)組(edges[])根據(jù)KrusKal算法求最小生成樹，這部分由KrusKal（）函數(shù)實(shí)現(xiàn)，要注意的是進(jìn)行KrusKal算法之前，需要對edges[]中的元素按照

         權(quán)值進(jìn)行升序排序，因此調(diào)用了stdlib.h頭文件中的qsort()函數(shù)來進(jìn)行排序。

*/

運(yùn)行結(jié)果：

程序運(yùn)行結(jié)果

n為城市的數(shù)量，需要有用戶從終端輸入。