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

快乐的流畅：个人主页

个人专栏：《C游记》《进击的C++》《Linux迷航》

远方有一堆篝火，在为久候之人燃烧！

文章目录

引言
一、最小生成树的概念
二、Kruskal算法
- 2.1 思想
- 2.2 实现
三、Prim算法
- 3.1 思想
- 3.2 实现
四、Kruskal和Prim的对比

引言

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

一、最小生成树的概念

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

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

只能使用该网络的边来构造最小生成树
只能使用恰好n-1条边来连接n个顶点
选用的这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算法采用全局贪心的策略：

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

具体图示如下：

2.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();}
}

细节：

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

三、Prim算法

3.1 思想

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

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

具体图示如下：

3.2 实现

思路：

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

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

细节：

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

四、Kruskal和Prim的对比

	Kruskal 算法	Prim 算法
算法类型	贪心算法	贪心算法
适用图类型	稀疏图，特别适合边权值分布较广的图	稠密图，特别适合顶点多边多的图
基本思想	从边的角度出发，按权值从小到大选择边	从顶点出发，每次扩展最小权值的边
时间复杂度	`O(E log V)`	`O(E log V)`
典型应用	网络设计问题，边多且分散的图	电网、网络设计问题，稠密的图
贪心选择标准	每次选择权值最小且不形成环的边	每次选择最小的连接权值，扩展已加入的顶点集合