当前位置： 首页 > article >正文

数据结构（并查集，图）

article 2025/4/1 17:51:19

并查集

练习版

class UnionFindSet
{
public:
	void swap(int* a, int* b)
	{
		int tmp = *a;
		*a = *b;
		*b = tmp;
	}
	UnionFindSet(size_t size)
		:_ufs(size,-1)
	{}
	int UnionFind(int x)
	{}
	void Union(int x1, int x2)
	{}

	//长分支改为相同节点
	int FindRoot(int x)
	{}
	bool InSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}
	int SetCount()
	{}
private:
	std::vector<int> _ufs;
};
class UnionFindSet
{
public:
	void swap(int* a, int* b)
	{
		int tmp = *a;
		*a = *b;
		*b = tmp;
	}
	UnionFindSet(size_t size)
		:_ufs(size,-1)
	{

	}
	int UnionFind(int x)
	{
		int parent = x;
		while (_ufs[parent] >= 0)
		{
			parent = _ufs[parent];
		}
		return parent;
	}
	void Union(int x1, int x2)
	{
		int root1 = UnionFind(x1);
		int root2 = UnionFind(x2);
		/*if (root1 > root2)
		{
			swap(&root1, &root2);
		}
		if (root1 != root2)
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}*/

		if (abs(_ufs[root1]) < abs(_ufs[root2]))
			swap(&root1, &root2);
		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	//长分支改为相同节点
	int FindRoot(int x)
	{
		int root = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}

		while (_ufs[x] >= 0)
		{
			int parent = _ufs[x];
			_ufs[x] = root;
			x = parent;
		}
		return root;
	}
	bool InSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}
	int SetCount()
	{
		int count = 0;
		for (int i = 0; i < _ufs.size(); i++)
		{
			if (_ufs[i] < 0)
				count++;
		}
		return count;
	}
private:
	std::vector<int> _ufs;
};

图

邻接矩阵

template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
	typedef Graph<V, W, MAX_W, Direction> Self;
public:
	Graph() = default;

	// 图的创建
	// 1、IO输入  -- 不方便测试,oj中更适合
	// 2、图结构关系写到文件，读取文件
	// 3、手动添加边
	Graph(const V* a, size_t n)//邻接矩阵
	{
		_vertexs.reserve(n);
		for (size_t i = 0; i < n; ++i)
		{
			_vertexs.push_back(a[i]);
			_indexMap[a[i]] = i;
		}

		_matrix.resize(n);
		for (size_t i = 0; i < _matrix.size(); ++i)
		{
			_matrix[i].resize(n, MAX_W);
		}
	}

	size_t GetVertexIndex(const V& v)
	{
		auto it = _indexMap.find(v);
		if (it != _indexMap.end())
		{
			return it->second;
		}
		else
		{
			//assert(false);
			throw invalid_argument("顶点不存在");

			return -1;
		}
	}


	void _AddEdge(size_t srci, size_t dsti, const W& w)
	{
		_matrix[srci][dsti] = w;
		// 无向图
		if (Direction == false)
		{
			_matrix[dsti][srci] = w;
		}
	}

	void AddEdge(const V& src, const V& dst, const W& w)
	{
		size_t srci = GetVertexIndex(src);
		size_t dsti = GetVertexIndex(dst);
		_AddEdge(srci, dsti, w);
	}

	void Print()
	{
		// 顶点
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
		}
		cout << endl;

		// 矩阵
		// 横下标
		cout << "  ";
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			//cout << i << " ";
			printf("%4d", i);
		}
		cout << endl;

		for (size_t i = 0; i < _matrix.size(); ++i)
		{
			cout << i << " "; // 竖下标
			for (size_t j = 0; j < _matrix[i].size(); ++j)
			{
				//cout << _matrix[i][j] << " ";
				if (_matrix[i][j] == MAX_W)
				{
					//cout << "* ";
					printf("%4c", '*');
				}
				else
				{
					//cout << _matrix[i][j] << " ";
					printf("%4d", _matrix[i][j]);
				}
			}
			cout << endl;
		}
		cout << endl;
	}
};

邻接矩阵 

template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
	typedef Graph<V, W, MAX_W, Direction> Self;
public:
	Graph() = default;

	// 图的创建
	// 1、IO输入  -- 不方便测试,oj中更适合
	// 2、图结构关系写到文件，读取文件
	// 3、手动添加边
	Graph(const V* a, size_t n)//邻接矩阵
	{
		_vertexs.reserve(n);
		for (size_t i = 0; i < n; ++i)
		{
			_vertexs.push_back(a[i]);
			_indexMap[a[i]] = i;
		}

		_matrix.resize(n);
		for (size_t i = 0; i < _matrix.size(); ++i)
		{
			_matrix[i].resize(n, MAX_W);
		}
	}

	size_t GetVertexIndex(const V& v)
	{
		auto it = _indexMap.find(v);
		if (it != _indexMap.end())
		{
			return it->second;
		}
		else
		{
			//assert(false);
			throw invalid_argument("顶点不存在");

			return -1;
		}
	}


	void _AddEdge(size_t srci, size_t dsti, const W& w)
	{
		_matrix[srci][dsti] = w;
		// 无向图
		if (Direction == false)
		{
			_matrix[dsti][srci] = w;
		}
	}

	void AddEdge(const V& src, const V& dst, const W& w)
	{
		size_t srci = GetVertexIndex(src);
		size_t dsti = GetVertexIndex(dst);
		_AddEdge(srci, dsti, w);
	}

	void Print()
	{
		// 顶点
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
		}
		cout << endl;

		// 矩阵
		// 横下标
		cout << "  ";
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			//cout << i << " ";
			printf("%4d", i);
		}
		cout << endl;

		for (size_t i = 0; i < _matrix.size(); ++i)
		{
			cout << i << " "; // 竖下标
			for (size_t j = 0; j < _matrix[i].size(); ++j)
			{
				//cout << _matrix[i][j] << " ";
				if (_matrix[i][j] == MAX_W)
				{
					//cout << "* ";
					printf("%4c", '*');
				}
				else
				{
					//cout << _matrix[i][j] << " ";
					printf("%4d", _matrix[i][j]);
				}
			}
			cout << endl;
		}
		cout << endl;
	}
private:
	vector<V> _vertexs;			// 顶点集合
	map<V, int> _indexMap;		// 顶点映射下标
	vector<vector<W>> _matrix;  // 邻接矩阵
};

广度优先遍历

void BFS(const V& src)//广度优先遍历
{
	size_t srci = GetVertexIndex(src);

	// 队列和标记数组
	queue<int> q;
	vector<bool> visited(_vertexs.size(), false);

	q.push(srci);
	visited[srci] = true;
	int levelSize = 1;

	size_t n = _vertexs.size();
	while (!q.empty())
	{
		// 一层一层出
		for (int i = 0; i < levelSize; ++i)
		{
			int front = q.front();//下标
			q.pop();
			cout << front << ":" << _vertexs[front] << " ";//下标对应的值
			// 把front顶点的邻接顶点入队列
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[front][i] != MAX_W)
				{
					if (visited[i] == false)
					{
						q.push(i);
						visited[i] = true;
					}
				}
			}
		}
		cout << endl;

		levelSize = q.size();
	}

	cout << endl;
}

深度优先遍历

void _DFS(size_t srci, vector<bool>& visited)
{
	cout << srci << ":" << _vertexs[srci] << endl;//访问起点
	visited[srci] = true;

	// 找一个srci相邻的没有访问过的点，去往深度遍历
	for (size_t i = 0; i < _vertexs.size(); ++i)
	{
		if (_matrix[srci][i] != MAX_W && visited[i] == false)
		{
			_DFS(i, visited);
		}
	}

}

void DFS(const V& src)
{
	size_t srci = GetVertexIndex(src);
	vector<bool> visited(_vertexs.size(), false);

	_DFS(srci, visited);
}

最小生成树

Kruskal算法
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, MAX_W);
	}

	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 ufs(n);
	while (!minque.empty())
	{
		Edge min = minque.top();
		minque.pop();

		if (!ufs.InSet(min._srci, min._dsti))
			//如果一条边的两个端点属于同一个集合，则形成环
		{
			cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
			minTree._AddEdge(min._srci, min._dsti, min._w);
			ufs.Union(min._srci, min._dsti);
			++size;
			totalW += min._w;
		}
		else
		{
			cout << "构成环：";
			cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
		}
	}

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

void TestGraphMinTree()
{
	const char* str = "abcdefghi";
	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);

	Graph<char, int> kminTree;
	cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
	kminTree.Print();
}

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, MAX_W);
	}

	/*set<int> X;
	set<int> Y;
	X.insert(srci);
	for (size_t i = 0; i < n; ++i)
	{
		if (i != srci)
		{
			Y.insert(i);
		}
	}*/

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

	cout << "Prim开始选边" << endl;
	size_t size = 0;
	W totalW = W();
	while (!minq.empty())
	{
		Edge min = minq.top();
		minq.pop();

		// 最小边的目标点也在X集合，则构成环
		if (X[min._dsti])
		{
			//cout << "构成环:";
			//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
		}
		else
		{
			minTree._AddEdge(min._srci, min._dsti, min._w);
			cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
			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 && Y[i])//避免重复
				{
					minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
				}
			}
		}
	}

	if (size == n - 1)
	{
		return totalW;
	}
	else
	{
		return W();
	}
}
void TestGraphMinTree()
	{
		const char str[] = "abcdefghi";
		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);

		Graph<char, int> kminTree;
		cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
		kminTree.Print();
		cout << endl << endl;

		Graph<char, int> pminTree;
		cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
		pminTree.Print();
		cout << endl;

		for (size_t i = 0; i < strlen(str); ++i)
		{
			cout << "Prim:" << g.Prim(pminTree, str[i]) << endl;
		}
	}

 

邻接表

template<class W>
struct Edge
{
	//int _srci;
	int _dsti;  // 目标点的下标
	W _w;		// 权值
	Edge<W>* _next;

	Edge(int dsti, const W& w)
		:_dsti(dsti)
		, _w(w)
		, _next(nullptr)
	{}
};

template<class V, class W, bool Direction = false>
class Graph
{
	typedef Edge<W> Edge;
public:
	Graph(const V* a, size_t n)
	{
		_vertexs.reserve(n);
		for (size_t i = 0; i < n; ++i)
		{
			_vertexs.push_back(a[i]);
			_indexMap[a[i]] = i;
		}

		_tables.resize(n, nullptr);
	}

	size_t GetVertexIndex(const V& v)
	{
		auto it = _indexMap.find(v);
		if (it != _indexMap.end())
		{
			return it->second;
		}
		else
		{
			//assert(false);
			throw invalid_argument("顶点不存在");

			return -1;
		}
	}

	void AddEdge(const V& src, const V& dst, const W& w)
	{
		size_t srci = GetVertexIndex(src);
		size_t dsti = GetVertexIndex(dst);

		// 1->2
		Edge* eg = new Edge(dsti, w);
		eg->_next = _tables[srci];//新创建的边的 _next 指针指向当前 _tables[srci] 所指向的链表头节点
		_tables[srci] = eg;//更新 _tables[srci] 使其指向新创建的边 eg，即将新边插入到链表头部

		// 2->1
		if (Direction == false)
		{
			Edge* eg = new Edge(srci, w);
			eg->_next = _tables[dsti];
			_tables[dsti] = eg;
		}
	}

	void Print()
	{
		// 顶点
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
		}
		cout << endl;

		for (size_t i = 0; i < _tables.size(); ++i)
		{
			cout << _vertexs[i] << "[" << i << "]->";
			Edge* cur = _tables[i];
			while (cur)
			{
				cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
				cur = cur->_next;
			}
			cout << "nullptr" << endl;
		}
	}

private:
	vector<V> _vertexs;			// 顶点集合
	map<V, int> _indexMap;		// 顶点映射下标
	vector<Edge*> _tables;		// 邻接表//表示存储每个顶点对应的边链表的表头指针数组
};

http://www.kler.cn/a/614735.html

相关文章：

  • Gerbv 与 Python 协同：实现 Gerber 文件智能分析与制造数据自动化
  • 【从零实现Json-Rpc框架】- 项目实现 - Dispatcher模块实现篇
  • AI+Xmind自动生成测试用例（思维导图格式）
  • RabbitMQ消息相关
  • 垃圾回收机制的几种实现机制简介
  • 【keil】单步调试
  • ✨分享我在飞书多维表格中使用DeepSeek的经历✨
  • c++第三课（基础c）
  • Android Jetpack学习总结（源码级理解）
  • 《云原生安全攻防》-- K8s容器安全：权限最小化与SecurityContext
  • 模块化革命：树莓派CM5嵌入式工业计算机如何重构嵌入式系统开发边界
  • 在IDEA中使用TortoiseSVN
  • C语言笔记数据结构（链表）
  • LangChain 基础系列之 Prompt 工程详解：从设计原理到实战模板
  • 爬虫问题整理（2025.3.27）
  • 软件的常用设计模式。可参考一个一个学习
  • 数据结构与算法——顺序表之手撕OJ题
  • 【商城实战(95)】Ansible自动化运维，开启高效部署新篇章
  • 2025清华大学：DeepSeek教程全集（PDF+视频精讲，共10份）.zip
  • 前端工程化--gulp的使用