管道铺设施工的最佳方案选择。n(n>10)个居民区之间需要铺设煤

2019-03-04 本文已影响0人 F1NEEN

解题思路

首先理解题意是求生成图的最小生成图，然后利用算法编写程序，之后加上通过磁盘文件读取数据，最后考虑图片形式输出。

算法实现

设G=(V,E)是一个无向连通网，令T=(U,TE)是G的最小生成树。T的初始化状态为U={ v0 }( v0 ∈V),TE={}，重复执行以下操作：在所有u∈U,v∈V–U的边中一条代价最小的边（u,v）并入集合TE,同时v并入U,直至U=V为止。此时TE中必有n-1条边，则T就是一棵最小生成树。为了节省时间和空间，在边集中选取最短边时，对于V–U中的每个顶点，只保留从该顶点到U中某顶点的最短边。
伪代码描述如下：

初始化：U={ v0 },TE={}；
重复执行以下操作，直至U=V：
2.1 在E中寻找最短边(u，v)，且满足u∈U,v∈V–U；
2.2 U=U+{V}；
2.3 TE=TE+{（u,v）}；

#include <iostream>
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
#define undefineNum 9999;//默认初始化数据的值
const int MaxNum = 50;//存储图数据的数组的最大值
int main(void)
{
goon:cout << "**********************************************\n";
    cout << "****      管道铺设施工的最佳方案选择      ****\n";
    cout << "****             Author: 潘悦             ****\n";
    cout << "****            Grade: 软工1703           ****\n";
    cout << "****            Time: 2019/2/27           ****\n";
    cout << "**********************************************\n\n";
    int areaNum, lineNum;// 居民区个数, 管道条数
    int area1, area2;// 某管道的两个居民区
    int price;//管道单位长度价格
    int distance, lower_distance = 0;//两居民区间的距离,最短总路线长度
    int areaArrary[MaxNum][MaxNum];//将表示居民区的无向图用邻接矩阵表示
    int i, j;//变量
    FILE *f;
    char *arr;
    arr = "data1.txt";
    if((f = fopen(arr, "rb")) == NULL)
    {
        printf("文件无法打开\n");
        exit(0);
    }
    fscanf(f, "%d", &areaNum);
    fscanf(f, "%d", &lineNum);
    fscanf(f, "%d", &price);
    for (i = 0; i < areaNum; i++)
        for (j = 0; j < areaNum; j++)
            areaArrary[i][j] = undefineNum;//初始化图的邻接矩阵  
    cout << "--请输入各管道连接的两居民区及距离,如: 0 1 50\n";
    j = 1;//j表示第n条线路
    for (i = 0; i < lineNum; i++)
    {
        fscanf(f, "%d", &area1);
        fscanf(f, "%d", &area2);
        fscanf(f, "%d", &distance);
        areaArrary[area1][area2] = distance;
        areaArrary[area2][area1] = distance;
        j++;
    }
    fclose(f);
    int short_way[MaxNum];// 居民区i距离目前生成树的点集中某个居民区的最短路程
    int near_area[MaxNum];// 目前生成树的点集中能使距离下一居民区最近的居民区
    int min_way;// 目前生成树的点集外顶点到目前生成树的点集内顶点具有最短路径的边
    int temp_area;// 与目前生成树的点集路程最短的居民区  
    for (i = 1; i < areaNum; i++)//将第一个顶点0加入最小生成树的点集中
    {
        short_way[i] = areaArrary[0][i];
        near_area[i] = 0;
    }
    short_way[i] = 0;
    near_area[i] = 0;
    cout << "\n设计成功! 居民小区管道铺设最优方案设计如下:\n";
    for (i = 1; i < areaNum; i++)//第一个顶点0已加入生成树,循环将剩下的n-1个顶点加入生成树
    {
        min_way = undefineNum;      j = 1;      temp_area = 1;
        while (j < areaNum)
        {
            if (short_way[j] != 0 && short_way[j] < min_way)
            {
                min_way = short_way[j];
                temp_area = j;
            }
            j++;
        }
        cout << "居民区" << near_area[temp_area] << "----(" << min_way << "米)----居民区" << temp_area << endl;
        short_way[temp_area] = 0;
        lower_distance += min_way;//计算最短总长度
        for (j = 0; j < areaNum; j++)//更新候选最短路径数组
            if (areaArrary[temp_area][j] < short_way[j])
            {
                short_way[j] = areaArrary[temp_area][j];
                near_area[j] = temp_area;
            }
    }
    cout << "最短总长度为: " << lower_distance << "米" << endl;
    cout << "最低总造价为: " << lower_distance * price << "元" << endl << endl;
    char choice;
    cout << "清空数据,重新输入?    YES(y) or NO(n) : "; cin >> choice;
    if (choice == 'y')
    {
        system("cls");//清空屏幕,重新开始
        goto goon;
    }
    if (choice == 'n')
    {
        cout << "\n       恭喜你,成功退出!\n\n";
        exit(0);//退出程序  }
    }
}