【数据结构】图和并查集
🌈个人主页：秦jh_-ZEEKLOG博客
🔥 系列专栏：《数据结构》https://blog.ZEEKLOG.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482
目录
前言
💬 hello! 各位铁子们大家好哇。
今日更新了并查集和图的相关内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
C语言的输入与输出
并查集
并查集原理
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个 单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一 个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不 同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个 数。(负号下文解释)
毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是： 西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识 了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。
一趟火车之旅后，每个小分队成员就互相熟悉，称为了一个朋友圈。
从上图可以看出：编号6,7,8同学属于0号小分队，该小分队中有4人(包含队长0)；编号为4和9的同 学属于1号小分队，该小分队有3人(包含队长1)，编号为3和5的同学属于2号小分队，该小分队有3 个人(包含队长1)。
仔细观察数组中内融化，可以得出以下结论：
- 数组的下标对应集合中元素的编号
- 数组中如果为负数，负号代表根，数字代表该集合中元素个数
- 数组中如果为非负数，代表该元素双亲在数组中的下标
在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个 小圈子的学生相互介绍，最后成为了一个小圈子：
现在0集合有7个人，2集合有3个人，总共两个朋友圈。
通过以上例子可知，并查集一般可以解决一下问题：
1.查找元素属于哪个集合
沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
2.查看两个元素是否属于同一个集合
沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
3.将两个集合归并成一个集合
将两个集合中的元素合并
将一个集合名称改成另一个集合的名称
3.集合的个数
遍历数组，数组中元素为负数的个数即为集合的个数。
并查集实现
#pragma once #include<map> #include<vector> template<class T> class UnionFindSet { public: UnionFindSet(const T* a, int n) { for (int i = 0; i < n; i++) { _a.push_back(a[i]); _indexMap[a[i]] = i; } } private: vector<T> _a; //编号找人 map<T, int> _indexMap;//人找编号 }; 编号找人可以直接用vector搞定，人找编号可以通过map建立映射关系。
下面实现一个简单的，假设给的元素是下标。
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; };路径压缩是一个小优化：
当存储的是左边的情形时，在查找时，通过路径压缩，可以把层数降低。比如查找6时，会把6以及6上面的都变成根的直接儿子。这样下次查找这些数时，效率就变高了。
下面是两道使用并查集可以解决的题目：
图
图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，其中：
顶点集合V = {x|x属于某个数据对象集}是有穷非空集合；
E = {(x,y)|x,y属于V}或者E = {<x,y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合，也叫做边的集合。
(x, y)表示x到y的一条双向通路，即(x, y)是无方向的；Path(x, y)表示从x到y的一条单向通路，即 Path(x, y)是有方向的。
顶点和边：图中结点称为顶点，第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间 有一条边，图中的第k条边记作ek，ek = (vi，vj)或<vi,vj>。
有向图和无向图：在有向图中，顶点对是有序的，顶点对称为顶点x到顶点y的一条 边(弧)，<x,y>和<y,x>是两条不同的边，比如下图G3和G4为有向图。在无向图中，顶点对(x, y) 是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x, y)和(y，x) 是同一条边，比如下图G1和G2为无向图。注意：无向边(x, y)等于有向边<x,y>和<y,x> 。
树是一种特殊(无环联通)的图。图不一定是树。
完全图：在有n个顶点的无向图中，若有n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边， 则称此图为无向完全图，比如上图G1；在n个顶点的有向图中，若有n * (n-1)条边，即任意两个顶点之间有且仅有方向相反的边，则称此图为有向完全图，比如上图G4。
邻接顶点：在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依 附于顶点u和v；在有向图G中，若<u,v>是E(G)中的一条边，则称顶点u邻接到v，顶点v邻接自顶 点u，并称边<u,v>与顶点u和顶点v相关联。
顶点的度：顶点v的度是指与它相关联的边的条数，记作deg(v)。在有向图中，顶点的度等于该顶 点的入度与出度之和，其中顶点v的入度是以v为终点的有向边的条数，记作indev(v);顶点v的出度 是以v为起始点的有向边的条数，记作outdev(v)。因此：dev(v) = indev(v) + outdev(v)。注意：对于无向图，顶点的度等于该顶点的入度和出度，即dev(v) = indev(v) = outdev(v)。
路径：在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。
路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。
简单路径与回路：若路径上各顶点v1，v2，v3，…，vm均不重复，则称这样的路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环。
子图：设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图。
连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中任 意一 对顶点都是连通的，则称此图为连通图。
强连通图：在有向图中，若在每一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj 到 vi的路径，则称此图是强连通图。
生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点 和n-1条边。
图的存储结构
邻接矩阵
因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。
注意：
- 无向图的邻接矩阵是对称的，第i行(列)元素之和，就是顶点i的度。有向图的邻接矩阵则不一 定是对称的，第i行(列)元素之后就是顶点i 的出(入)度。
- 如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个 顶点不通，则使用无穷大代替。
- 用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通，缺陷是如果顶点比较多，边比 较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路 径不是很好求。
代码实现
namespace matrix { template<class V, class W, W MAX_W = INT_MAX, bool Direction = false> class Graph { 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; } _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 { 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); _matrix[srci][dsti] = w; //无向图 if (Direction == false) { _matrix[dsti][srci] = 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 < _matrix.size(); i++) cout << 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 << "* "; else cout << _matrix[i][j] << " "; } cout << endl; } cout << endl; } 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(); } }邻接表
邻接表：使用数组表示顶点的集合，使用链表表示边的关系。
1. 无向图邻接表存储
注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点 vi边链表集合中结点的数目即可。
2. 有向图邻接表存储
注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的dst取值是i。
代码实现
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 { 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]; _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;//邻接表 }; 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> g1(a, 4); g1.AddEdge("张三", "李四", 100); g1.AddEdge("张三", "王五", 200); g1.AddEdge("王五", "赵六", 30); g1.Print(); } } 
