无向连通网的最小生成树算法[第1部分]

2024-05-15 21:32

本文主要是介绍无向连通网的最小生成树算法[第1部分],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

摘要:求解图的最小生成树在工程管理、最优化规划等领域有广泛的应用,因此对最小生成树算法的研究具有重要的意义。本文针对图的最小生成树算法,首先对几种经典的最小生成树算法进行了总结,最后针对无向连通网的最小生成树问题,分别使用普利姆算法和克鲁斯卡尔算法进行了详细的算法原理分析与程序实现。
关键词:无向连通网;最小生成树算法;普利姆算法;克鲁斯卡尔算法
The Minimum Spanning Tree Algorithm of undirected connected network

Abstract:The minimum spanning tree of graphs is widely used in engineering management, optimization planning and other areas, so it is very important to study the minimum spanning tree algorithm. In this paper, Several classical minimum spanning tree algorithms are summarized, At the same time, a detailed algorithm analysis and program realization are carried out for the minimum spanning tree problem of undirected connected network by using the Prim algorithm and the Kruskal algorithm.
Key words:Undirected connected network;MST;Prim algorithm;Kruskal algorithm
1 引 言
求解图的最小生成树(Minimum Spanning Tree,MST)属于图论的典型应用问题。其中,连通图的最小生成树在理论研究和工程设计上均有广泛的研究和应用,因此最小生成问题从提出到理论描述,再到算法实现方式都取得了丰富的研究和应用成果。迄今为止,国内外学者就最小生成树问题,分别针对有向图和无向图提出了多种解决策略。其中,针对带权值的有向图,吴文虎等[1]提出了通过有向圈的收缩和展开求解最小生成树的策略;冯俊文[2]等提出了基于表格表示的表上作业法;对于无向图的最小生成树算法,包含Prim算法、Kruskal算法、Dijkstra最小生成树等经典的求解算法[3]。本文针对无向连通网的最小生成树问题,首先针对经典的Prim算法通过从部分最小生成树边集合扩展的角度逐步从剩余候选边集中选取最小边构造最小生成树;针对Kruskal算法可能的环路问题,通过使用并查集[4-5]来对所选的边进行连通分量的判断,同时对所选边集合进行路径压缩提高下一次查询效率。最后给出了详细的算法设计流程和实例验证。
2 算法描述
最小生成树问题在实际的工程管理、最优化规划等方面有实际的应用价值,例如交通路网的规划、旅行路线规划、通信网络设计、故障诊断[6-7]等。因此在基于图论的应用问题中,通常需要对带权值的无向连通图求最小生成。在求无向连通网的最小生成树时,需要预先构造一个带权值的无向连通图并用邻接矩阵表示图的存储结构,无向连通网和邻接矩阵表示分别如下所示(其中*表示距离为无穷)。
这里写图片描述
在最小生成树的求解算法中,Prim算法和kruskal算法使用最为广泛,本文利用Prim算法和Kruskal算法思想进行详细的程序设计与求解验证。
2.1 Prim算法
这里写图片描述
这里写图片描述
2.2 Kruskal算法
这里写图片描述
3 算法实现描述
3.1 Prim算法实现描述
根据Prim算法的思想和伪代码,在程序开始时需要给定一个连通网并给出一个初始顶点。接着从最小生成树边集合扩展的角度,从剩余结点和边中选择出权值最小的边,分别加入生成树的顶点集合和边集合。由于对于连通网其生成树总是存在的,因此根据生成树的性质,对于N个结点的连通网,需要N-1条边是的任意两个结点之间相互连通,那么算法结束的条件满足经过N-1此迭代,并在每一次迭代中选择出权值最小的边。如果在任意一次迭代过程中,不存在由已经加入生成树和剩余顶点集之间取值最小的边,则该连通网的输入数据存在错误导致图不连通。
为了方便实现边信息的表示,定义一个结构体类型的边结点edgeNode,该结点中存储边的起始顶点from、终点顶点to以及边的权值cost,同时定义邻接矩阵AdjMatrix和边集合数组edgeSet。
这里写图片描述
这里写图片描述
为了表述普利姆算法边和顶点的加入过程,使用流程图[8]来表示整个程序各实现步骤之间的逻辑关系,普利姆算法程序运行流程图如下:
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
3.2 Kruakal算法实现描述
根据Kruskal算法的思想和伪代码,程序在开始的时候需要对连通网中的边按照权值排序,接着从边集合扩展的角度,从剩余边集中选择最小的边,若所选边加入后不构成环路,则分别将边和顶点加入生成树的顶点集合和边集合。由于无向连通网的生成树总是存在的,根据生成树性质,对于N个结点的连通图,需要N-1条边使得任意两个结点之间相互连通,因此算法结束的条件是从边集中选择N-1条边。如果所有的边遍历完,选择边的数量小于N-1,则该连通网的输入数据存在错误导致图不连通。
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
4 算法实现及主要函数模块说明
为了实现Prim算法和Kruskal算法,程序中定义了边结点用来表示一条边的两个顶点及权值数据,边结点edgeNode定义如下:
typedef struct edgeNode
{
int from,to;
int cost;
}
EDGENODE;
4.1 Prim算法及主要的功能函数模块说明
(1)creatMatrix函数模块
函数原型:void creatMatrix(int **AdjMatrix,int n,int e);
函数功能:以文件读入或者键盘输入的方式构造邻接矩阵,AdjMatrix表示邻接矩阵,n和e分别表示图的顶点数和边数。
(2)printMatrix函数模块
函数原型:void printMatrix(int **AdjMatrix,int n);
函数功能:输出邻接矩阵,AdjMatrix表示邻接矩阵,n表示图的顶点数。
(3)initEdgeSet函数模块
函数原型:void initEdgeSet(int **AdjMatrix,EDGENODE *edgeSet,int n,int start);
函数功能:将start与其他顶点之间的权值存放到候选边集合edgeSet中。
(4)chooseEdge函数模块
函数原型:int chooseEdge(EDGENODE *edgeSet,int n,int index);
函数功能:从候选边集edgeSet中选出最小边结点,其中 index为edgeSet选取边时下标的起始位置。
(5)modfiyEdgeSet函数模块
函数原型:void modfiyEdgeSet(int **AdjMatrix,EDGENODE *edgeSet,int n,int index,int to);
函数功能:新加入结点后,调整候选边集edgeSet中的待选边结点,其中to为新加入到中的顶点编号。
(6)primMst最小生成树函数模块
函数原型:void primMst(int **AdjMatrix,EDGENODE *edgeSet,int n,int start);
函数功能:通过顶点从候选边集中选取最小边构造最小生成树。
(7)printMst最小生成树输出函数模块
函数原型:void printMst(EDGENODE *edgeSet,int n);
函数功能:输出最终最小生成树中的选取的边和最小权值和。

这篇关于无向连通网的最小生成树算法[第1部分]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/992976

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];