淮南做网站公司,厚街建设网站,网站建设实用教程,企业服务平台公众号最小生成树 并查集定义举例说明查找某个元素属于哪个集合代码实现路径压缩 Kruskal算法原理代码实现 Prim算法原理代码实现 并查集
定义
#x1f680;在一些应用问题中#xff0c;需要将n个不同的元素分成一些不相交的集合。开始时#xff0c;每个元素自成一个单元素集合在一些应用问题中需要将n个不同的元素分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素属于哪个集合的运算。适合描述这类问题的抽象数据结构叫做并查集。
由于每个集合就是一颗树形结构一个并查集内存在多个集合所以并查集是一个森林。 通常用数组来充当这种数据结构采用双亲表示法的方式即子节点存储父节点的指针。
举例说明
例如有10名同学它们的编号分别为0-9它们来自三个班级1班2班3班其中034号同学来自一班179同学来自2班2568号同学来自3班。
初始结构每个元素各自独立为一个集合。 元素的合并相同班级的同学合并为同一个集合。 合并规则 将子节点的数据加到父节点的数据中将字节点的数据改为父节点的指针。这样父节点中的数据的绝对值就是此集合中元素个数各个子节点存储的都是指向父节点的指针。 合并的优化 在合并时最好将集合内元素数量较少的集合合并到集合内元素数量多的集合。这样在查找某个元素属于哪个集合时可以减少时间消耗。例如将1班和3班合并优先是将1班合并到3班这样第三层的结点数量比较少相比于将3班合并到1班。 查找某个元素属于哪个集合 例如查找n号下元素属于哪个集合只需要判断n号位置的元素是否为负数如果为负数说明n号位置就是这个集合的根节点(用根节点的下标来标识集合)如果不是负数就顺着父节点向上访问直到根节点为止。
代码实现
#pragma once#include vector
#include iostream/*
* 并查集
* 1.核心采用双亲表示法孩子结点存储的是父节点的下表
* 2.采用类似堆的结构表示---在数组中存储
*/
class UnionFindSet {
private:std::vectorint _ufs;
public:UnionFindSet(size_t n) :_ufs(n,-1) {}int FindRoot(int x) {int parent x;//一直向上找到存储负数的结点while (_ufs[parent] 0) {parent _ufs[parent];}return parent;}void Union(int x1, int x2) {int root1 FindRoot(x1);int root2 FindRoot(x2);if (root1 root2) { return; } //本身就在一个集合当中if (abs(_ufs[root1]) abs(_ufs[root2])) {std::swap(root1, root2);}_ufs[root1] _ufs[root2]; //将root2结点的数据加到root1结点的数据上_ufs[root2] root1; //将root2结点的数据修改为root1(根结点的下标)}size_t SetSize() const {size_t cnt 0;for (auto e : _ufs) {if (e 0) { cnt; } //结点数据为0的就表示为根结点能够代表一个集合}return cnt;}bool InSet(int x1, int x2) {int root1 FindRoot(x1);int root2 FindRoot(x2);return root1 root2;}
};路径压缩
在经过多次集合合并时可能会出现某个集合的树形结构深度很深从而导致查询某个元素的集合时时间消耗比较大所以可以对树形结构的路径进行压缩。 上图只是个示例通常来说数据量很大的时候才需要路径压缩。
压缩策略 在查找某个元素属于哪个集合时进行路径的压缩在找到某个元素的根节点后不着急返回而是依次将此路径上的该元素的父节点合并到根结点处完成路径压缩。这样下次再查找某个元素属于哪个集合时就可以提高效率。 int FindRoot(int x) {int parent x;//一直向上找到存储负数的结点while (_ufs[parent] 0) {parent _ufs[parent];}//核心代码int cur x;while (_ufs[cur] 0) {int tmp cur;cur _ufs[cur];_ufs[tmp] parent;}return parent;
}Kruskal
最小生成树 最小生成树就是在图的所有生成树中找出各个路径权值和最小的那个路径。
算法原理
克鲁斯卡尔算法是求图的最小生成树的一个经典算法其采用全局贪心的思想每次都去选权值最小的边(可以将所有边放在一个小根堆中每次获取堆顶元素)去构成最小生成树(不能重复选取某一个边)但是这种贪心方式可能会造成环路的产生所以在每选一个边之前都要判断一下选取这个边后会不会构成环路。而判环的这个步骤使用并查集是非常适合的可以将已经选取出来的构成最小生成树的顶点放在一个集合S中在添加某个边时如果这个边的两个顶点均位于集合S中说明构成了环路这条边是不能选取的。 选取边的过程 最小生成树的结果并不唯一例如上图中有两个权值为8的边上面的选法中是选取了ah这条边选取bc这条边也是没有问题的。
代码实现
struct Edge {size_t _srci;size_t _dsti;W _weight;Edge(size_t srci,size_t dsti,const W weight) :_srci(srci),_dsti(dsti),_weight(weight) {}bool operator (const Edge e) const {return _weight e._weight;}
};W Kruskal(self min_tree) {size_t n _vertex.size();min_tree._vertex _vertex;min_tree._index_map _index_map;//初始化矩阵min_tree._matrix.resize(n, std::vectorW(n, W_MAX));//开始计算最小生成树std::priority_queueEdge,std::vectorEdge,std::greaterEdge pq;for (int i 0; i n; i) {for (int j 0; j n; j) {if (i j _matrix[i][j] ! W_MAX) { //ij在无向图中避免同一条边添加两次pq.push(Edge(i, j, _matrix[i][j]));}}}W total W();//记录权值和size_t size 0;//记录挑选出的边的个数UnionFindSet ufs(n);while (size n - 1 !pq.empty()) {Edge eg pq.top();pq.pop();if (ufs.InSet(eg._srci, eg._dsti) false) {min_tree._AddEdge(eg._srci, eg._dsti, eg._weight);ufs.Union((int)eg._srci, (int)eg._dsti);total eg._weight;size;}}if (size ! n - 1) {return W();}return total;
}Prim
算法原理
Prim算法与Krunskal算法都是采用贪心的策略但是Prim算法采用的是局部贪心的策略在Prim算法中会将图的顶点分类到两个集合XY中对于已经选入到最小生成树的边相连的顶点放在X集合中没有选进最小生成树的顶点放入Y集合。而在贪心选取权值最小的边时是在一个顶点位于X集合另一个顶点位于Y集合的所有边中去选择的。所以Prim算法需要指定一个起始顶点。当某个顶点被添加到X集合后要将与其相连的边放入到优先级队列中放入优先级队列的边也是有要求的就是它另一个顶点必须是在Y集合中的如果采用优先级队列的方式存储边仍然会出现环路情况所以在选边的同时也要注意判环操作 选取边的过程 假设起始顶点为a 代码实现
W Prim(self min_tree, const V src) {size_t n _vertex.size();min_tree._vertex _vertex;min_tree._index_map _index_map;//初始化矩阵min_tree._matrix.resize(n, std::vectorW(n, W_MAX));//将所有的顶点划分为两个集合 X Y已经选择的点放入X集合中没有选择的点在Y集合中size_t srci this-GetVertexIndex(src);std::vectorbool X(n, false);std::vectorbool Y(n, true);X[srci] true;Y[srci] false;//将与X集合中所有顶点相连的边存入优先级队列以供贪心选择std::priority_queueEdge, std::vectorEdge, std::greaterEdge pq;for (size_t i 0; i n; i) {if (_matrix[srci][i] ! W_MAX) {pq.push(Edge(srci, i, _matrix[srci][i]));}}size_t size 0;W total_w W();while (size n - 1 !pq.empty()) {Edge eg pq.top();pq.pop();//防止选出的边构成环if (true X[eg._dsti]) {continue;}X[eg._dsti] true;Y[eg._dsti] false;min_tree._AddEdge(eg._srci, eg._dsti, eg._weight);size;total_w eg._weight;//std::cout _vertex[eg._srci] - _vertex[eg._dsti] : eg._weight std::endl;//将以dsti点为起点的边加入到队列中for (size_t i 0; i n; i) {//存在边且终点位于Y集合中if (_matrix[eg._dsti][i] ! W_MAX Y[i]) {pq.push(Edge(eg._dsti, i, _matrix[eg._dsti][i]));}}}if (size ! n - 1) {return W();}return total_w;
}
