C语言实现最小生成树构造算法
最小生成树
最小生成树(minimum spanning tree)是由n个顶点,n-1条边,将一个连通图连接起来,且使权值最小的结构。
最小生成树可以用Prim(普里姆)算法或kruskal(克鲁斯卡尔)算法求出。
我们将以下面的带权连通图为例讲解这两种算法的实现:
注:由于测试输入数据较多,程序可以采用文件输入
Prim(普里姆)算法
时间复杂度:O(N^2)(N为顶点数)
prim算法又称“加点法”,用于边数较多的带权无向连通图
方法:每次找与之连线权值最小的顶点,将该点加入最小生成树集合中
注意:相同权值任选其中一个即可,但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最小生成树:
1.初始化:
lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0表示i点加入了MST。
mst[i]:表示对应lowcost[i]的起点,当mst[i]=0表示起点i加入MST。
由于我们规定最开始的顶点是1,所以lowcost[1]=0,MST[1]=0。即只需要对2~n进行初始化即可。
#define MAX 100 #define MAXCOST 0x7fffffff int graph[MAX][MAX]; void prim(int graph[][MAX], int n) { int lowcost[MAX]; int mst[MAX]; int i, j, min, minid, sum = 0; for (i = 2; i <= n; i++) { lowcost[i] = graph[1][i];//lowcost存放顶点1可达点的路径长度 mst[i] = 1;//初始化以1位起始点 } mst[1] = 0;
2.查找最小权值及路径更新
定义一个最小权值min和一个最小顶点ID minid,通过循环查找出min和minid,另外由于规定了某一顶点如果被连入,则lowcost[i]=0,所以不需要担心重复点问题。所以找出的终点minid在MST[i]中可以找到对应起点,min为权值,直接输出即可。
我们连入了一个新的顶点,自然需要对这一点可达的路径及权值进行更新,所以循环中还应该包括路径更新的代码。
for (i = 2; i <= n; i++) { min = MAXCOST; minid = 0; for (j = 2; j <= n; j++) { if (lowcost[j] < min && lowcost[j] != 0) { min = lowcost[j];//找出权值最短的路径长度 minid = j; //找出最小的ID } } printf("V%d-V%d=%d\n",mst[minid],minid,min); sum += min;//求和 lowcost[minid] = 0;//该处最短路径置为0 for (j = 2; j <= n; j++) { if (graph[minid][j] < lowcost[j])//对这一点直达的顶点进行路径更新 { lowcost[j] = graph[minid][j]; mst[j] = minid; } } } printf("最小权值之和=%d\n",sum); }
具体代码如下:
#include<stdio.h> #define MAX 100 #define MAXCOST 0x7fffffff int graph[MAX][MAX]; void prim(int graph[][MAX], int n) { int lowcost[MAX]; int mst[MAX]; int i, j, min, minid, sum = 0; for (i = 2; i <= n; i++) { lowcost[i] = graph[1][i];//lowcost存放顶点1可达点的路径长度 mst[i] = 1;//初始化以1位起始点 } mst[1] = 0; for (i = 2; i <= n; i++) { min = MAXCOST; minid = 0; for (j = 2; j <= n; j++) { if (lowcost[j] < min && lowcost[j] != 0) { min = lowcost[j];//找出权值最短的路径长度 minid = j; //找出最小的ID } } printf("V%d-V%d=%d\n",mst[minid],minid,min); sum += min;//求和 lowcost[minid] = 0;//该处最短路径置为0 for (j = 2; j <= n; j++) { if (graph[minid][j] < lowcost[j])//对这一点直达的顶点进行路径更新 { lowcost[j] = graph[minid][j]; mst[j] = minid; } } } printf("最小权值之和=%d\n",sum); } int main() { int i, j, k, m, n; int x, y, cost; //freopen("1.txt","r",stdin);//文件输入 scanf("%d%d",&m,&n);//m=顶点的个数,n=边的个数 for (i = 1; i <= m; i++)//初始化图 { for (j = 1; j <= m; j++) { graph[i][j] = MAXCOST; } } for (k = 1; k <= n; k++) { scanf("%d%d%d",&i,&j,&cost); graph[i][j] = cost; graph[j][i] = cost; } prim(graph, m); return 0; }
编译运行结果:
kruskal(克鲁斯卡尔)算法
时间复杂度:O(NlogN)(N为边数)
kruskal算法又称“加边法”,用于边数较少的稀疏图
方法:每次找图中权值最小的边,将边连接的两个顶点加入最小生成树集合中
注意:相同权值任选其中一个即可,但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最小生成树:
1.初始化:
构建边的结构体,包括起始顶点、终止顶点,边的权值
借用一个辅助数组vset[i]用来判断某边是否加入了最小生成树集合
#define MAXE 100 #define MAXV 100 typedef struct{ int vex1; //边的起始顶点 int vex2; //边的终止顶点 int weight; //边的权值 }Edge; void kruskal(Edge E[],int n,int e) { int i,j,m1,m2,sn1,sn2,k,sum=0; int vset[n+1]; for(i=1;i<=n;i++) //初始化辅助数组 vset[i]=i; k=1;//表示当前构造最小生成树的第k条边,初值为1 j=0;//E中边的下标,初值为0
2.取边和辅助集合更新
按照排好的顺序依次取边,若不属于同一集合则将其加入最小生成树集合,每当加入新的边,所连接的两个点即纳入最小生成树集合,为避免重复添加,需要进行辅助集合更新
注:由于kruskal算法需要按照权值大小顺序取边,所以应该事先对图按权值升序,这里我采用了快速排序算法,具体算法可以参照快速排序(C语言)
while(k<e)//生成的边数小于e时继续循环 { m1=E[j].vex1; m2=E[j].vex2;//取一条边的两个邻接点 sn1=vset[m1]; sn2=vset[m2]; //分别得到两个顶点所属的集合编号 if(sn1!=sn2)//两顶点分属于不同的集合,该边是最小生成树的一条边 {//防止出现闭合回路 printf("V%d-V%d=%d\n",m1,m2,E[j].weight); sum+=E[j].weight; k++; //生成边数增加 if(k>=n) break; for(i=1;i<=n;i++) //两个集合统一编号 if (vset[i]==sn2) //集合编号为sn2的改为sn1 vset[i]=sn1; } j++; //扫描下一条边 } printf("最小权值之和=%d\n",sum); }
具体算法实现:
#include <stdio.h> #define MAXE 100 #define MAXV 100 typedef struct{ int vex1; //边的起始顶点 int vex2; //边的终止顶点 int weight; //边的权值 }Edge; void kruskal(Edge E[],int n,int e) { int i,j,m1,m2,sn1,sn2,k,sum=0; int vset[n+1]; for(i=1;i<=n;i++) //初始化辅助数组 vset[i]=i; k=1;//表示当前构造最小生成树的第k条边,初值为1 j=0;//E中边的下标,初值为0 while(k<e)//生成的边数小于e时继续循环 { m1=E[j].vex1; m2=E[j].vex2;//取一条边的两个邻接点 sn1=vset[m1]; sn2=vset[m2]; //分别得到两个顶点所属的集合编号 if(sn1!=sn2)//两顶点分属于不同的集合,该边是最小生成树的一条边 {//防止出现闭合回路 printf("V%d-V%d=%d\n",m1,m2,E[j].weight); sum+=E[j].weight; k++; //生成边数增加 if(k>=n) break; for(i=1;i<=n;i++) //两个集合统一编号 if (vset[i]==sn2) //集合编号为sn2的改为sn1 vset[i]=sn1; } j++; //扫描下一条边 } printf("最小权值之和=%d\n",sum); } int fun(Edge arr[],int low,int high) { int key; Edge lowx; lowx=arr[low]; key=arr[low].weight; while(low<high) { while(low<high && arr[high].weight>=key) high--; if(low<high) arr[low++]=arr[high]; while(low<high && arr[low].weight<=key) low++; if(low<high) arr[high--]=arr[low]; } arr[low]=lowx; return low; } void quick_sort(Edge arr[],int start,int end) { int pos; if(start<end) { pos=fun(arr,start,end); quick_sort(arr,start,pos-1); quick_sort(arr,pos+1,end); } } int main() { Edge E[MAXE]; int nume,numn; //freopen("1.txt","r",stdin);//文件输入 printf("输入顶数和边数:\n"); scanf("%d%d",&numn,&nume); for(int i=0;i<nume;i++) scanf("%d%d%d",&E[i].vex1,&E[i].vex2,&E[i].weight); quick_sort(E,0,nume-1); kruskal(E,numn,nume); }
编译运行结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04