目录

1.最小生成树

1.1 Kruskal算法

代码部分

1.2 Prim算法

代码部分

---

1.最小生成树

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

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

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

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

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

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

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

1.1 Kruskal算法

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

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

我用大白话来通俗的讲一下它的思路（结合上面的图）

        首先，我们要选择边最小的一条（按照贪心策略），所以我们选择了h，g两点所连成的边，其次我们找下一个最小的，我们发现有两条边的权值都为2，所以我们随便选择其中一条就行了，假设我们选i，c两点间的那条，接下来就选择g，f那条，以此类推，直到f图我们发现，它没有选权值为6的那条边，这是因为如果选了那条边，i根g就相连了，构成了回路就不满足我们的要求了（如何处理回路我们在代码讲解部分来解决）。以此类推直到所有边都处理完，我们的最小生成树就出来了。

代码部分

边的类

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 (size_t i = 0; i < n; i++)
			{
				minTree._matrix[i].resize(n);
			}
			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]));
					}
				}
			}

			//选出n-1条边
			int size = 0;
			W totalW = W();
			UnionFindSet<V> ufs(n);
			while (!minque.empty())
			{
				Edge min = minque.top();
				minque.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();
		}

这段代码就是我们的库鲁斯卡尔算法，我们来详细的分析它的逻辑。

        首先，我们的参数就是我们的图类型的空对象，我们要做的就是先对最小生成树对象进行构造，我们先获取图的顶点个数，并且把图的顶点数组和顶点与下标的映射关系都拷贝给最小生成树对象，并给最小生成树的邻接矩阵进行初始化的操作，接下来我们可以用优先队列来存边的值，这就节省了我们比对大小的时间，优先队列会按照greater的比对方式将我们插入的边从小到大进行排序。接下来我们就要遍历图的邻接矩阵，将边对象插入到我们的优先队列中。

       接下来就是我们的最小生成树生成的过程了，我们既然要选出n-1条边，那么有可能选不到n-1条，这种情况下我们的最小生成树就生成失败了，所以我们要来一个size记录选了多少条边来帮助我们进行判断，我们可以来一个totalw来记录最小生成树的边的权值的总和，接下来我们就需要使用一个循环来选边，我们循环的终止条件就是我们之前分析的只要将所有边都处理完就结束了，接下来我们可以使用我们之前写过的并查集，我们将最小的边的起点和终点进行判断，如果他们在一个集合中就说明之前已经有一条边使他们连接在一起了，此时这一条边就会构成回路，我们就舍弃这条边，倘若它们不在一个集合里，我们就将这条边添加到最小生成树里，并且给这两点连接成一组，再给我们的size和totalw进行增加操作就可以了。

        当所有的边都遍历完之后，如果size不是n-1，我们的最小生成树就生成失败了，我们就返回它的初始构造，倘若成功了，我们就返回它的权值之和。

测试用例

const char* str = "abcdefghi";
	matrix::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);
	matrix::Graph<char, int> kminTree;
	cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
	kminTree.Print();

运行截图：

1.2 Prim算法

我用通俗易懂的话来解释一遍，假设我们以a点为起点，那么a点就在A树这个集合里面，我们找A树中顶点的轻量级邻接边，此时只有一个a顶点，所以我们就找a的，所以我们就选出了a，b这条边，接下来把b也加入到A树里面，我们接下来就找a，b这两个顶点的轻量级邻接边，以此类推，并且注意不能构成回路，直到所有顶点都到A树里面，最小生成树就形成了。

代码部分

//Prim普利姆算法最小生成树
		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);
			}

			
			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]));
				}
			}

			size_t size = 0;
			W totalW = W();
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();

				//最小边的顶点也在X集合，构成环
				if (X[min._dsti])
				{
					//cout << "构成环" << endl;
					continue;
				}
				else
				{
					minTree._AddEdge(min._srci, min._dsti, min._w);
					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 && X[i] == false)
						{
							minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
						}
					}
				}
				
			}

			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

根库鲁斯卡尔算法一样，我们的形参还是需要最小生成树对象，除此之外我们还需要一个顶点作为起点。

        前段部分代码跟我们的库鲁斯卡尔算法是一样的，都要先给最小生成树对象进行初始化操作，根据我们之前的分析，我们接下来可以创建两个顺序表x，y。x存的是最小生成树中的节点，y存的是还没放到树中的节点，我们先对它们进行初始化，刚开始的顶点肯定都在y中，所以我们给x初始化成false，y为true，然后起点对应的位置做一下调整就可以了。

        我们还是可以选择优先队列来帮助我们找轻量级边。接下来我们的思路是先把起点的邻接边插入到队列中，然后开始我们的循环部分，我们的循环的思路就是，拿到轻量级的边，检查一下它的终点是不是在x中，在的话很明显就构成回路了，这条边我们也就不能用，如果不在我们就可以将边添加到最小生成树中，顶点添加到x集合中，同时还要将这个新加入的顶点的邻接边插入到队列中。最后当size=n-1时，我们可以提前退出循环了。

        我们会发现，库鲁斯卡尔算法和普利姆算法还是有相似之处的，都是采用贪心策略，只不过一个是从全局选择轻量级边，一个是局部选择。

测试用例

const char* str = "abcdefghi";
	matrix::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);
	/*matrix::Graph<char, int> kminTree;
	cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
	kminTree.Print();*/
	cout << "-------------------------" << endl;
	matrix::Graph<char, int> pminTree;
	cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
	pminTree.Print();

运行截图：

我们可以发现它们两个算法的最小生成树权值是一样的。