解題思路
首先理解題意是求生成圖的最小生成圖醋寝，然后利用算法編寫程序，之后加上通過磁盤文件讀取數據带迟，最后考慮圖片形式輸出音羞。
算法實現
設G=(V,E)是一個無向連通網，令T=(U,TE)是G的最小生成樹仓犬。T的初始化狀態(tài)為U={ v0 }( v0 ∈V),TE={}嗅绰，重復執(zhí)行以下操作：在所有u∈U,v∈V–U的邊中一條代價最小的邊（u,v）并入集合TE,同時v并入U,直至U=V為止。此時TE中必有n-1條邊婶肩，則T就是一棵最小生成樹办陷。為了節(jié)省時間和空間，在邊集中選取最短邊時律歼，對于V–U中的每個頂點民镜，只保留從該頂點到U中某頂點的最短邊。
偽代碼描述如下：
- 初始化：U={ v0 },TE={}险毁；
- 重復執(zhí)行以下操作制圈，直至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;// 居民區(qū)個數, 管道條數
int area1, area2;// 某管道的兩個居民區(qū)
int price;//管道單位長度價格
int distance, lower_distance = 0;//兩居民區(qū)間的距離,最短總路線長度
int areaArrary[MaxNum][MaxNum];//將表示居民區(qū)的無向圖用鄰接矩陣表示
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 << "--請輸入各管道連接的兩居民區(qū)及距離,如: 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];// 居民區(qū)i距離目前生成樹的點集中某個居民區(qū)的最短路程
int near_area[MaxNum];// 目前生成樹的點集中能使距離下一居民區(qū)最近的居民區(qū)
int min_way;// 目前生成樹的點集外頂點到目前生成樹的點集內頂點具有最短路徑的邊
int temp_area;// 與目前生成樹的點集路程最短的居民區(qū)
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設計成功! 居民小區(qū)管道鋪設最優(yōu)方案設計如下:\n";
for (i = 1; i < areaNum; i++)//第一個頂點0已加入生成樹,循環(huán)將剩下的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 << "居民區(qū)" << near_area[temp_area] << "----(" << min_way << "米)----居民區(qū)" << 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);//退出程序 }
}
}
mfc實現
圖1-1
圖1-2
運行結果
以data1.txt和data2.txt為例試運行。
文本文件中有居民區(qū)數量楷掉，管道數量景鼠，單位管道價格，各管道連接的兩居民區(qū)及長度甘磨。
圖2-1
圖2-2
圖2-3
圖2-4
結果正確。
