本文主要是介绍BUAA(2021春) 最少布线(图)——Prim(BFS+贪心)+kruskal(并查集)双解法+原理解释,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
BUAA数据结构第七次编程题——最少布线(图)
- 看前须知
- 第七次上机题汇总
- 题目内容
- 问题描述
- 输入形式
- 输出形式
- 样例
- 样例说明
- 题解
- 思考和详解
- 参考代码
- 补充测试的数据
- 原理解释
- Prim(普里姆)算法
- kruskal(克鲁斯卡尔)算法
看前须知
要点介绍和简要声明.
第七次上机题汇总
图遍历(图-基本题)——邻接矩阵远比邻接表简单且好操作.
独立路径数计算——DFS+回溯.
最少布线(图)——Prim(BFS+贪心)+kruskal(并查集)双解法+原理解释.
北京地铁乘坐线路查询——Dijkstra和Floyd双解法.
题目内容
问题描述
北航主要办公科研楼有新主楼、逸夫楼、如心楼、办公楼、图书馆、主楼、一号楼等等;。北航网络中心计划要给相关建筑物间铺设光缆进行网络连通,请给出用料最少的铺设方案。
编写程序输入一个办公区域分布图及建筑物之间的距离,计算出用料最少的铺设方案(只有一组最优解,不用考虑多组解)。要求采用Prim或Kruskal算法实现。
输入形式
办公区域分布图的顶点(即建筑物)按照自然数(0,1,2,n-1)进行编号,从标准输入中首先输入两个正整数,分别表示线路图的顶点的数目和边的数目,然后在接下的行中输入每条边的信息,每条边占一行,具体形式如下:
< n> < e>
< id> < vi> < vj> < weight>
…
即顶点vi和vj之间边的权重是weight,边的编号是id。
输出形式
输出铺设光缆的最小用料数,然后另起一行输出需要铺设的边的id,并且输出的id值按照升序输出。
样例
6 101 0 1 6002 0 2 1003 0 3 5004 1 2 5005 2 3 5006 1 4 3007 2 4 6008 2 5 4009 3 5 20010 4 5 600
【样例输出】
15002 4 6 8 9
样例说明
样例输入说明该分布图有6个顶点,10条边;顶点0和1之间有条边,边的编号为1,权重为600;顶点0和2之间有条边,权重为100,其它类推。其对应图如下:
经计算此图的最少用料是1500,可以使图连通,边的编号是2 4 6 8 9。其对应的最小生成树如下:
题解
思考和详解
这道题我们可以采用Prim 和 kruskal两种解法,如果想知道这两者的解法的原理,可以移步拓展板块。
这道题就是最基础的最小生成树的算法题,按部就班来操作不难。
Prim
参考代码
Prim
#include<stdio.h>
#include<stdlib.h>
#define M 101
#define INF 0x3f3f3f3f
int sum,top=0,MinSpanTreeVertex[200],egdesID[200][200];
// MinSpanTreeVertex存储的是路径顶点ID,egdesID存储的是两个顶点间路径ID
void MinSpanTree_Prim(int weights[][M],int vertexNum,int FirstVertexID,int *edges);//Prim算法
int cmp (const void * a, const void * b);
int main()
{ int weights[M][M],edges[M];int i,j,k,vertexNum,edgeNum,ID;int v1,v2,w;scanf("%d %d",&vertexNum,&edgeNum); //顶点个数和边个数 for(i=0;i<vertexNum;i++)for(j=0;j<vertexNum;j++)weights[i][j]=INF; //初始化 for(i=0;i<edgeNum;i++){scanf("%d %d %d %d",&ID,&v1,&v2,&w); //录入信息 egdesID[v1][v2]=ID;egdesID[v2][v1]=ID;weights[v1][v2]=w;weights[v2][v1]=w;}MinSpanTree_Prim(weights,vertexNum,0,edges); //最小生成树 qsort(MinSpanTreeVertex,top,sizeof(int),cmp); //按要求排序 printf("%d\n",sum);for(i=0;i<vertexNum-1;i++)printf("%d ",MinSpanTreeVertex[i]); //输出 return 0;
}
//最小生成树——Prim算法(从0开始)
void MinSpanTree_Prim(int weights[][M],int vertexNum,int FirstVertexID,int *edges)
{// weights为权重数组, vertexNum为顶点个数, FirstVertexID为最小数第一个个节点,edges为最小生成树边int min,minweight[M];int i,j,k;for(i=0;i<vertexNum;i++) //初始化相关数组 {minweight[i]=weights[FirstVertexID][i]; //将传入的第一个顶点与之有边的权值存入数组 edges[i]=FirstVertexID; //初始化第一个顶点 }minweight[FirstVertexID] = 0; //将第一个顶点加入生成树,0 表示为相应下表的顶点已经加入树 for(i=1;i<vertexNum;i++){min=INF;for(j=0,k=0;j<vertexNum;j++)if(minweight[j]!=0 && minweight[j]<min){min = minweight[j];k=j; //在数组中找到最小值,其下标为 k }sum+=minweight[k];minweight[k] = 0;//找到最小生成树的一个新顶点//printf("%d ",egdesID[k][edges[k]]); MinSpanTreeVertex[top]=egdesID[k][edges[k]]; //记录顶点信息 top++;for(j=0;j<vertexNum;j++) //依次检查新加入的顶点 k 到未加入顶点之间的权值 if(minweight[j]!=0 && weights[k][j] < minweight[j]){minweight[j]=weights[k][j]; //替换操作 edges[j]=k;}}
}
int cmp (const void * a, const void * b)
{return *(int*)a - *(int*)b;
}
kruskal
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<stdbool.h>
struct edge //边结构体
{int ID; //路径ID int u,v; //两个顶点 int w; //权重
};
struct edge edges[600100];
int i,top=0;
int Father[10100],MinSpanTreeVertex[2000];
//Father存储的是每个顶点的最早出现(祖先)顶点,MinSpanTreeVertex存储的是路径顶点ID
int cnt;
long long res; //结果
//最小生成树——Kruskal算法(并查集)
void initFather(int vertexNum)
{int i; for(i=1;i<=vertexNum;++i){Father[i]=i; //初始话祖先数组(一开始都是自己本身的编号) }
}
int getFather(int x)
{return Father[x]==x?x:(Father[x]=getFather(Father[x])); //回退祖先
}
void kruskal(int vertexNum,int edgeNum)
{int p,q;cnt=0,res=0;for(i=0;i<edgeNum;++i){p=getFather(edges[i].u); //回退到祖先 q=getFather(edges[i].v); //回退到祖先 if(p!=q) //如果祖先不同(即没有构成闭环) {Father[p]=q; //更新祖先 MinSpanTreeVertex[top++]=edges[i].ID; //录入节点信息 res+=edges[i].w; //加上花费的费用 cnt++; //树节点+1 }if(cnt==vertexNum-1) //满足条件 {break;}}
}
int cmp(const void*p1,const void*p2) //按照权重排序
{struct edge *a=(struct edge*)p1;struct edge *b=(struct edge*)p2;return a->w-b->w;
}
int cmp2 (const void * a, const void * b) //按照大小排序
{return *(int*)a - *(int*)b;
}
int main()
{int n,m;scanf("%d%d",&n,&m);initFather(n); //初始化祖先数组 int i;for(i=0;i<m;i++)scanf("%d %d %d %d",&edges[i].ID,&edges[i].u,&edges[i].v,&edges[i].w);qsort(edges,m,sizeof(struct edge),cmp);kruskal(n,m);printf("%d\n",res);qsort(MinSpanTreeVertex,top,sizeof(int),cmp2); //排序 for(i=0;i<n-1;i++)printf("%d ",MinSpanTreeVertex[i]); //输出
}
补充测试的数据
【样例输入】
6 10
1 0 1 16
2 0 2 20
3 0 3 19
4 1 2 11
5 1 4 6
6 1 5 5
7 2 4 14
8 4 5 9
9 2 3 22
10 3 4 18
【样例输出】
56
1 4 5 6 10
原理解释
Prim(普里姆)算法
时间复杂度:O(N^2)(N为顶点数)
prim算法又称“加点法”,用于边数较多的带权无向连通图
方法:每次找与之连线权值最小的顶点(贪心),将该点加入最小生成树集合中,直到所有点都访问完(BFS访问)。
注意:相同权值任选其中一个即可,但是不允许出现闭合回路的情况。
开始操作:1. 先随便选一个点(因为最后所有的点都会在最小生成树里,所以可以随便选)。
2.比较1点的边(1,5,6),选择权值为1的边.
3. 比较1,3两点的边(4,5,5,5,6,6),选择权值为4的边。
4.比较1,3,6三点的边(2,5,5,5,6,6),选择权值为2的边。
5.比较1,3,4,6四点的边(5,6,6),选择权值为5顶点边
5.比较1,2,3,4,6五点的边(3,6),选择权值为3顶点边
6.完成构造
kruskal(克鲁斯卡尔)算法
时间复杂度:O(NlogN)(N为边数)
kruskal算法又称“加边法”,用于边数较少的稀疏图
方法:每次找图中权值最小的边,将边连接的两个顶点加入最小生成树集合中
注意:相同权值任选其中一个即可,但是不允许出现闭合回路(并查集)的情况。
第一步:按照边的权重对边进行排序
第二步:从上至下依次取出边,每次取的边如果在树中形成了环路则必须丢弃。直到最后一条顶点被连接在树中则最小生成树生成。
在取出(D,E)这条边时由于与(C,D)、(C,E)产生了回路,所以丢弃这条边。
这里我们就来到了问题的重点了,我们到底如何判断新加进来的边到底会不会形成一个环路呢?这里我们可以使用并查集的。
判断回路的产生
初始状态我们将图中每一个结点都看成一颗树,就比如这样:
此时我们取出排序边集中的第一条边(C,D),我们发现C、D两个节点来自不同的树,这就说明这条边的加入不会形成环路。此时我么需要将D树置成C的子树。就比如这样:
此时我们取出第二条边(C,A),我们发现C、A两个节点属于不同的树,所以(C,A)边的加入不会成环,我们将这条边加到最小生成树的边集当中,此时我们将需要将A树置为C的子树,就比如这样:
我们取出第三条边(C,E),发现C、E仍然属于两个不同的树,所以我们依旧将这条边加入最小生成树的边集当中。然后将E树置为C树的子树,就比如这样:
重点来了,我们取出第四条边(D,E),发现这两个节点都来自同一个树,说明如果我们将(D,E)边加入到生成树的边集中就会形成环路,所以(D,E)这条边就需要舍弃。
我们取出第五条边:(A,B),发现A、B属于不同的节点,这就代表这个边的加入不会成环,我们将这条边加入最小生成树的边集当中。这是我们发现边集中边的数量加一刚好等于节点数,这也就说明,每个节点都已将包含在最小生成树的边集当中了,也就不需要继续向下取排序边集了。
此时我们将边集中的边重构成一张图,也就是一个最小生成树了:
上面就是整个Kruskal的思路
这篇关于BUAA(2021春) 最少布线(图)——Prim(BFS+贪心)+kruskal(并查集)双解法+原理解释的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!