高阶数据结构(1):并查集与图

"Head in the clouds"

一、并查集

(1)认识并查集？

在一些问题中需要将n个不同的元素划分成一些不想交的集合。

开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。

例举如下场景:

某高校总共招生10人,成都5人,西安4人,武汉1人。这些人作为新人进入高校,可能并没有任何关系,互不相识。(一个一个单独的团体)

相反,如果此时要进行分寝,这些人便会自发组织成一个小队。

当然,在语言中,无法实现上述这样的结构。因此选用数组来进行模拟。

但,突然寝室单间规模进行更改,不再是单独的四人寝。那么也就意味着,本来已经以集合形式分离的三个队,此时需要进行合并。

此时,仅仅只需让另外一棵“树” 作为其子树即可。

得出以下结论:

1. 数组的下标对应集合中元素的编号
2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数
3. 数组中如果为非负数，代表该元素双亲在数组中的下标

(2)并查集的实现

由此,我们不免需要对以下问题提供解决方法:

1. 查找元素属于哪个集合
2. 查看两个元素是否属于同一个集合
3. 将两个集合归并成一个集合
4. 集合的个数

①查找


//查找x 属于哪一个集合(返回下标)
size_t FindRoot(int x)
{
	while (_ufs[x] >= 0)
			x = _ufs[x];
 
	return x;
}

沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)

②合并


		void Union(int x1, int x2)
		{
			//先判断是否x1 x2 已经属于此集合了
			int root1 = FindRoot(x1);
			int root2 = FindRoot(x2);
 
			//1.属于一个集合
			if (root1 == root2) return;
 
			//2.需要进行合并
			//用谁去做根呢 ？ 答案是都可以
			//两个棵树的 合并
			_ufs[root1]+=_ufs[root2];
			//去做 合并的子树
			_ufs[root2]=root1;
		}

1.将两个集合中的元素合并。

2.将一个集合名称改成另一个集合的名称。

③是否在集合里


		bool InSet(int x1,int x2)
		{
			return FindRoot(x1) == FindRoot(x2);
		}

沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在

④集合个数


		size_t SetSize()
		{
			int size = 0;
			for (auto e : _ufs)
			{
				if (e < 0) size++;
			}
			return size;
		}

遍历数组，数组中元素为负数的个数即为集合的个数。

测试1:

优化:

①路径压缩:

在这种情况下


		//查找x 属于哪一个集合(返回下标)
		size_t FindRoot(int x)
		{
			//先找到root 节点
			int root = x;
			while (_ufs[root] >= 0)
				root = _ufs[root];
 
			//路径压缩
			while (_ufs[x] >= 0) //直到更新到 根节点！
			{
				//记录x 的parnet 避免被修改
				int parent = _ufs[x];
				//直接让x 作为 root的子节点
				_ufs[x] = root;
 
				x = parent;
			}
			return x;
		}

②集合与集合的合并


		void Union(int x1, int x2)
		{
			//先判断是否x1 x2 已经属于此集合了
			int root1 = FindRoot(x1);
			int root2 = FindRoot(x2);
 
			//1.属于一个集合
			if (root1 == root2) return;
 
			//为什么需要小的集合树 向大的集合树合并？
			//控制 
			if (_ufs[root1] < _ufs[root2])
				swap(root1, root2);
 
			_ufs[root1]+=_ufs[root2];
			//去做 合并的子树
			_ufs[root2]=root1;
		}

(3)并查集OJ题

省份数量https://leetcode.cn/problems/bLyHh0/

但是,如果写一个这个题,就得写一整个并查集？显然很麻烦。

可见,并查集的核心就在于 find

等式方程的可满足性https://leetcode.cn/problems/satisfiability-of-equality-equations/comments/

二、图

(1)认识图

图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V,E)

V:顶点集合= {x|x属于某个数据对象集}是有穷非空集合;

E = {(x,y)|x,y属于V}或者E = {|x,y属于V && Path(x, y)}是顶点间关系的有穷集合，也叫
做边的集合;

你是否对G2感到熟悉？是的没错,树是一种特殊的集合。

图的其他概念:

1.完全图: 无向完全图(G1) 有向完全图(G4);

顾名思义，即任意两个顶点之间有且仅有一条边。

2.邻接顶点：在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点。

3.顶点的度：顶点v的度是指与它相关联的边的条数。

4.路径:在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。

5.路径长度:在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。

简单路径与回路：
径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环。

子图：设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E。

连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。

如果图中任意一对顶点都是连通的，则称此图为连通图。

生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。

(2)图的存储结构

图的存储结构,实质就是指的是顶点与权值的存储结构。

节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？

①邻接矩阵

因此邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。

注:

1.无向图的邻接矩阵是对称的，第i行(列)元素之和，就是顶点i的度。有向图的邻接矩阵则不一定是对称的，第i行(列)元素之后就是顶点i 的出(入)度。

2. 如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替。

反思:

优点

用邻接矩阵存储图的有点是能够快速知道两个顶点是否连通。

缺陷:

是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。

②邻接表

邻接表：使用数组表示顶点的集合，使用链表表示边的关系。

邻接表的实现,很类似于哈希桶的实现。在每个顶点的后面,挂接直接相连的点。

因此,如果想要知道一个顶点,和哪些顶点存在连通,只需要遍历链表即可。

注:因为无向图是双向的, 因此如果存在 i ->j 是连通的,那么 i->j 也是连通的。

(3)图存储结构的实现

①邻接矩阵

对于图而言,其也是一个数据结构。不外于 CURD；

ADD;


		size_t GetVertexIndex(const V& key)
		{
			auto ret = _mapIndex.find(key);
			if (ret != _mapIndex.end())
			{
				return ret->second;
			}
			else
			{
				//assert(false);
				cout << "顶点不存在:"<
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}
		void _AddEdge(size_t srci, size_t dsti,const W& w)
		{
			_martex[srci][dsti] = w;
 
			if (Direction == false)
			{
				_martex[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);
		}

删除、修改也就不再多言,就是找到 srci 、dsti 去邻接矩阵里操作即可。

测试:


		void Print()
		{
			for (size_t i = 0;i < _vertex.size();++i)
			{
				cout << "[" << i << "]" << "->" << _vertex[i]<
			}
 
			cout << "  ";
			for (size_t i = 0;i < _matrix.size();++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)
				{
					if (_matrix[i][j] == MAX_W)
					{
						//cout << "* ";
						printf("%4c", '*');
					}
					else
					{
						//cout << _matrix[i][j] << " ";
						printf("%4d", _matrix[i][j]);
					}
				}
				cout << endl;
			}
			cout << endl;
		}

②邻接表

ADD;


		size_t GetVertexIndex(const V& v)
		{
			auto ret = _mapIndex.find(v);
			if (ret != -_mapIndex.end())
			{
				return ret->second;
			}
			else
			{
				//assert(false);
				cout << "顶点不存在:" << key << endl;
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}
 
		void _AddEdge(size_t srci, size_t dsti, const W& w)
		{
			Edge* eg = new Edge(dsti, w);
			eg->_next = _table[srci];
			_table[srci] = eg;
 
			if (Direction == false)
			{
				Edge* eg = new Edge(srci, w);
				eg->_next = _table[dsti];
				_table[dsti] = eg;
			}
		}
 
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			_AddEdege(srci, dsti, w);
		}

测试:

(4)图的遍历

给定一个图G和其中任意一个顶点v0，从v0出发，沿着图中各边访问图中的所有顶点，

且每个顶点仅被遍历一次。

①广度(BFS)优先遍历

应用到图的顶点。

②深度(DFS)优先遍历

应用到图:

③具体实现:

BFS;


		void BFS(const V& src)
		{
			size_t srci = GetVertexIndex(src);
			int n = _vertex.size();
 
			queue<int> q;
			vector<bool> visited(n, false);
			size_t levelsize = 1;
			
			q.push(srci);
			visited[srci] = true;
 
			while (!q.empty())
			{
				for (size_t i = 0;i 
				{
					cout << "第" << i << "层";
					int front = q.front();
					q.pop();
					for (size_t i = 0;i < n;++i)
					{
						if (_matrix[front][i] != MAX_W
							&& visited[i] == false)
						{
							q.push(i);
							visited[i] = true;
						}
					}
				}
				levelsize = q.size();
			}
		}

DFS;


		void _DFS(size_t srci, vector<bool>& visited)
		{
			cout << srci << ":" << _vertex[srci] << endl;
			visited[srci] = true;
 
			for (size_t i = 0;i < _matrix.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(_matrix.size(),false);
			_DFS(srci, visited);
		}

测试;

三、图高阶(选学掌握)

对于图而言,掌握图的概念,图结构的基本优缺点,BFS \ DFS仅够了。

下面内容知道思想即可。

(1)最小生成树

什么是生成树呢？

连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不在连通；反之，在其中引入任何一条新边，都会形成一条回路。

最小生成树的三大准则;

1. 只能使用图中的边来构造最小生成树。

2.只能使用恰好n-1条边来连接图中的n个顶点
3.选用的n-1条边不能构成回路

最小生成树的算法;

Kruskal算法和Prim算法; 两者都是采用贪心策略

贪心算法:求局部最优解。从而实现整体的最优解。

①kruskal克鲁斯卡尔算法

思想:

任给一个有n个顶点的连通网络N={V,E}，首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}。

其中每个顶点自成一个连通分量，其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。

如此重复，直到所有顶点在同一个连通分量上为止。

核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。


		W Kruskal(Self& mintree)
		{
			size_t n = _vertex.size();
 
			mintree._vertex = _vertex;
			mintree._mapIndex = _mapIndex;
			mintree._matrix.resize(n);
			for (size_t i = 0;i < n;++i)
			{
				mintree._matrix[i].resize(n, MAX_W);
			}
 
			priority_queue, greater> minque;
			for (size_t i = 0;i < n;++i)
			{
				for (size_t j = 0;j < n;++j)
				{
					if (_matrix[i][j] != MAX_W)
					{
						minque.push(Edge(i,j,_matrix[i][j]));
					}
				}
			}
 
			int size = 0;
			W totalW = W();
 
			dy::UnionFindSet<int> ufs(n);
			while (!minque.empty())
			{
				Edge min = minque.top();
				minque.pop();
 
				if (!ufs.InSet(min._srci,min._dsti))
				{
					cout << _vertex[min._srci] << "->" << _vertex[min._dsti]<<":"<
					mintree._AddEdge(min._srci, min._dsti, min._w);
					ufs.Union(min._srci, min._dsti);
					++size;
					totalW += min._w;
				}
				else
				{
					cout << "构成环:";
					cout<<_vertex[min._srci]<<"->"<< _vertex[min._dsti]<<":"<< min._w<
				}
			}
 
			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

测试:

②Prim(普里姆算法)算法

思想:

Prim算法和 Dijkastra算法(最短路径) 的算法相似。

集合A的边总是能构成一颗树，这棵树可以从任何节点r开始, 直到覆盖V的所有节点。

算法每一步,就是去找和 A、A之外所有节点的边,自小的那个,加入到结合A当中。

因为每一步都是让权值最小的入集合,因此可以形成一个最小生成树。


		W Prim(Self& mintree,const V& src)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertex.size();
 
			mintree._vertex = _vertex;
			mintree._mapIndex = _mapIndex;
 
			mintree._matrix.resize(n);
			for (size_t i = 0;i < n;++i)
			{
				mintree._matrix[i].resize(n, MAX_W);
			}
 
			vector<bool> X(n,false);
			vector<bool> Y(n,true);
			X[srci] = true;
			Y[srci] = false;
			
			priority_queue, greater> minque;
			for (size_t i = 0;i < n;++i)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minque.push(Edge(srci, i,_matrix[srci][i]));
				}
			}
 
			cout << "Prim开始选边" << endl;
			size_t size = 0;
			W totalW = W();
			while (!minque.empty())
			{
				Edge min = minque.top();
				minque.pop();
 
				if (X[min._dsti])
				{
					//cout << "构成换" << min._srci << "->" << min._dsti<
				}
				else
				{
					//cout << "不构成" << min._srci << "->" << min._dsti <<":" << min._w;
					mintree._AddEdge(min._srci, min._dsti, min._w);
					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])
						{
							minque.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
						}
					}
				}
			}
 
			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

测试:

(2)最短路径

最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。

①Dijkstra(迪杰斯特拉)算法

单源最短路径--Dijkstra算法:

S为已确定的最短路径的结点集合。
Q为其余未确定最短路径的结点集合。

每次从Q 中找出一个起点到该结点代价最小的结点u ，将u 从Q 中移出，并放入S
中，对u 的每一个相邻结点v 进行松弛操作。

注:算法要求图中所有边的权重非负

本质和Prim如出一辙,也是使用的贪心策略。


		void Dijkstra(const V& src, vector& dist, vector<int>& pPath)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertex.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)
			{
				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;
 
				//松弛
				for (size_t v = 0;v < n;++v)
				{
					if (S[v] == false && _matrix[u][v] != MAX_W
						&& _matrix[u][v] + dist[u] < dist[v])
					{
							dist[v] = _matrix[u][v] + dist[u];
							pPath[v] = u;
					}
				}
			}
		}


		void PrintPathshort(const V& src ,const vector& dist,const vector<int>& pPath)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertex.size();
 
			for (size_t i = 0;i < n;++i)
			{
				if (i != srci)
				{
					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 << _vertex[index] << "->";
					}
					cout << "权值和：" << dist[i] << endl;
				}
			}
		}

测试:

②单源最短路径--Bellman-Ford算法

对于Dijkstra算法而言,唯一的不足在于,不能很好处理负权值位的问题。

Bellman-Ford算法:
优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显的缺点，它的时间复杂度 O(N*E)。

Bellman-Ford本质是一种暴力解法


 
		bool BellmanFord(const V& src,vector& dist,vector<int>& pPath)
		{
			size_t n = _vertex.size();
			size_t srci = GetVertexIndex(src);
			
			dist.resize(n, MAX_W);
			pPath.resize(n, -1);
 
			//srci -> srci
			dist[srci] = W();
			bool update = false;
			for (size_t k = 0;k < n;++k)
			{
				//i->j 更新一次
				cout << "更新边:" << endl;
				for (size_t i = 0;i < n;++i)
				{
					for (size_t j = 0;j < n;++j)
					{
						//srci -> i + i->j
						if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
						{
							update = true;
							cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j] << endl;
							dist[j] = dist[i] + _matrix[i][j];
							pPath[j] = i;
						}
					}
				}
 
				if (update == false) break;
			}
 
			// 还能更新就是带负权回路
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					// srci -> i + i ->j
					if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
					{
						return false;
					}
				}
			}
		}

测试:

关于bellford的优化除开上述的循环跳出

③多源最短路径--Floyd-Warshall算法

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。

上面两个算法主要针对单源路径。

Floyd-Warshall 也不会受到负权值的影响。


		void FloydWarshall(vector>& vvDist, vectorint>>& vvpPath)
		{
			size_t n = _vertex.size();
			vvDist.resize(n);
			vvpPath.resize(n);
			// 初始化权值和路径矩阵
			for (size_t i = 0; i < n; ++i)
			{
				vvDist[i].resize(n, MAX_W);
				vvpPath[i].resize(n, -1);
			}
 
 
			// 直接相连的边更新一下
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (_matrix[i][j] != MAX_W)
					{
						vvDist[i][j] = _matrix[i][j];
						vvpPath[i][j] = i;
					}
 
					if (i == j)
					{
						vvDist[i][j] = W();
					}
				}
			}
 
			// 不经过k
			for (size_t k = 0;k < n;++k)
			{
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						//k 作为中间 去更新 i->j
						// i->k  k->j
						if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
							&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
							{
							vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
							//因为是从i->k  k->j  k
							vvpPath[i][j] = vvpPath[k][j];
							}
					}
				}
			}
		}

④

说起三种算法,效率最高的肯定是

Dijkstra算法的空间复杂度可以达到O(N^2);

Bellmanford: 时间复杂度最坏可以达到O(N^3) 取决于图的密集程度

Floyd算法和bell 相差无几

总结

①并查集的概念、实际应用

②图的概念、存储结构（邻接表、邻接矩阵）

③图的遍历BFS、DFS

④最小生成树+最短路径

本篇就到此为止啦

感谢你的阅读 ~ 祝你好运

相关阅读:
哈希表的总结
 KubeSphere简介，功能介绍，优势，架构说明及应用场景
 分子相互作用的人工智能
 Python123：使用函数输出指定范围内的Fibonacci数、使用函数验证哥德巴赫猜想（C语言）
梯度下降、损失函数、神经网络的训练过程
 Selenium自动化测试框架工作原理你明白了吗？
【Java 基础篇】Java LinkedHashSet 详解：有序唯一元素存储的完美选择
 SAP 内向交货单报表
 vue实现浏览器禁止复制、禁用F12、禁用右侧菜单
 软考高项重要知识点整理
原文地址：https://blog.csdn.net/RNGWGzZs/article/details/127117013

高阶数据结构(1):并查集 与 图

一、并查集

(1)认识并查集？

得出以下结论:

(2)并查集的实现

①查找

②合并

③是否在集合里

④集合个数

测试1:

优化:

①路径压缩:

②集合与集合的合并

(3)并查集OJ题

二、图

(1)认识图

图的其他概念:

(2)图的存储结构

①邻接矩阵

②邻接表

(3)图存储结构的实现

①邻接矩阵

ADD;

测试:

②邻接表

ADD;

测试:

(4)图的遍历

①广度(BFS)优先遍历

②深度(DFS)优先遍历

③具体实现:

测试;

三、图高阶(选学掌握)

(1)最小生成树

①kruskal克鲁斯卡尔算法

测试:

②Prim(普里姆算法)算法

测试:

(2)最短路径

①Dijkstra(迪杰斯特拉)算法

测试:

②单源最短路径--Bellman-Ford算法

测试:

③多源最短路径--Floyd-Warshall算法

④

总结

高阶数据结构(1):并查集与图