通讯网络

• 题目内容
• • 文献查阅情况
  • 问题解题思路
  • 算法执行情况分析
  • 插入链接与图片
  • 运行结果截图 
  • 总结
  • 参考文献目录

题目内容

（通讯网络）某地区共有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重印)