最小生成树—Kruskal算法和Prim算法

这篇具有很好参考价值的文章主要介绍了最小生成树—Kruskal算法和Prim算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.最小生成树

连通图:在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中任
意一对顶点都是连通的,则称此图为连通图。

生成树:一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点
和n-1条边。

最小生成树:构成生成树的这些边加起来权值最小的

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

若连通图由n个顶点组成,则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三
条:
        1. 只能使用图中权值最小的边来构造最小生成树
        2. 只能使用恰好n-1条边来连接图中的n个顶点
        3. 选用的n-1条边不能构成回路

构造最小生成树的方法:Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。
贪心算法:是指在问题求解时,总是做出当前看起来最好的选择。也就是说贪心算法做出的不是
整体
最优的的选择,而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。

2.Kruskal算法

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

最小生成树—Kruskal算法和Prim算法

实现思路:借助优先级队列将每一条权值按照从小到大的顺序存储起来,依次取出优先级队列中的值,判断当前边做为最小生成树的边是否构成回路,如果构成构成回路则采用并查集进行排除。

3.Prim算法

最小生成树—Kruskal算法和Prim算法

实现思路:给一个源点,借助两个vector数组X和Y,从X中加入源点,然后在Y中选择权值最小的边添加到优先级队列中,然后依次去除优先级队列中的值,如果最小边的目标点也在X集合中,就说明构成环了,否则该边就是最小边,进行添加边,然后更新X数组和Y数组继续选边文章来源地址https://www.toymoban.com/news/detail-452305.html

4.代码实现

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<queue>
#include<functional>
using namespace std;

namespace matrix
{
	class UnionFindSet
	{
	public:
		UnionFindSet(size_t size)
			: _ufs(size, -1) {}
		int FindRoot(size_t index)
		{
			while (_ufs[index] >= 0)
			{
				index = _ufs[index];
			}
			return index;
		}
		bool Union(int x1, int x2)
		{
			int root1 = FindRoot(x1);
			int root2 = FindRoot(x2);
			if (root1 == root2)
				return false;
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
			return true;
		}
		bool InSet(int x1, int x2)
		{
			return FindRoot(x1) == FindRoot(x2);
		}
		int Count()
		{
			int count = 0;
			for (auto& e : _ufs)
			{
				if (e < 0)
					count++;
			}
			return count;
		}
	private:
		vector<int> _ufs;
	};
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V,W, MAX_W, Direction> self;
	public:
		Graph() = default;
		Graph(const V* vertexs, size_t n)
		{
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				_vertexs.push_back(vertexs[i]);
				_indexMap[vertexs[i]] = i;
			}
			_matrix.resize(n);
			for (auto& e : _matrix)
			{
				e.resize(n, MAX_W);
			}
		}
		void _addEdge(size_t srci, size_t dsti, const W& w)
		{
			_matrix[srci][dsti] = w;
			if (Direction == false)
				_matrix[dsti][srci] = w;
		}
		size_t GetVertexIndex(const V& v)
		{
			auto ret = _indexMap.find(v);
			if (ret != _indexMap.end())
				return ret->second;
			else
				return -1;
		}
		//添加边:
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			_addEdge(srci, dsti, w);
		}
		void Print()
		{
			//打印顶点和下标的映射关系
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				cout << _vertexs[i] << "-" << i << " ";
			}
			cout << endl;
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				if (i == 0)
					cout << "  ";
				cout << i << " ";
			}
			cout << endl;
			//打印矩阵:
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				cout << i << " ";
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (_matrix[i][j] != INT_MAX)
						cout << _matrix[i][j] << " ";
					else
						cout << "*" << " ";
				}
				cout << endl;
			}
			cout << endl;
			//打印所有的边:
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (_matrix[i][j] != INT_MAX)
						cout << _vertexs[i] << "-" << _vertexs[j] << ":" << _matrix[i][j] << endl;
				}
			}
		}
		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._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (int i = 0; i < n; i++)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					//i < j 避免相同的边加入两次
					if (i < j && _matrix[i][j] != MAX_W)
					{
						minq.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}
			//选出n-1条边:
			int size = 0;
			W totalw = W();
			UnionFindSet ufs(n);
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();
				if (!ufs.InSet(min._srci, min._dsti))
				{
					minTree._addEdge(min._srci, min._dsti,min._w);
					ufs.Union(min._srci, min._dsti);
					++size;
					totalw += min._w;
				}
			}
			if (size == n - 1)
				return totalw;
			else
				return W();
		}
		W Prim(self& minTree, const W& src)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();
			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (int i = 0; i < n; i++)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}
			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;
			Y[srci] = false;
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			for (size_t i = 0; i < n; i++)
			{
				if (_matrix[srci][i] != MAX_W)
					minq.push(Edge(srci, i, _matrix[srci][i]));
			}
			size_t size = 0;
			W totalw = W();
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();
				//最小边的目标点也在X集合则构成环
				if (X[min._dsti])
				{
					cout << "构成环:";
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
				else
				{
					//添加边:
					minTree._addEdge(min._srci, min._dsti, min._w);
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					X[min._dsti] = true;
					Y[min._dsti] = false;
					++size;
					totalw += min._w;
					if (size == n - 1)
						break;
					for (size_t i = 0; i < n; i++)
					{
						if (_matrix[min._dsti][i] != MAX_W && Y[i])
							minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
					}
				}
			}
			if (size == n - 1)
				return totalw;
			return W();
		}
	private:
		vector<V> _vertexs; //存储顶点的集合
		vector<vector<W>> _matrix; //存储边集合的矩阵
		map<V, int> _indexMap;//顶点映射下标
	};
	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('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;
		cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
		kminTree.Print();
		Graph<char, int> pminTree;
		cout << "Prim:" << g.Prim(pminTree,'a') << endl;
		pminTree.Print();
	}
}
int main()
{
	matrix::TestGraphMinTree();
	return 0;
}

到了这里,关于最小生成树—Kruskal算法和Prim算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论13-最小生成树-Kruskal算法+Prim算法

    基本思想:按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路 具体做法:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中 不产生 回路,直至森林变成一棵树为止。 2.2.1 如果图不联通,直接返回空,该

    2024年02月01日
    浏览(50)
  • 最小生成树Kruskal、Prim算法C++

    连通图: 在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1和顶点v2是连通的。如果图中任意一对顶点都是连通的,则称此图为连通图。 生成树: 一个连通图的最小连通子图称作为图的生成树。有 n个顶点 的连通图的生成树有 n个顶点和 n-1 条边。 最小生成树: 最小生活

    2024年02月10日
    浏览(41)
  • 【最小生成树】一文学懂prim、kruskal算法

    博主简介: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: 算法 ;该专栏专注于蓝桥杯和ACM等算法竞赛🔥 近期目标: 写好专栏的每一篇文章 首先,我们要了解什么是最小生

    2023年04月25日
    浏览(32)
  • 用prim和kruskal算法求最小生成树问题

    题目 http://ybt.ssoier.cn:8088/problem_show.php?pid=1350 信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn) http://ybt.ssoier.cn:8088/problem_show.php?pid=1391 相当于一个图中求最小生成树的问题 prim解决 kruskal解法 信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn) http://ybt.ssoier.cn:8088/problem_show.ph

    2024年02月09日
    浏览(38)
  • C语言实现最小生成树算法:Prim和Kruskal

    以下是使用C语言实现Prim算法生成最小生成树的代码: 注释如下: #include stdio.h 和 `#include #define V 5 定义了图中顶点的个数为5。 int minDistance(int dist[], int visited[]) 函数用于找到顶点集合中未访问的顶点中距离最小的顶点。输入参数 dist 用于存储顶点到最小生成树的距离,输入

    2024年02月03日
    浏览(42)
  • 【数据结构】无向图的最小生成树(Prime,Kruskal算法)

    连通图 :在 无向图 中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中 任意一对顶点都是连通的 ,则称此图为连通图 强连通图 :在 有向图 中,若在每一对顶点vi和vj之间都存在一条从vi到vj的路径,也存在一条从vj到vi的路径,则称此图是强连通图 生成

    2024年01月24日
    浏览(48)
  • 【算法基础:搜索与图论】3.5 求最小生成树算法(Prim&Kruskal)

    最小生成树 有关树的定义 生成子图 :生成子图是从原图中选取部分节点以及这些节点之间的边所组成的图。生成子图中的所有节点和边都必须在原图中存在。 生成树 :一个连通 无向图 的 生成子图 ,同时要求是树。也即在图的边集中选择 n - 1 条,将所有顶点连通。 我们

    2024年02月16日
    浏览(40)
  • 求无向图的最小生成树——Kruskal算法(超详细)【并查集,python实现】

    以如下无向图为例,求最小生成树及其权值。 补充知识点: 最小生成树(不官方的解释):包含所有节点,保持整个图连通,所有边权值之和最小。 1、补充在前 (1)图的存储 采用二维列表存储(点,点,边的权值) (2)顶点转换 为了便于计算,将字母A ~ G用数字0 ~ 6代

    2024年02月04日
    浏览(45)
  • 求最小生成树Prim(普里姆)和Kruskal(克鲁斯卡尔)算法

     想求最小生成树,我们首先得弄懂以下几个概念   连通图 :图中任意两个顶点都是连通的 极小连通子图 :既要保持图连通又要使得边数最少的子图 生成树 : 包含图中全部顶点的一个极小连通子图 连通图用通俗的话来讲就是,某一个顶点,可以 直接或者间接 (通过其他顶点

    2024年02月05日
    浏览(45)
  • 【数据结构与算法】最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

      🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 一、最小生成树的概念 二、最小生成树的求解方法 三、练习题 四、最小生成树在实际应用中的例子 最近非科班的同学学到了最小生成树并询问我,于是想趁

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包