通訊網絡

• 題目内容
• • 文獻查閱情況
  • 問題解題思路
  • 算法執行情況分析
  • 插傳入連結接與圖檔
  • 運作結果截圖 
  • 總結
  • 參考文獻目錄

題目内容

（通訊網絡）某地區共有n座村莊，每座村莊的坐标(x,y)已知，現在要在村莊之間建立通訊網絡。通訊工具有兩種，分别是需要鋪設的普通線路和無線通訊的衛星裝置。隻能給k個村莊配備衛星裝置，擁有衛星裝置的村莊互相間可直接通訊。鋪設了線路的村莊之間也可以通訊。但是由于技術原因，兩個村莊之間線路長度最多不能超過 d, 否則就會由于信号衰減導緻通訊不可靠。要想增大 d 值，則會導緻要投入更多的裝置（成本）。如何配置設定衛星裝置，才能使各個村莊之間能直接或間接的通訊，并且 d 的值最小？

文獻查閱情況

給定一個無向圖，如果它任意兩個頂點都聯通并且是一棵樹，那麼我們就稱之為生成樹(Spanning Tree)。如果是帶權值的無向圖，那麼權值之和最小的生成樹，我們就稱之為最小生成樹(MST, Minimum Spanning Tree)。

我們由最小生成樹的定義，可以延伸出一個修建道路的問題：把無向圖的每個頂點看作村莊，計劃修建道路使得可以在所有村莊之間通行。把每個村莊之間修建道路的費用看作權值，那麼我們就可以得到一個求解修建道路的最小費用的問題。

常見求解最小生成樹的算法有Kruskal算法和Prim算法。由于篇幅問題再此對于Prim算法，就不多做解釋了。現在我們看看Kruskal算法，是怎麼來求解最小生成樹的問題。

Kruskal算法描述

Kruskal算法是基于貪心的思想得到的。首先我們把所有的邊按照權值先從小到大排列，接着按照順序選取每條邊，如果這條邊的兩個端點不屬于同一集合，那麼就将它們合并，直到所有的點都屬于同一個集合為止。至于怎麼合并到一個集合，那麼這裡我們就可以用到一個工具——-并查集(不知道的同學請移步：Here)。換而言之，Kruskal算法就是基于并查集的貪心算法。

Kruskal算法流程

對于圖G(V,E)，以下是算法描述：
           

輸入： 圖G

輸出： 圖G的最小生成樹

具體流程：

(1)将圖G看做一個森林，每個頂點為一棵獨立的樹

(2)将所有的邊加入集合S，即一開始S = E

(3)從S中拿出一條最短的邊(u,v)，如果(u,v)不在同一棵樹内，則連接配接u,v合并這兩棵樹，同時将(u,v)加入生成樹的邊集E’

(4)重複(3)直到所有點屬于同一棵樹，邊集E’就是一棵最小生成樹

問題解題思路

第一步模組化，輸入n個村莊坐标Xi,Yi，将村莊看做結點，建立無向完全圖，

接着建立最小生成樹

kruskal算法（避圈法）建立最小生成樹

• 所有邊按照權值非降次序排序
• 選取權值最小且沒有回路的邊，記錄選取的邊對應的結點
• 所有的結點都包含在樹中即可結束，選取（n-1）條邊

共需要邊n-1條。由于隻能k個村莊之間用衛星，即

最小生成樹中最長的k-1條邊需要删去，不鋪設通訊線路，滿足條件為：删

除後，剩餘的邊中，最長的邊要<=d。由于衛星可以連接配接子產品中任意村莊，

是以在建立最小生成樹後，删除邊的過程中，每删除一條邊，需記下被删除

邊的兩個村莊的坐标，即為需要衛星相連接配接的村莊的坐标，輸出衛星配置設定

##算法流程

using namespace std;
#include <math.h>//添加數學函數庫
#define maxn 100
#include<stdio.h>
#include<algorithm>
typedef struct{
    int x, y;
    double w;
}edge;
edge e[maxn];
int rank_[maxn], father[maxn],  sum;
int cmp(edge a, edge b){  //按權值非降序排序(相同則按x坐标)
    if(a.w == b.w)  return a.x < b.x;
    return a.w < b.w;
}

void make_set(int x){
    father[x] = x; 
    rank_[x] = 0;
}

int find_set(int x){
    return  x != father[x] ? find_set(father[x]) : father[x];
}

void union_set(int x, int y, int w){
    sum += w;
    if(x == y)  return ;
    if(rank_[x] > rank_[y])  father[y] = x;
    else{
        if(rank_[x] == rank_[y])  rank_[y]++;
        father[x] = y;
    }
}
//現在隻需要寫檔案輸入n,k,d,加n村莊個坐标，
//輸出得到“每行倆村莊對應 的英文字母“空格” 距離d”
int main(){
	int i,j,n,k,d;
	double D[100][100];//d[1][4]即為第二個村莊與第五個村莊之間的距離 
	FILE*fp1=fopen("in.txt","r");
    //fscanf(fp,"%d %d %d", &n);
	//freopen("in.txt", "r", stdin);//讀檔案 in.txt
	fscanf(fp1,"%d %d %d", &n,&k,&d);//輸出得到“每行倆村莊對應的英文字母  距離d”
    printf("輸入n,k,d   %d %d %d\n", n, k, d);
    for(i = 0; i < n; i++){
        fscanf(fp1,"%d %d", &e[i].x, &e[i].y);
        //getchar(); 
        printf("村莊%c的坐标：( %d , %d )\n", i + 'A', e[i].x, e[i].y);
    }
    fclose(fp1);  //關閉檔案
	printf("\n\n");
	 
    //運算d
    int a,b;
	for(i = 0; i < n; i++)
	for(j = 1; j < n; j++){
	 	a=e[i].x-e[j].x;
	 	b=e[i].y-e[j].y;
	 	if( a < 0)a=-a;
	 	if( b < 0)b=-b;
	 	D[i][j]=sqrt(a*a+b*b);	//添加數學函數庫  printf("%lf\n",sqrt(a)); 3.000000
	} 
	FILE*fp2=fopen("kruskal.txt","w");
	fprintf(fp2,"%d\n",n*(n-1)/2);
	for(i = 0; i < n; i++)
	for(j = i+1; j < n; j++){
	 	fprintf(fp2,"%c %c %lf\n", i + 'A', j + 'A',D[i][j]);	
	}	
	fclose(fp2);//關閉檔案 
int x, y,n1;//kruskal完成最小生成樹 
    char cx, cy;
    FILE*fp=fopen("kruskal.txt","r+");
    fscanf(fp,"%d\n", &n1);
    printf("模組化得n1=%d條邊的無向完全圖\n", n);
    //getchar();
    for(i = 0; i < n1; i++){
        fscanf(fp,"%c %c %lf\n", &cx, &cy, &e[i].w);
        printf("%c %c %f\n", cx, cy, e[i].w);
    }

	freopen("kruskal.txt", "r", stdin);
    scanf("%d", &n1);
    getchar();
    for(i = 0; i < n1; i++){
        scanf("%c %c %lf", &cx, &cy, &e[i].w);
        getchar();
        e[i].x = cx -'A', e[i].y = cy - 'A';
        make_set(i);  //0對應于A
    }
    sort(e, e + n1, cmp);
    printf("n1=%d\n",n1); //問題所在 
    printf("n=%d\n",n);
    a=0;b=0;
    int number=0;//鋪設線路裝置的條數 
    printf("建立最小生成樹:\n");
    	for(i = 0; i < n1; i++){
        x = find_set(e[i].x), y = find_set(e[i].y);
        if(x != y){
            printf("%c-%c : %lf\n", e[i].x + 'A', e[i].y + 'A', e[i].w);
            union_set(x, y, e[i].w);
	}
	printf("依次删除%d條最大邊，形成%d個子產品\n這些子產品用衛星通訊,既保證了d最小，又使得各村莊能通訊\n", k-1, k);
    //printf("total:  %lf\n", sum);
	
	return 0;
}

           

算法執行情況分析

插傳入連結接與圖檔

連結: link.(https://img-blog.csdnimg.cn/20190115115347668.png)

圖檔:

//現在隻需要寫檔案輸入n,k,d,加n村莊個坐标，

//輸出得到“每行倆村莊對應的英文字母“空格” 距離d”

用以輸入的檔案及内容，輸入n,k,d,加n村莊個坐标x y

用以輸出生成樹的檔案及内容,輸出得到“完全圖的邊數，每行倆村莊對應的英文字母“空格” 距離d”

運作結果截圖

[dev c++]

總結

由于我是用freopen(“kruskal.txt”, “w”, stdout); //stdout是标準輸出流，預設為螢幕%/向檔案kruskal.txt輸出資料即邊數及每個結點之間的權值，fclose(stdout); //關閉檔案。前一步模組化完成，關閉了儲存模組化資料的檔案kruskal.txt，接着就無法再打開這個檔案進行讀取資料，那麼後面的kruskal算法就無法進行下去。于是我采取了改進方案

（1）在fclose(stdout)之後如果想恢複原來的stdout的話：

fdopen( fd_stdout, “r” );

freopen(“kruskal.txt”, "r ", stdin);//讀檔案kruskal.txt

當然，方案1freopen（）——重定向标準輸入輸出流

失敗了，于是采取方案2；

（2）采用指針fp指向檔案，而不是對标準輸入輸出流重定向FILEfp2=fopen(“kruskal.txt”,“w”);

fprintf(fp2,"%d\n",n(n-1)/2);

當然在做這份報告的過程中也遇到了些許難以解決的問題，在翻遍了百度也無法找到我想要的答案的時候，幸好我的同學們伸出了援助之手，真幸運，最後問題得以被解決。

參考文獻目錄

張瑞霞 張敬偉，《資料結構與算法》，—北京：清華大學出版社，2018

張瑞霞主編 《資料結構與算法實驗教程》，—北京：清華大學出版社，2018

古天龍，常亮，《離散數學》，—北京：清華大學出版社，2012.7(2017.8重印)