【数据结构】无向图的最小生成树（Prime，Kruskal算法）

---

前言

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

强连通图：在有向图中，若在每一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj到vi的路径，则称此图是强连通图

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

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

一、最小生成树

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

1. 只能使用图中的边来构造最小生成树
2. 只能使用恰好n-1条边来连接图中的n个顶点
3. 选用的n-1条边不能构成回路

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

二、Kruskal算法

里面涉及一些图的代码，不了解的可以参考之前我写的【数据结构】图的创建（邻接矩阵，邻接表）以及深度广度遍历（BFS,DFS）

1.方法：

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

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

2.判断是否成环

我们要保证不能成环需要保证选入某条边之前，这条边两个顶点本身就不连通，换种说法就是两个顶点没有公共的顶点或者不在同一个集合当中，这个时候我们就可以考虑之前学的并查集的知识来解决了，并查集就是解决两个元素的联合与判断是否在一个结合中的数据结构。

不知道小伙伴可以去看看之前我写的【数据结构】并查集的简单实现，合并，查找（C++）

3.代码实现

typedef Graph<V, W, MAX_W, false> Self;

		//建立边的类，保存边的两个顶点下标和权值
		struct Edge {
			size_t _srci;
			size_t _dsti;
			W _w;

			Edge(size_t srci,size_t dsti,W w)
				:_srci(srci),
				_dsti(dsti),
				_w(w)
			{}

			bool operator>(const Edge& e)const {
				return _w > e._w;//小根堆判断
			}

		};

		W Kruskal(Self& minTree)
		{
			//minTree为最小生成树，刚开始什么都没有
			size_t n = _vertexs.size();

			//初始化最小生成树
			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}


			//我们每次选边从全部边中选出最小的（保证不构成回路的情况）
			//所以我们可以考虑用小根堆来存入边，这样每次方便找最小的
			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						//将所有有效值边放进堆中
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}

			 
			int size = 0;
			W totalW = W();
			UnionFindSet ufs(n); 

			// 选出n-1条边
			while (!minque.empty())
			{
				//取出最小边
				Edge min = minque.top();
				minque.pop();

				if (!ufs.InSet(min._srci, min._dsti))//判断是否成环
				{
				
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] <<":"<<min._w << endl;
					//不成环就将当前边放入最小生成树当中
					    
					minTree._AddEdge(min._srci, min._dsti, min._w);
					//并把这两个顶点放入同一个并查集集合当中
					ufs.Union(min._srci, min._dsti);
					++size;
					totalW += min._w;//权值总和增加
				}
				else
				{
					//cout << "构成环：";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
				 
			}

			if (size == n - 1)//边数选够说明最小生成树
				//创建成功
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

三、 Prim算法

1.方法：

Prim算法采用的局部贪心的策略，从当前选入的局部的点中选取最小的边

Prim算法的优点在于他不会构成环，他是以顶点为单位进行筛选，X表示已经选入的点，Y中存的未选入的点，X从Y中选顶点加入到X中，然后Y删除这个顶点，（若X中出现两个相同顶点则构成环），但这种情况基本不大可能出现，因为我们每次都是从Y中选，都是X中没有的顶点

2.代码

typedef Graph<V, W, MAX_W, false> Self;

		//建立边的类，保存边的两个顶点下标和权值
		struct Edge {
			size_t _srci;
			size_t _dsti;
			W _w;

			Edge(size_t srci,size_t dsti,W w)
				:_srci(srci),
				_dsti(dsti),
				_w(w)
			{}

			bool operator>(const Edge& e)const {
				return _w > e._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 (size_t 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;

			 
			// 从X->Y集合中连接的边里面选出最小的边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;

			// 先把srci连接的边添加到小根堆中
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			cout << "Prim开始选边" << endl;
			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
				{
					//从Y中选出顶点
					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;
			}
			else
			{
				return W();
			}

四、源码

namespace matrix {
	//V为顶点类型，W为边权值类型，MAX_W为权值最大值也就是无效值
	//Direction用来判断是不是有向图，false为无向图
	template<class V,class W,W  MAX_W=INT_MAX,bool Direction=false>
	class Graph {
	public:
		Graph() = default;
		Graph(const V* a, size_t n) {
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; i++) {
				_vertexs.push_back(a[i]);
				_indexMap[a[i]] = i;
				//将顶点存入_vertexs，下标映射存进map
			}

			_matrix.resize(n);
			for (size_t i = 0; i < _matrix.size(); i++) {
				_matrix[i].resize(n, MAX_W);
				//邻接矩阵默认初始值为无效值
			}
		}

		size_t GetVertexIndex(const V& v) {
			//获得对应顶点在数组中的下标
			auto it = _indexMap.find(v);
			if (it != _indexMap.end()) {
				return it->second;
				//有这个顶点返回其下标
			}
			else {
				throw("顶点不存在");
				return -1;
			}
		}

		void _AddEdge(size_t srci, size_t dsti, const W& w) {
			//存入权值
			_matrix[srci][dsti] = w;
			if (Direction == false) {
				_matrix[dsti][srci] = w;
				//无向图要两个方向都存
			}
		}

		void AddEdge(const V& src, const V& dst, const W& w) {
			//添加边与顶点的关系。从src到dst方向的关系
			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 << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}//打印顶点集
			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] == MAX_W) {
						printf("%4c", '*');
					}
					else {
						printf("%4d", _matrix[i][j]);
					}
				}
				cout << endl;
			 }
		}

	 
	 


		void BFS(const V& src) {
			size_t srci = GetVertexIndex(src);
			queue<int>q;
			q.push(srci);
			vector<bool>visited(_vertexs.size(), false);
			visited[srci] = true;//标记这个顶点被访问过了
			int levelSize = 1;
			while (!q.empty()) {
				//levelSize为当前层的大小
				for (size_t i = 0; i < levelSize; i++) {
					int front = q.front();
					q.pop();
					cout << front << ":" << _vertexs[front]<<" ";

					for (size_t i = 0; i < _vertexs.size(); i++) {
						if (_matrix[front][i] != MAX_W && visited[i] == false) {
							q.push(i);
							visited[i] = true;//标记这个顶点被访问过了
						}
					}
				}
				levelSize = q.size();//更新当前层的数量
				cout << endl;
			}
			cout << endl;
		}


		void _DFS(size_t srci, vector<bool>& visited) {
			cout << srci << ":" << _vertexs[srci] << endl;
			visited[srci] = true;//标记这个顶点被访问过了
			for (size_t i = 0; i < _vertexs.size(); i++) {
				if (_matrix[srci][i] != MAX_W && visited[i] == false) {
					_DFS(i, visited);
				}
			}
		}

		void DFS(const V& src) {
			size_t srci = GetVertexIndex(src);
			vector<bool>visited(_vertexs.size(), false);

			_DFS(srci, visited);
		}


 

	 
		 
		
		
		 

		typedef Graph<V, W, MAX_W, false> Self;

		//建立边的类，保存边的两个顶点下标和权值
		struct Edge {
			size_t _srci;
			size_t _dsti;
			W _w;

			Edge(size_t srci,size_t dsti,W w)
				:_srci(srci),
				_dsti(dsti),
				_w(w)
			{}

			bool operator>(const Edge& e)const {
				return _w > e._w;//小根堆判断
			}

		};

		W Kruskal(Self& minTree)
		{
			//minTree为最小生成树，刚开始什么都没有
			size_t n = _vertexs.size();

			//初始化最小生成树
			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}


			//我们每次选边从全部边中选出最小的（保证不构成回路的情况）
			//所以我们可以考虑用小根堆来存入边，这样每次方便找最小的
			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						//将所有有效值边放进堆中
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}

			 
			int size = 0;
			W totalW = W();
			UnionFindSet ufs(n); 

			// 选出n-1条边
			while (!minque.empty())
			{
				//取出最小边
				Edge min = minque.top();
				minque.pop();

				if (!ufs.InSet(min._srci, min._dsti))//判断是否成环
				{
				
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] <<":"<<min._w << endl;
					//不成环就将当前边放入最小生成树当中
					    
					minTree._AddEdge(min._srci, min._dsti, min._w);
					//并把这两个顶点放入同一个并查集集合当中
					ufs.Union(min._srci, min._dsti);
					++size;
					totalW += min._w;//权值总和增加
				}
				else
				{
					//cout << "构成环：";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
				 
			}

			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 (size_t 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;

			 
			// 从X->Y集合中连接的边里面选出最小的边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;

			// 先把srci连接的边添加到小根堆中
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			cout << "Prim开始选边" << endl;
			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
				{
					//从Y中选出顶点
					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;
			}
			else
			{
				return W();
			}
		}

	private:
		vector<V>_vertexs;//顶点集合
		map<V, int>_indexMap;//存顶点与数组下标的映射关系
		vector<vector<W>>_matrix;//邻接矩阵
	};



 }