彻底搞懂克鲁斯卡尔(Kruskal)算法(附C++代码实现)

2023-11-05 00:20

本文主要是介绍彻底搞懂克鲁斯卡尔(Kruskal)算法(附C++代码实现),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.问题

图中的6个顶点分别代表6个村庄,线段的权值代表村庄之间的距离。请问如何找到最短的路径来访问每一个村庄,且每个村庄只访问一次。

二.解决

1.提取图的边,并将边按权值大小从小到大排列,并放入edge数组。如下:

    

2.创建根数组(辅助数组),数组下标代表顶点节点本身,其元素代表顶点的根节点,如下:

提示:这里的“根”并不是树结构中真正的根,一棵树中只有一个根,而这里的“根”泛指长辈,可能是父节点,也可能是“爷”节点。初始化根数组为-1,代表初始状态下每个顶点都各自代表一个集合。

 3.将edge数组中的边从小到大依次放回图中,如果后续加入的边与图中已放入的边形成了环,那么将此边丢弃,继续将下一条边放入,规则同前。

形成环,即说明加入的这条边的起点和终点已经属于一个集合,有共同的根。                      加入边的过程就是多个子集不断合并的过程,同一集合中的顶点不可相连。前面的辅助数组就是用来判断起点与终点是否属于一个集合。具体实现看代码注释。

 4.放入(顶点数-1)条边后,最小生成树(Minimum Spanning Tree)构建完成,即可结束循环。

一棵树有n个节点,则有n-1条边

三.细节 

上述算法主要有两点需要考虑:

  • 树的储存
  • 集合的表示

树的储存:常见的图储存结构有:邻接矩阵,邻接边表,十字链表,邻接多重表,边集数组                              显然,上述算法中频繁涉及到对边的操作,所以边集数组是最佳选择。

集合的表示:使用辅助数组,存放各顶点的根顶点,如果两个顶点的根相同,则属于同一集                        合,另则相反。初始化辅助数组元素为-1,代表每个顶点本身就是根节点。

四.实现 

#include<iostream>
#define MAX_VEX  10
#define MAX_EDGE 100  //10个顶点组成的无向图最多有100条边
#define TYPE int
using namespace std;struct Edge  //边的属性结构体
{TYPE start;TYPE end;TYPE weight;
};void ini_gragh(int& vex, int& edge, Edge* gragh);//采用边集数组储存图void sort_edge(Edge* edges,int edge);//使用冒泡排序,根据权值大小将边从小到大排序int find_root(int parent[], int n);//寻找根节点以判断是否在一个集合中int main()
{int vex; //顶点个数int edge; //边个数Edge gragh[MAX_EDGE];ini_gragh(vex, edge, gragh);//边集数组初始化图sort_edge(gragh, edge);//依据权值大小给边从小到大排序int roots[MAX_VEX];  //根数组,存放各顶点的根节点,以区别是否属于同一个集合Edge MST[MAX_EDGE];   //存放最小生成树(minimum spanning tree)int count = 0;  for (int i = 0; i < vex; i++)roots[i] = -1;  //初始化root数组,-1代表自己就是根节点;初始状态下每个顶点都是独立的根for (int i = 0; i < MAX_EDGE; i++){int vex_m = find_root(roots, gragh[i].start);//寻找起点的根节点int vex_n = find_root(roots, gragh[i].end);//寻找终点的根节点if (vex_m != vex_n)//如果两者的根节点不同,说明他们属于不同的集合,可以相连{MST[count] = gragh[i];//将此边放入MST数组count++;roots[vex_m] = vex_n;//将两个树合并,即将顶点vex_n作为vex_m的根节点}if (count == vex-1)//当count达到顶点数-1,说明最小树已经生成,退出循环break;}for (int i = 0; i < vex - 1; i++){printf("(%d,%d)%d\n", MST[i].start, MST[i].end, MST[i].weight);   //打印最小生成树}return 0;
}void ini_gragh(int& vex, int& edge, Edge* gragh)
{cout << "输入连通网顶点数:";cin >> vex;cout << "输入连通网边数: ";cin >> edge;cout << "依次输入各边的起点,终点和权重(空格隔开):" << endl;for (int i = 0; i < edge; i++){cin >> gragh[i].start >> gragh[i].end >> gragh[i].weight;}
}void sort_edge(Edge* edges_arr,int edge)
{Edge temp;	for (int i = 0; i < edge; i++){for (int k = 0; k < edge - i - 1; k++)//冒泡排序,注意这里要减1{if (edges_arr[k].weight > edges_arr[k + 1].weight){temp = edges_arr[k];edges_arr[k] = edges_arr[k + 1];edges_arr[k + 1] = temp;}}}
}int find_root(int roots[], int n)
{while (roots[n] > -1)  //迭代寻找根节点n = roots[n];return n;
}

运行结果:

 

 

这篇关于彻底搞懂克鲁斯卡尔(Kruskal)算法(附C++代码实现)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部

Python实现精准提取 PDF中的文本,表格与图片

《Python实现精准提取PDF中的文本,表格与图片》在实际的系统开发中,处理PDF文件不仅限于读取整页文本,还有提取文档中的表格数据,图片或特定区域的内容,下面我们来看看如何使用Python实... 目录安装 python 库提取 PDF 文本内容:获取整页文本与指定区域内容获取页面上的所有文本内容获取

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

Java使用HttpClient实现图片下载与本地保存功能

《Java使用HttpClient实现图片下载与本地保存功能》在当今数字化时代,网络资源的获取与处理已成为软件开发中的常见需求,其中,图片作为网络上最常见的资源之一,其下载与保存功能在许多应用场景中都... 目录引言一、Apache HttpClient简介二、技术栈与环境准备三、实现图片下载与保存功能1.

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》:本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal

Nexus安装和启动的实现教程

《Nexus安装和启动的实现教程》:本文主要介绍Nexus安装和启动的实现教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、Nexus下载二、Nexus安装和启动三、关闭Nexus总结一、Nexus下载官方下载链接:DownloadWindows系统根

SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程

《SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程》LiteFlow是一款专注于逻辑驱动流程编排的轻量级框架,它以组件化方式快速构建和执行业务流程,有效解耦复杂业务逻辑,下面给大... 目录一、基础概念1.1 组件(Component)1.2 规则(Rule)1.3 上下文(Conte

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》:本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma

MySQL 横向衍生表(Lateral Derived Tables)的实现

《MySQL横向衍生表(LateralDerivedTables)的实现》横向衍生表适用于在需要通过子查询获取中间结果集的场景,相对于普通衍生表,横向衍生表可以引用在其之前出现过的表名,本文就来... 目录一、横向衍生表用法示例1.1 用法示例1.2 使用建议前面我们介绍过mysql中的衍生表(From子句