无向连通网的最小生成树算法[第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

相关文章

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python如何生成指定文件大小

《python如何生成指定文件大小》:本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin(推荐)的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤:代码片段:2. 应用 JSON 样式到

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC(MediaAccessControl)地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

PyQt5+Python-docx实现一键生成测试报告

《PyQt5+Python-docx实现一键生成测试报告》作为一名测试工程师,你是否经历过手动填写测试报告的痛苦,本文将用Python的PyQt5和python-docx库,打造一款测试报告一键生成工... 目录引言工具功能亮点工具设计思路1. 界面设计:PyQt5实现数据输入2. 文档生成:python-