【数据结构】图的最小生成树

引言

前置知识：【数据结构】并查集
前置知识：【数据结构】图的概念和存储结构

一、最小生成树的概念

最小生成树（Minimum Spanning Tree, MST） 是图论中的一个重要概念，指的是在一个连通的无向图中，选择一部分边，使得这些边连接所有顶点且边权值之和最小，同时生成的子图仍是一个树结构（没有环）。

按照定义，若连通网络由n个顶点组成，则其生成树必含n个顶点，n-1条边。因此，构造最小生成树有3个准则：

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

下面讲解两种经典的最小生成树算法——kruskal算法和prim算法，它们都采用了贪心策略来进行实现。

前置声明：

template<class W>
struct Edge
{
	int _srci;
	int _dsti;
	W _w;

	Edge(int srci, int dsti, const W& w)
		: _srci(srci)
		, _dsti(dsti)
		, _w(w)
	{}

	bool operator>(const Edge& e) const
	{
		return _w > e._w;
	}
};

template<class V, class W, W W_MAX = INT_MAX, bool Direction = false>
class Graph
{
	typedef Edge<W> Edge;
	typedef Graph<V, W, W_MAX, Direction> Self;
	//...
}

二、Kruskal算法

2.1 思想

Kruskal算法采用全局贪心的策略：

1. 每次选取图中权值最小的边。
2. 每次选取完后，判断是否构成回路。若构成，则舍弃这条边。

具体图示如下：

2.2 实现

思路：

1. 采用优先级队列（小堆），将所有边存入，以便每次选取全图权值最小的边。
2. 采用并查集，存储已选取的顶点。每次选取边时，判断两侧顶点是否在并查集中，以此判断是否构成回路。

W Kruskal(Self& minTree)
{
	minTree._vertexs = _vertexs;
	minTree._indexMap = _indexMap;
	int n = _edges.size();
	minTree._edges.resize(n, vector<W>(n, W_MAX));

	priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (i < j && _edges[i][j] != W_MAX)//无向图，防止重复记录路径
			{
				minHeap.push(Edge(i, j, _edges[i][j]));
			}
		}
	}

	UnionFindSet<V> ufs(n);
	W total = W();
	int count = 0;
	while (!minHeap.empty())
	{
		Edge top = minHeap.top();
		minHeap.pop();

		int srci = top._srci, dsti = top._dsti;
		W w = top._w;
		if (!ufs.InSet(srci, dsti))
		{
			minTree._AddEdge(srci, dsti, w);
			ufs.Union(srci, dsti);
			total += w;
			++count;

			if (count == n - 1)
			{
				break;
			}

			cout << _vertexs[srci] << "--" << _vertexs[dsti] << ":" << w << endl;
		}
		else
		{
			cout << _vertexs[srci] << "--" << _vertexs[dsti] << ":" << w << "[构成环]" << endl;
		}
	}

	if (count == n - 1)
	{
		return total;
	}
	else
	{
		return W();
	}
}

细节：

1. 输入一个空图，输出最小生成树的总权值，并将空图变为最小生成树。
2. count记录已选边数，若达到n-1，则可直接跳出循环，提高效率。

三、Prim算法

3.1 思想

Prim算法采用局部贪心的策略：

1. 将已被选择的点看作一个顶点集合，初始状态只有起点在集合中。
2. 每次在集合周围查找，找到消耗权值最小即可抵达的点，并将其纳入集合。

具体图示如下：

3.2 实现

思路：

1. 采用优先级队列（小堆），将起始点周围的路径存入，以便每次选取集合周围权值最小的边。
2. 集合用bool数组表示，每次只有当目标点不在集合中，才将其纳入集合。
3. 每次将新点纳入集合后，再将新点周围的路径存入优先级队列，依次迭代。

W Prim(Self& minTree, const V& src)
{
	minTree._vertexs = _vertexs;
	minTree._indexMap = _indexMap;
	int n = _edges.size();
	minTree._edges.resize(n, vector<W>(n, W_MAX));

	//起始点周围的路径入堆
	priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;
	int srci = GetIndex(src);
	for (int i = 0; i < n; ++i)
	{
		if (_edges[srci][i] != W_MAX)
		{
			minHeap.push(Edge(srci, i, _edges[srci][i]));
		}
	}

	vector<bool> S(n, false);
	S[srci] = true;

	W total = W();
	int count = 0;
	while (!minHeap.empty())
	{
		Edge top = minHeap.top();
		minHeap.pop();

		int srci = top._srci, dsti = top._dsti;
		W w = top._w;
		if (!S[dsti])
		{
			minTree._AddEdge(srci, dsti, w);
			S[dsti] = true;
			total += w;
			++count;

			if (count == n - 1)
			{
				break;
			}

			for (int i = 0; i < n; ++i)
			{
				if (!S[i] && _edges[dsti][i] != W_MAX)//无向图，防止重复记录路径
				{
					minHeap.push(Edge(dsti, i, _edges[dsti][i]));
				}
			}

			cout << _vertexs[srci] << "--" << _vertexs[dsti] << ":" << w << endl;
		}
		else
		{
			cout << _vertexs[srci] << "--" << _vertexs[dsti] << ":" << w << "[构成环]" << endl;
		}
	}

	if (count == n - 1)
	{
		return total;
	}
	else
	{
		return W();
	}
}

细节：

1. 输入一个空图和一个起始点，输出最小生成树的总权值，并将空图变为最小生成树。
2. count记录已选边数，若达到n-1，则可直接跳出循环，提高效率。

四、Kruskal和Prim的对比

• Kruskal：适用于稀疏图，因为其从边的角度出发，边的数量相对少时效率更高。
• Prim：适用于稠密图，因为它每次从顶点出发，逐渐扩展树，对于稠密图（边多的图）效率更高