高阶数据结构----------并查集和图

2023-11-10 12:30
文章标签 数据结构 高阶 并查 集和图

本文主要是介绍高阶数据结构----------并查集和图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 各个根节点保存的该集合的数量。叶子节点保存的根节点的下标。代码实现如下

UnionFindSet.h

#pragma once
#include <vector>
#include <map>//template<class T>
//class UnionFindSet
//{
//public:
//	UnionFindSet(const T* a, size_t n)
//	{
//		for (size_t i = 0; i < n; ++i)
//		{
//			_a.push_back(a[i]);
//			_indexMap[a[i]] = i;
//		}
//	}
//private:
//	vector<T> _a;                  // 编号找人
//	map<T, int> _indexMap;          // 人找编号
//};class UnionFindSet
{
public:UnionFindSet(size_t n):_ufs(n, -1){}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]))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);}size_t SetSize(){size_t size = 0;for (size_t i = 0; i < _ufs.size(); ++i){if (_ufs[i] < 0){++size;}}return size;}private:vector<int> _ufs;
};void TestUnionFindSet()
{UnionFindSet ufs(10);ufs.Union(8, 9);ufs.Union(7, 8);ufs.Union(6, 7);ufs.Union(5, 6);ufs.Union(4, 5);ufs.FindRoot(6);ufs.FindRoot(9);
}

Graph.h

#pragma once
#include <vector>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <functional>// weight
namespace matrix
{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);cout << "不存在顶点" << ":" << v << endl;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;for (size_t i = 0; i < _matrix.size(); ++i){for (size_t j = 0; j < _matrix[i].size(); ++j){if (i < j && _matrix[i][j] != MAX_W){cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;}}}}//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;//	size_t n = _vertexs.size();//	while (!q.empty())//	{//		int front = q.front();//		q.pop();//		cout << front <<":"<<_vertexs[front] << endl;//		// 把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;//}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);}struct Edge{size_t _srci;size_t _dsti;W _w;Edge(size_t srci, size_t dsti, const W& w):_srci(srci), _dsti(dsti), _w(w){}bool operator>(const Edge& e) const{return _w > e._w;}};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();}}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 PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath){size_t srci = GetVertexIndex(src);size_t n = _vertexs.size();for (size_t i = 0; i < n; ++i){if (i != srci){// 找出i顶点的路径vector<int> path;size_t parenti = i;while (parenti != srci){path.push_back(parenti);parenti = pPath[parenti];}path.push_back(srci);reverse(path.begin(), path.end());for (auto index : path){cout << _vertexs[index] << "->";}cout << dist[i] << endl;}}}void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath){size_t srci = GetVertexIndex(src);size_t n = _vertexs.size();dist.resize(n, MAX_W);pPath.resize(n, -1);dist[srci] = 0;pPath[srci] = srci;// 已经确定最短路径的顶点集合vector<bool> S(n, false);for (size_t j = 0; j < n; ++j){// 选最短路径顶点且不在S更新其他路径int u = 0;W min = MAX_W;for (size_t i = 0; i < n; ++i){if (S[i] == false && dist[i] < min){u = i;min = dist[i];}}S[u] = true;// 松弛更新u连接顶点v  srci->u + u->v <  srci->v  更新for (size_t v = 0; v < n; ++v){if (S[v] == false && _matrix[u][v] != MAX_W&& dist[u] + _matrix[u][v] < dist[v]){dist[v] = dist[u] + _matrix[u][v];pPath[v] = u;}}}}private:vector<V> _vertexs;			// 顶点集合map<V, int> _indexMap;		// 顶点映射下标vector<vector<W>> _matrix;  // 邻接矩阵};void TestGraph1(){Graph<char, int, INT_MAX, true> g("0123", 4);g.AddEdge('0', '1', 1);g.AddEdge('0', '3', 4);g.AddEdge('1', '3', 2);g.AddEdge('1', '2', 9);g.AddEdge('2', '3', 8);g.AddEdge('2', '1', 5);g.AddEdge('2', '0', 3);g.AddEdge('3', '2', 6);g.Print();}void TestBDFS(){string a[] = { "张三", "李四", "王五", "赵六", "周七" };Graph<string, int> g1(a, sizeof(a) / sizeof(string));g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 200);g1.AddEdge("王五", "赵六", 30);g1.AddEdge("王五", "周七", 30);g1.Print();g1.BFS("张三");g1.DFS("张三");}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;}}void TestGraphDijkstra(){/*const char* str = "syztx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 10);g.AddEdge('s', 'y', 5);g.AddEdge('y', 't', 3);g.AddEdge('y', 'x', 9);g.AddEdge('y', 'z', 2);g.AddEdge('z', 's', 7);g.AddEdge('z', 'x', 6);g.AddEdge('t', 'y', 2);g.AddEdge('t', 'x', 1);g.AddEdge('x', 'z', 4);vector<int> dist;vector<int> parentPath;g.Dijkstra('s', dist, parentPath);g.PrintShortPath('s', dist, parentPath);*/// 图中带有负权路径时，贪心策略则失效了。// 测试结果可以看到s->t->y之间的最短路径没更新出来const char* str = "sytx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 10);g.AddEdge('s', 'y', 5);g.AddEdge('t', 'y', -7);g.AddEdge('y', 'x', 3);vector<int> dist;vector<int> parentPath;g.Dijkstra('s', dist, parentPath);g.PrintShortPath('s', dist, parentPath);}
}namespace link_table
{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->2Edge* eg = new Edge(dsti, w);eg->_next = _tables[srci];_tables[srci] = eg;// 2->1if (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;		// 邻接表};void TestGraph1(){/*Graph<char, int, true> g("0123", 4);g.AddEdge('0', '1', 1);g.AddEdge('0', '3', 4);g.AddEdge('1', '3', 2);g.AddEdge('1', '2', 9);g.AddEdge('2', '3', 8);g.AddEdge('2', '1', 5);g.AddEdge('2', '0', 3);g.AddEdge('3', '2', 6);g.Print();*/string a[] = { "张三", "李四", "王五", "赵六" };Graph<string, int, true> g1(a, 4);g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 200);g1.AddEdge("王五", "赵六", 30);g1.Print();}
}

 Test.cpp

#include <iostream>
using namespace std;#include "UnionFindSet.h"
#include"Graph.h"//int main()
//{
//	string a[] = { "", "", "", "" };
//	UnionFindSet<string> ufs(a, 4);
//
//	return 0;
//}int main()
{//matrix::TestGraph1();//matrix::TestBDFS();//matrix::TestGraphMinTree();matrix::TestGraphDijkstra();//link_table::TestGraph1();//TestUnionFindSet();return 0;
}

这篇关于高阶数据结构----------并查集和图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/382664。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2