【高阶数据结构】图的应用--最小生成树

2024-09-02 00:04

本文主要是介绍【高阶数据结构】图的应用--最小生成树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、最小生成树

连通图中的每一棵生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树就不在连通;反之,在其中引入任何一条新边,都会形成一条回路。

若连通图由n个顶点组成,则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条:

1.只能使用图中的边来构造最小生成树

2.只能使用恰好n-1条边来连接图中的n个顶点

3.选用的n-1条边不能构成回路

构造最小生成树的方法:Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。

贪心算法:是指在问题求解时,总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择,而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。

二、Kruskal算法

任给一个有n个顶点的连通网络N={V,E},首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL},其中每个顶点自成一个连通分量,其次不断从E中取出权值最小的一条边(若有多条任取其一),若该边的两个顶点来自不同的连通分量,则将此边加入到G中。如此重复,直到所有顶点在同一个连通分量上为止。

核心:每次迭代时,选出一条具有最小权值,且两端点不在同一连通分量上的边,加入生成树。

在这里插入图片描述

在图23-1上执行Kruskal算法的过程。加了阴影的边属于不断增长的森林A。该算法按照边的权重大小依次进行考虑。箭头指向的边是算法每一步所考察的边。如果该条边将两棵不同的树连接起来,它就被加入到森林里,从而完成对两棵树的合并

我们对使用领接矩阵实现的图来查找最小生成树

代码实现:

// 临接矩阵
namespace Matrix
{template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>class Graph{typedef Graph<V, W, MAX_W, Direction> Self;private:std::vector<V> _vertexs;             // 顶点集合std::map<V, size_t> _vIndexMap;      // 顶点的下标映射关系std::vector<std::vector<W>> _matrix; // 存储边集合的矩阵struct Edge{size_t _srci;size_t _dsti;W _w;Edge(size_t srci, size_t dsti, const W &w): _srci(srci), _dsti(dsti), _w(w){}bool operator>(const Edge &e) const{return _w > e._w;}};W Kruskal(Self &minTree){size_t n = _vertexs.size();minTree._vertexs = _vertexs;minTree._vIndexMap = _vIndexMap;minTree._matrix.resize(n);for (int i = 0; i < n; i++){minTree._matrix[i].resize(n, MAX_W);}std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> minqueue;for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){if (i < j && _matrix[i][j] != MAX_W){minqueue.push({i, j, _matrix[i][j]});}}}// 选出n-1条边size_t size = 0;W totalW = W();UnionFindSet ufs(n);while (minqueue.size()){Edge min = minqueue.top();minqueue.pop();if (ufs.InSet(min._srci, min._dsti) == false){std::cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << std::endl;minTree._AddEdge(min._srci, min._dsti, min._w);ufs.Union(min._srci, min._dsti);++size;totalW += min._w;}else{std::cout << "构成环:";std::cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << std::endl;}}if (size == n - 1)return totalW;elsereturn W();}};
}

三、Prim算法

与Kruskal算法类似,Prim 算法也是23.1节所讨论的通用最小生成树算法的一个特例。Prim 算法的工作原理与Dijkstra的最短路径算法相似(该算法将在24.3节中讨论)。Prim算法所具有的一个性质是集合A中的边总是构成一裸树。如图23-5所示,这梯树从一个任意的根结点r开始,一直长大到覆盖V中的所有结点时为止。算法每一步在连接集合A和A之外的结点的所有边中,选择一条轻量级边加入到A中。根据推论23.2,这条规则所加人的边都是对A安全的边。因此,当算法终止时,A中的边形成一棵最小生成树。本策略也属于贪心策略,因为每一步所加人的边都必须是使树的总权重增加量最小的边。

在这里插入图片描述

代码实现:

// 临接矩阵
namespace Matrix
{template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>class Graph{typedef Graph<V, W, MAX_W, Direction> Self;private:std::vector<V> _vertexs;             // 顶点集合std::map<V, size_t> _vIndexMap;      // 顶点的下标映射关系std::vector<std::vector<W>> _matrix; // 存储边集合的矩阵W Prim(Self &minTree, const V &v){minTree._vertexs = _vertexs;minTree._vIndexMap = _vIndexMap;int n = _vertexs.size();minTree._matrix.resize(n);for (int i = 0; i < n; i++){minTree._matrix[i].resize(n, MAX_W);}size_t srci = GetVertexIndex(v);// 标记数组,将顶点分为两个部分,一个是一个加入最小生成树的部分,一个是未加入的std::vector<bool> X(n, false);std::vector<bool> Y(n, true);X[srci] = true;Y[srci] = false;std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> minq;for (size_t i = 0; i < n; i++){if (_matrix[srci][i] != MAX_W){minq.push({srci, i, _matrix[srci][i]});}}size_t size = 0;W totalW = W();while (minq.size()){Edge min = minq.top();minq.pop();size_t srci = min._srci;size_t dsti = min._dsti;if (X[min._dsti]){std::cout << "构成环:";std::cout << _vertexs[srci] << "->" << _vertexs[dsti] << ":" << _matrix[srci][dsti] << std::endl;}else{minTree._AddEdge(srci, dsti, _matrix[srci][dsti]);std::cout << _vertexs[srci] << "->" << _vertexs[dsti] << ":" << min._w << std::endl;X[dsti] = true;Y[dsti] = false;++size;totalW += _matrix[srci][dsti];if (size == n - 1)break;for (size_t i = 0; i < n; i++){if (_matrix[dsti][i] != MAX_W && Y[i]){minq.push({dsti, i, _matrix[dsti][i]});}}}}if (size == n - 1){return totalW;}elsereturn W();}};
}

测试代码:

void TestGraphMinTree()
{const char str[] = "abcdefghi";Graph<char, int> g(str, strlen(str));g.AddEdge('a', 'b', 4);g.AddEdge('a', 'h', 8);// g.AddEdge('a', 'h', 9);g.AddEdge('b', 'c', 8);g.AddEdge('b', 'h', 11);g.AddEdge('c', 'i', 2);g.AddEdge('c', 'f', 4);g.AddEdge('c', 'd', 7);g.AddEdge('d', 'f', 14);g.AddEdge('d', 'e', 9);g.AddEdge('e', 'f', 10);g.AddEdge('f', 'g', 2);g.AddEdge('g', 'h', 1);g.AddEdge('g', 'i', 6);g.AddEdge('h', 'i', 7);Graph<char, int> kminTree;std::cout << "Kruskal:" << g.Kruskal(kminTree) << std::endl;kminTree.Print();std::cout << std::endl<< std::endl;Graph<char, int> pminTree;std::cout << "Prim:" << g.Prim(pminTree, 'a') << std::endl;pminTree.Print();std::cout << std::endl;for (size_t i = 0; i < strlen(str); ++i){std::cout << "Prim:" << g.Prim(pminTree, str[i]) << std::endl;}
}

这篇关于【高阶数据结构】图的应用--最小生成树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时

C/C++随机数生成的五种方法

《C/C++随机数生成的五种方法》C++作为一种古老的编程语言,其随机数生成的方法已经经历了多次的变革,早期的C++版本使用的是rand()函数和RAND_MAX常量,这种方法虽然简单,但并不总是提供... 目录C/C++ 随机数生成方法1. 使用 rand() 和 srand()2. 使用 <random