C++实现并查集结构-创新互联

前言

并查集一般用于多元素,多集合的查找问题;
听说很有用,但是平时好像确实没有怎么见过。。
leetcode典型例题:岛屿数量

成都创新互联是一家集网站建设,新安企业网站建设,新安品牌网站建设,网站定制,新安网站建设报价,网络营销,网络优化,新安网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。一、原理
  • 其实并查集的每个小集合就是一张有向图,只不过是所有子节点指向父节点的图结构。
    在这里插入图片描述
    他之所以能够高效的合并和查找,是因为它在查找过程中,一直在动态更改所有走过节点的父节点。
主要结构:

这里先定义一个节点结构:

templateclass EleNode
{public:
	T value;
	EleNode* father;
	EleNode(T val)
	{value = val;
		father = nullptr;
	}
};
  • 该节点结构非常类似于链表
    只不过它里面存的指针指向自己的爸爸

主结构中:

  • nodeMap根据用户数据存储对应节点数据,所有被创建出来的节点都被存放在里面
  • numMap仅用于记录该集合的元素数量(只记录头部元素,因为这个数据只需要一条)
  • void createNode(T val)函数中,创建节点需要在nodeMapnumMap中初始化
templateclass UnionFindSet
{//节点记录
	unordered_map*>nodeMap;
	//元素集数量记录
	unordered_map*, int>numMap;
public:
	UnionFindSet(){}
	//构造函数
	UnionFindSet(const vector& list)
	{for (int i = 0; i< list.size(); i++)
		{	createNode(list[i]);
		}
	}
	//销毁节点
	~UnionFindSet()
	{for (auto ele : nodeMap)
		{	delete ele.second;
		}
	}

	// 新建一个节点
	void createNode(T val)
	{if (nodeMap.find(val) != nodeMap.end()) return;
		EleNode* newNode = new EleNode(val);
		nodeMap.insert(make_pair(val, newNode));
		numMap.insert(make_pair(newNode, 1));
	}
}
主要方法:

有三个方法,分别为:

// 判断是否在同个集合中
bool isSameSet(const T& v1, const T& v2);
// 执行联合,即合并节点
void doUnion(EleNode* t1, EleNode* t2);
//找头节点
EleNode* findHead(EleNode* node);
  1. 判断是否在同个集合中
    判断两个节点的头节点是不是同一个。
    为啥要找到头节点?
    其实根据刚才的那张图就很显而易见
  • 如果两个节点在同一个集合中,那么他们两个一直执行查找父亲的操作;最后绝对能找到同一个头节点
  • 如果两个节点不在同集合中,那么执行该操作过后;最后绝对找到不同的头节点
// 是否为同个集合
	bool isSameSet(const T& v1, const T& v2)
	{assert(nodeMap.find(v1) != nodeMap.end() && nodeMap.find(v2) != nodeMap.end());
		return findHead(nodeMap[v1]) == findHead(nodeMap[v2]);
	}
  1. 合并节点
  • 将节点数量较小的那个集合,它的头部节点的指针指向节点数量较大集合的头节点。
    这实际上也是两个图结构的合并。至于为啥要选出节点少的一边,这个跟并查集的优化逻辑有关,放在下面的方法说。

1>首先判断他们是否已经在同个集合中,在同集合中就跳出。
2>再分别找到他们两个的集合数量中的较大值和较小值
3>将数量较小的一方并入数量较大的一方,通过将较小集合头节点的father指向改为较大集合头部
4>更新集合数量值
在这里插入图片描述

  • 比如上图中,用户输入2和4时,应该怎么操作?
    实际上就是直接将1号指针指向3号。
    改完以后:
    在这里插入图片描述
// 执行联合
	void doUnion(EleNode* t1, EleNode* t2)
	{// 判断头节点并保存
		EleNode* head1 = findHead(t1);
		EleNode* head2 = findHead(t2);
		if (head1 == head2) return;

		//找较大较小集合
		EleNode* big = numMap[head1] >= numMap[head2] ? head1 : head2;
		EleNode* small = numMap[head1] >= numMap[head2] ? head2 : head1;
		//改头
		small->father = big;
		//数值更新
		numMap[big] = numMap[big] + numMap[small];
		numMap.erase(small);
	}
public:
	// 执行联合外部接口
	void doUnion(const T& v1, const T& v2)
	{assert(nodeMap.find(v1) != nodeMap.end() && nodeMap.find(v2) != nodeMap.end());
		doUnion(nodeMap[v1], nodeMap[v2]);
	}
  1. 找头节点
  • 找头节点的操作不仅仅是找到头部,还包含了一个重要的优化
  • 这个优化就是将所有走过的,非头节点全部直接连在头结点上
  • 并查集中,一个集合(图)最理想的状态就是所有子节点全部直接指向头节点,这种情况下,从子节点向上寻找头节点的代价是O(1)

例:从2位置开始,找到集合头部
在这里插入图片描述
执行后:
在这里插入图片描述

  • 此时集合内节点数量未改变不需要调整,只需要调整结构即可

下面的函数中,将所有走过的路径全部压入栈内,并在找到头节点后,挨个将他的父亲改为头节点,最后返回头部。

//找头
	EleNode* findHead(EleNode* node)
	{stack*>path;
		while (node->father != nullptr)
		{	path.push(node);
			node = node->father;
		}
		while (!path.empty())
		{	path.top()->father = node;
			path.pop();
		}
		return node;
	}
二、全部代码
#include#include#include#include#includeusing namespace std;

templateclass EleNode
{public:
	T value;
	EleNode* father;
	EleNode(T val)
	{value = val;
		father = nullptr;
	}
};

templateclass UnionFindSet
{//节点记录
	unordered_map*>nodeMap;
	//元素集数量记录
	unordered_map*, int>numMap;

	//找头
	EleNode* findHead(EleNode* node)
	{stack*>path;
		while (node->father != nullptr)
		{	path.push(node);
			node = node->father;
		}
		while (!path.empty())
		{	path.top()->father = node;
			path.pop();
		}
		return node;
	}

	// 执行联合
	void doUnion(EleNode* t1, EleNode* t2)
	{EleNode* head1 = findHead(t1);
		EleNode* head2 = findHead(t2);
		if (head1 == head2) return;

		//合并
		EleNode* big = numMap[head1] >= numMap[head2] ? head1 : head2;
		EleNode* small = numMap[head1] >= numMap[head2] ? head2 : head1;
		small->father = big;
		numMap[big] = numMap[big] + numMap[small];
		numMap.erase(small);
	}
public:
	UnionFindSet(){}
	//构造函数
	UnionFindSet(const vector& list)
	{for (int i = 0; i< list.size(); i++)
		{	createNode(list[i]);
		}
	}
	//销毁节点
	~UnionFindSet()
	{for (auto ele : nodeMap)
		{	delete ele.second;
		}
	}

	// 新建一个节点
	void createNode(T val)
	{if (nodeMap.find(val) != nodeMap.end()) return;
		EleNode* newNode = new EleNode(val);
		nodeMap.insert(make_pair(val, newNode));
		numMap.insert(make_pair(newNode, 1));
	}

	// 判断是否在同个集合中
	bool isSameSet(const T& v1, const T& v2)
	{assert(nodeMap.find(v1) != nodeMap.end() && nodeMap.find(v2) != nodeMap.end());
		return findHead(nodeMap[v1]) == findHead(nodeMap[v2]);
	}

	// 执行联合外部接口
	void doUnion(const T& v1, const T& v2)
	{assert(nodeMap.find(v1) != nodeMap.end() && nodeMap.find(v2) != nodeMap.end());
		doUnion(nodeMap[v1], nodeMap[v2]);
	}
};

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网页名称:C++实现并查集结构-创新互联
链接地址:http://pwwzsj.com/article/dcjicp.html