数据结构 —— 最小生成树

news/2024/10/5 23:02:50/

数据结构 —— 最小生成树

  • 什么是最小生成树
  • Kruskal算法
  • Prim算法

今天我们来看一下最小生成树：

我们之前学习的遍历算法并没有考虑权值，仅仅就是遍历结点：
在这里插入图片描述今天的最小生成树要满足几个条件：

  1. 考虑权值
  2. 所有结点联通
  3. 权值之和最小
  4. 无环

在这里插入图片描述

什么是最小生成树

最小生成树（Minimum Spanning Tree，简称MST）是指在一个加权的、无向的连通图中，由所有顶点构成的一个子图，这个子图是一棵树，并且其所有边的权重之和最小。换句话说，最小生成树是在保证图中所有顶点连通的前提下，使得连接这些顶点的边的总成本最低的一棵树。

最小生成树具有以下特性：

  1. 它包含图中的所有顶点。
  2. 它是一个没有环的连通子图（即树）。
  3. 它的边数比顶点数少一（对于 n 个顶点的图，有 n-1 条边）。
  4. 它的边的总权重是所有可能生成树中最小的。

最小生成树在很多实际应用中都有重要作用，例如在设计电信网络时，为了连接多个地点而需要铺设电缆或光纤，最小生成树可以用来确定一种成本最低的铺设方案。

求解最小生成树的常用算法包括：

  • Kruskal算法：此算法通过不断选择权重最小的边来构建最小生成树，同时避免添加会导致环路形成的边。它通常利用并查集（Disjoint Set Union）数据结构来检测环路。
  • Prim算法：此算法从任意一个顶点开始，逐步将顶点及其权重最小的连接边加入到生成树中，直到所有顶点都被包含进来。Prim算法可以使用优先队列（Priority Queue）来高效地选择下一个应加入的边。

我们今天就来介绍一下这两种算法：

Kruskal算法

Kruskal算法，简单来说，就是把所有边拿出来，从小到大挑边，构成最小生成树：

Kruskal算法是一种用于寻找加权、无向连通图的最小生成树（Minimum Spanning Tree, MST）的贪心算法。它的核心思想是在不形成任何环路的情况下，选择权重最小的边来构建生成树，直到所有的顶点都被包含在树中。

以下是Kruskal算法的主要步骤：

  1. 排序边：将图中所有的边按照权重从小到大排序。
  2. 初始化森林：创建一个森林，其中每个顶点都是一个单独的树（即每个顶点都是一个独立的连通分量）。
  3. 选择边：遍历排序后的边列表。对于每条边，检查它的两个端点是否已经在同一棵树中（即是否属于同一个连通分量）。如果不是，将这条边添加到最小生成树中，并将这两个顶点所在的树合并成一棵更大的树。
  4. 重复步骤3：继续选择满足条件的边，直到最小生成树中包含了图中的所有顶点，或者已经选择了n-1条边（其中n是顶点的数量）。

在这里插入图片描述

Kruskal算法的关键在于能够快速地检测边的两个端点是否属于同一棵树，这通常是通过使用并查集（Union-Find）数据结构来实现的。并查集允许我们在对数时间内执行“查找”操作（确定顶点所属的树）和“合并”操作（将两棵树合并成一棵树）。

// 使用Kruskal算法计算最小生成树的总权重
W Kruskal(Self& minTree) // Self应为当前类的引用，minTree是用于存储最小生成树的实例
{// 初始化最小生成树的顶点集和索引minTree._vertex = _vertex;minTree._index = _index;minTree._matrix.resize(_vertex.size()); // 创建一个邻接矩阵，用于存储最小生成树中的边的权重for (auto& e : minTree._matrix) // 将邻接矩阵的所有元素初始化为最大权重值MAX_W{e.resize(_vertex.size(), MAX_W);}// 创建一个优先级队列，用于存储边的信息priority_queue<Edge, vector<Edge>, greater<Edge>> pq;// 将所有边（除了自环和重复边）加入优先级队列for (size_t i = 0; i < _vertex.size(); i++) {for (size_t j = 0; j < _vertex.size(); j++) {if (i < j && _matrix[i][j] != MAX_W) // 确保不加入自环和重复边{pq.push(Edge(i, j, _matrix[i][j])); // 将边加入优先级队列}}}// 初始化变量，用于记录最小生成树的总权重和边的数量W total = W();int size = 0;UnionFindSet ufs(_vertex.size()); // 创建并查集，用于判断顶点是否已经连接while (!pq.empty()) // 当优先级队列非空时{Edge min = pq.top(); // 取出权重最小的边pq.pop(); // 移除已取出的边// 判断边的两个顶点是否已经在同一集合内（即是否已经连接）if (!ufs.InSet(min._srci, min._desi)) {cout << _vertex[min._srci] << "-" << _vertex[min._desi] << ":" << _matrix[min._srci][min._desi] << endl; // 打印边的信息minTree._AddEdge(min._srci, min._desi, min._w); // 将边加入最小生成树total += min._w; // 更新最小生成树的总权重ufs.Union(min._srci, min._desi); // 合并两个顶点所在的集合++size; // 增加边的数量}}cout << endl;minTree.Print(); // 打印最小生成树// 如果边的数量等于顶点数量减一，则返回最小生成树的总权重if (size == _vertex.size() - 1){return total;}else{return W(); // 否则返回默认权重值（可能表示无法形成最小生成树）}
}

我们可以来测试一下：

	void TestGraph2(){string a[] = {"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));g1.AddEdge("小潮", "小傲", 30);g1.AddEdge("小潮", "高斯", 83);g1.AddEdge("小潮", "海皇", 34);g1.AddEdge("胖迪", "海皇", 78);g1.AddEdge("胖迪", "小傲", 76);g1.AddEdge("小杨", "皖皖", 54);g1.AddEdge("小杨", "高斯", 48);g1.Print();cout << endl;Graph<string, int, INT_MAX, false> kminTree;cout << "Kruskal:" << g1.Kruskal(kminTree) << endl;}

在这里插入图片描述按照Kruskal算法，构建出来的图是这样的：
在这里插入图片描述胖迪和海皇的关系被抹除了，其实我们之前的图里有环：
在这里插入图片描述

Kruskal算法的时间复杂度主要取决于排序边的操作和并查集的效率。在最好的情况下，排序边的时间复杂度为O(E log E)，其中E是边的数量；并查集操作的时间复杂度接近常数，因此整个算法的时间复杂度近似为O(E log E)。由于排序的主导作用，该算法适用于边的数量远小于顶点数量平方的图，即稀疏图。

Prim算法

Prim算法和上面的思想差不多，但是，Prim算法会从一个顶点开始，这里我假设是从"小潮"开始：
在这里插入图片描述
跟小潮连接的3条边，会进入优先级队列，维护起来：
在这里插入图片描述接下来，会选择30的权重来构造，然后30这条边的另一边的小傲的边入优先级队列：
在这里插入图片描述
以此类推：

// 使用Prim算法构建并返回最小生成树的总权重
W Prim(Self& minTree, const V& vertex) // Self应该是当前类的引用，minTree是用于存储最小生成树的实例，vertex是顶点的容器
{// 初始化最小生成树的顶点集和索引minTree._vertex = _vertex;minTree._index = _index;minTree._matrix.resize(_vertex.size()); // 创建一个邻接矩阵，用于存储最小生成树中的边的权重// 初始化邻接矩阵的所有元素为最大权重值MAX_Wfor (auto& e : minTree._matrix){e.resize(_vertex.size(), MAX_W);}// 区分顶点集合：已选择和未选择size_t srcIndex = FindSrci(vertex); // 找到起始顶点的索引vector<bool> select(_vertex.size(), false); // 已选择顶点集合，初始时所有顶点都未选择vector<bool> non_select(_vertex.size(), true); // 未选择顶点集合，初始时所有顶点都未被选择select[srcIndex] = true; // 起始顶点被标记为已选择non_select[srcIndex] = false; // 起始顶点从未选择集合中移除// 创建一个优先级队列，用于存储待处理的边priority_queue<Edge, vector<Edge>, greater<Edge>> pq; // 边按权重从小到大排序// 将起始顶点的邻接边加入优先级队列for (int i = 0; i < _vertex.size(); i++){if (_matrix[srcIndex][i] != MAX_W) // 如果存在边，且不是最大权重（表示边存在）{pq.push(Edge(srcIndex, i, _matrix[srcIndex][i])); // 加入边信息到优先级队列}}// 初始化计数器和总权重size_t size = 0;W total = W(); // 初始化总权重为0// 当优先级队列非空时while (!pq.empty()){Edge min = pq.top(); // 获取当前权重最小的边pq.pop(); // 从队列中移除已处理的边// 如果目标顶点已被选择，跳过这条边if (select[min._desi]) continue;// 输出边的信息cout << _vertex[min._srci] << "-" << _vertex[min._desi] << ":" << _matrix[min._srci][min._desi] << endl;// 添加边到最小生成树minTree._AddEdge(min._srci, min._desi, min._w);// 标记目标顶点为已选择select[min._desi] = true;non_select[min._desi] = false;++size; // 已处理的边数量加1total += min._w; // 更新总权重// 将新加入顶点的邻接边加入优先级队列for (size_t i = 0; i < _vertex.size(); i++){if (_matrix[min._desi][i] != MAX_W && non_select[i]) // 如果存在边且目标顶点未被选择{pq.push(Edge(min._desi, i, _matrix[min._desi][i])); // 加入边信息到优先级队列}}}// 打印最小生成树minTree.Print();// 如果边的数量等于顶点数量减一，则返回最小生成树的总权重if (size == _vertex.size() - 1){return total;}else{return W(); // 否则返回默认权重值（可能表示无法形成最小生成树）}
}

	void TestGraph2(){string a[] = {"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));g1.AddEdge("小潮", "小傲", 30);g1.AddEdge("小潮", "高斯", 83);g1.AddEdge("小潮", "海皇", 34);g1.AddEdge("胖迪", "海皇", 78);g1.AddEdge("胖迪", "小傲", 76);g1.AddEdge("小杨", "皖皖", 54);g1.AddEdge("小杨", "高斯", 48);g1.Print();cout << endl;Graph<string, int, INT_MAX, false> kminTree;cout << "Kruskal:" << g1.Kruskal(kminTree) << endl;cout << endl;Graph<string, int, INT_MAX, false> pminTree;cout << "Prim:" << g1.Prim(pminTree,"小潮") << endl;}

在这里插入图片描述

Prim算法同样是用于寻找加权无向图的最小生成树(Minimum Spanning Tree, MST)的一种贪心算法。与Kruskal算法不同的是，Prim算法从一个顶点开始，逐步添加最短的边来扩展树，直到包含所有的顶点。

Prim算法基本步骤：

  1. 选择任意一个顶点作为起始顶点。
  2. 在当前树的顶点的邻接边中找到权重最小的边，将这条边添加到树中，并将新的顶点也添加进来。
  3. 重复步骤2，直到树包含所有的顶点。

这是两种算法挑选边的过程和最后结果，大家可以类比对比：

		//Kruskal算法W Kruskal(Self& minTree){//初始化minTree._vertex = _vertex;minTree._index = _index;minTree._matrix.resize(_vertex.size());for (auto& e : minTree._matrix){e.resize(_vertex.size(), MAX_W);}//优先级队列priority_queue<Edge, vector<Edge>, greater<Edge>> pq;for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){if (i < j && _matrix[i][j] != MAX_W){pq.push(Edge(i, j, _matrix[i][j]));}}}//拿边构造最小生成树W totoal = W();int size = 0;UnionFindSet ufs(_vertex.size());while (!pq.empty()){Edge min = pq.top();//出边pq.pop();//判断是否在同一集合if (!ufs.InSet(min._srci ,min._desi)){cout << _vertex[min._srci] << "-" << _vertex[min._desi] <<":" << _matrix[min._srci][min._desi] << endl;minTree._AddEdge(min._srci, min._desi, min._w);totoal += min._w;//合并ufs.Union(min._srci, min._desi);++size;}}cout << endl;minTree.Print();if (size == _vertex.size() - 1){return totoal;}else{return W();}}W Prim(Self& minTree,const V& vertex){//初始化minTree._vertex = _vertex;minTree._index = _index;minTree._matrix.resize(_vertex.size());for (auto& e : minTree._matrix){e.resize(_vertex.size(), MAX_W);}//区分集合size_t srcIndex = FindSrci(vertex);vector<bool> select(_vertex.size(), false);vector<bool> non_select(_vertex.size(), true);select[srcIndex] = true;non_select[srcIndex] = false;//开始入边priority_queue<Edge, vector<Edge>, greater<Edge>> pq;for (int i = 0; i < _vertex.size(); i++){if (_matrix[srcIndex][i] != MAX_W){pq.push(Edge(srcIndex, i, _matrix[srcIndex][i]));}}size_t size = 0;W totoal = W();while (!pq.empty()){Edge min = pq.top();pq.pop();if (select[min._desi])continue;cout << _vertex[min._srci] << "-" << _vertex[min._desi] <<":" << _matrix[min._srci][min._desi] << endl;minTree._AddEdge(min._srci, min._desi, min._w);select[min._desi] = true;non_select[min._desi] = false;++size;totoal += min._w;//新入的顶点的边也加入到优先级队列for (size_t i = 0; i < _vertex.size(); i++){if (_matrix[min._desi][i] != MAX_W && non_select[i]){pq.push(Edge(min._desi, i, _matrix[min._desi][i]));}}}minTree.Print();if (size == _vertex.size() - 1){return totoal;}else{return W();}}

在这里插入图片描述


http://www.ppmy.cn/news/1473472.html

相关文章

使用echarts绘制中国地图根据不同的省份划分到指定区域里面中

使用echarts绘制中国地图根据不同的省份划分到指定区域里面中

需求&#xff1a;我们在开发过程中会遇到使用中国地图来划分不同区域省份下面的数量统计情况&#xff0c;但是有时候使用Echarts里面地图功能和我们实际业务需求不匹配的&#xff0c;这个时候就需要我们手动自定义进行划分不同区域下面的省份数据。例如大区1下面有哪些省份&…
阅读更多...
生产力工具|viso常用常见科学素材包

生产力工具|viso常用常见科学素材包

一、科学插图素材网站 一图胜千言&#xff0c;想要使自己的论文或重要汇报更加引人入胜&#xff1f;不妨考虑利用各类示意图和科学插图来辅助研究工作。特别是对于新手或者繁忙的科研人员而言&#xff0c;利用免费的在线科学插图素材库&#xff0c;能够极大地节省时间和精力。 …
阅读更多...
SpringBoot中整合ONLYOFFICE在线编辑

SpringBoot中整合ONLYOFFICE在线编辑

SpringBoot整合OnlyOffice SpringBoot整合OnlyOffice实现在线编辑1. 搭建私有的OnlyOffice的服务2. SpringBoot进行交互2.1 环境2.2 我们的流程2.3 接口规划2.3.1 获取编辑器配置的接口2.3.2 文件下载地址2.3.3 文件下载地址 3. 总结4. 注意4.1 你的项目的地址一定一定要和only…
阅读更多...
【国产开源可视化引擎Meta2d.js】钢笔

【国产开源可视化引擎Meta2d.js】钢笔

钢笔 钢笔是和其他众多绘图工具&#xff08;Photoshop、Sketch、Illustrator&#xff09;中一致的钢笔工具&#xff0c;能够很方便的在线绘制各种小图标 在线体验&#xff1a; 乐吾乐2D可视化 示例&#xff1a; // 开始绘画&#xff1a;curve。除了curve&#xff0c;还有poly…
阅读更多...
CASS如何输入距离和坐标绘制图形

CASS如何输入距离和坐标绘制图形

1、软件版本 这里使用CASS7.0软件进行操作。如下&#xff1a; 2、 操作 输入&#xff1a;500,45【表示距离500米&#xff0c;方向45度】。 点击回车&#xff0c;完成绘制。
阅读更多...
万界星空科技MES系统中的排版排产功能

万界星空科技MES系统中的排版排产功能

在当今高度竞争的市场环境中&#xff0c;企业对于生产管理的效率和质量要求日益提高。作为智能制造的重要组成部分&#xff0c;制造执行系统&#xff08;MES&#xff09;以其强大的功能&#xff0c;在提升企业生产能力方面发挥着不可替代的作用。万界星空科技作为行业领先的智能…
阅读更多...
PCA和PCoA分析的python代码

PCA和PCoA分析的python代码

主成分分析&#xff08;PCA&#xff09;和主坐标分析&#xff08;PCoA&#xff09;都是数据降维和可视化的常用方法&#xff0c;但它们在适用场景和计算方法上有一些重要区别。 主成分分析&#xff08;PCA&#xff09; 定义: PCA是一种线性降维方法&#xff0c;通过正交变换将…
阅读更多...
electron通信与持久化存储

electron通信与持久化存储

electron通信 主进程与渲染进程的通信方式 IPC (Inter-Process Communication) 通信&#xff1a; 使用 ipcMain 和 ipcRenderer 模块进行通信。 ipcMain 用于在主进程中接收和处理消息。 ipcRenderer 用于在渲染进程中发送消息。 使用 contextBridge 和 preload 脚本&#…
阅读更多...
最新文章

Copyright @ 2022~2023