C++使用Kruskal和Prim算法实现最小生成树
更新时间:2020年4月25日 17:26 点击:1202
很久以前就学过最小生成树之Kruskal和Prim算法,这两个算法很容易理解,但实现起来并不那么容易。最近学习了并查集算法,得知并查集可以用于实现上述两个算法后,我自己动手实现了最小生成树算法。
宏观上讲,Kruskal算法就是一个合并的过程,而Prim算法是一个吞并的过程,另外在Prim算法中还用到了一种数据结构——优先级队列,用于动态排序。由于这两个算法很容易理解,在此不再赘述。接下来给出我的源代码。
输入
第一行包含两个整数n和m,n表示图中结点个数,m表示图中边的条数;接下来m行,每一行包含三个整数u,v,w,表示途中存在一条边(u,v),并且其权重为w;为了便于调试,我的程序是从文件中输入数据的;
输出
输出程序选择的最小生成树的权值之和以及每一条边信息;
Kruskal算法:
#include <iostream> #include <vector> #include <algorithm> #include <fstream> using namespace std; struct Edge { int u; //边连接的一个顶点编号 int v; //边连接另一个顶点编号 int w; //边的权值 friend bool operator<(const Edge& E1, const Edge& E2) { return E1.w < E2.w; } }; //创建并查集 void MakeSet(vector<int>& uset, int n) { uset.assign(n, 0); for (int i = 0; i < n; i++) uset[i] = i; } //查找当前元素所在集合的代表元 int FindSet(vector<int>& uset, int u) { int i = u; while (uset[i] != i) i = uset[i]; return i; } void Kruskal(const vector<Edge>& edges, int n) { vector<int> uset; vector<Edge> SpanTree; int Cost = 0, e1, e2; MakeSet(uset, n); for (int i = 0; i < edges.size(); i++) //按权值从小到大的顺序取边 { e1 = FindSet(uset, edges[i].u); e2 = FindSet(uset, edges[i].v); if (e1 != e2) //若当前边连接的两个结点在不同集合中,选取该边并合并这两个集合 { SpanTree.push_back(edges[i]); Cost += edges[i].w; uset[e1] = e2; //合并当前边连接的两个顶点所在集合 } } cout << "Result:\n"; cout << "Cost: " << Cost << endl; cout << "Edges:\n"; for (int j = 0; j < SpanTree.size(); j++) cout << SpanTree[j].u << " " << SpanTree[j].v << " " << SpanTree[j].w << endl; cout << endl; } int main() { ifstream in("data.txt"); int n, m; in >> n >> m; vector<Edge> edges; edges.assign(m, Edge()); for (int i = 0; i < m; i++) in >> edges[i].u >> edges[i].v >> edges[i].w; sort(edges.begin(), edges.end()); //排序之后,可以以边权值从小到大的顺序选取边 Kruskal(edges, n); in.close(); system("pause"); return 0; }
Prim算法:
#include <iostream> #include <fstream> #include <vector> #include <list> #include <queue> using namespace std; struct Node { int v; int w; Node(int a, int b) :v(a), w(b){} }; struct Edge { int u; int v; int w; Edge(int a, int b, int c) :u(a), v(b), w(c){} friend bool operator<(const Edge& E1, const Edge& E2) { return E1.w>E2.w; } }; int n, m; vector<list<Node>> Adj; priority_queue<Edge> Q; int FindSet(vector<int>& uset, int v) { int i = v; while (i != uset[i]) i = uset[i]; return i; } void Prim() { int Cost = 0; //用于统计最小生成树的权值之和 vector<Edge> SpanTree; //用于保存最小生成树的边 vector<int> uset(n,0); //用数组来实现并查集 Edge E(0, 0, 0); for (int i = 0; i < n; i++) uset[i] = i; //并查集初始化 for (auto it = Adj[0].begin(); it != Adj[0].end(); it++) Q.push(Edge(0, it->v, it->w)); //根据Prim算法,开始时选取结点0,并将结点0与剩余部分的边保存在优先队列中 //循环中每次选取优先队列中权值最小的边,并更新优先队列 while (!Q.empty()) { E = Q.top(); Q.pop(); if (0 != FindSet(uset, E.v)) { Cost += E.w; SpanTree.push_back(E); uset[E.v] = E.u; for (auto it = Adj[E.v].begin(); it != Adj[E.v].end(); it++) if (0 != FindSet(uset, it->v)) Q.push(Edge(E.v, it->v, it->w)); } } cout << "Result:\n"; cout << "Cost: " << Cost << endl; cout << "Edges:\n"; for (int j = 0; j < SpanTree.size(); j++) cout << SpanTree[j].u << " " << SpanTree[j].v << " " << SpanTree[j].w << endl; cout << endl; } int main() { ifstream in("data.txt"); int u, v, w; in >> n >> m; Adj.assign(n, list<Node>()); for (int i = 0; i < m; i++) { in >> u >> v >> w; Adj[u].push_back(Node(v,w)); Adj[v].push_back(Node(u,w)); } Prim(); in.close(); system("pause"); return 0; }
就实现而言,Kruskal算法比Prim算法更容易,代码更易于理解。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
上一篇: C语言实现数独游戏的求解
下一篇: C语言实现车辆出租管理系统
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 在本篇内容里小编给大家分享了关于C++实现递归函数的教学步骤,需要的朋友跟着参考下。...2020-04-25