【c++高阶DS】图

🔥个人主页：Quitecoder

🔥专栏：c++笔记仓

01.并查集

在一些应用问题中，需要将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)

仔细观察数组中内融化，可以得出以下结论：

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

在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个小圈子的学生相互介绍，最后成为了一个小圈子

现在0集合有7个人，2集合有3个人，总共两个朋友圈

通过以上例子可知，并查集一般可以解决一下问题：

1. 查找元素属于哪个集合
   沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
2. 查看两个元素是否属于同一个集合
   沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
3. 将两个集合归并成一个集合
   将两个集合中的元素合并
   将一个集合名称改成另一个集合的名称
4. 集合的个数
   遍历数组，数组中元素为负数的个数即为集合的个数

代码实现：

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;_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}int FindRoot(int x){int parent = x;while (_ufs[parent] >= 0){parent = _ufs[parent];}return parent;}bool InSet(int x1,int x2){return FindRoot(x1) == FindRoot(x2);}size_t SetSize(){size_t size= 0;for (int i = 0; i < _ufs.size(); i++){if (_ufs[i] < 0) ++size;}return size;}
private:vector<int> _ufs;
};

题目链接1：LCR 116. 省份数量
题目描述：

class Solution {
public:   int findCircleNum(vector<vector<int>>& isConnected) {UnionFindSet ufs(isConnected.size());for(int i=0;i<isConnected.size();i++){for(int j=0;j<isConnected[i].size();j++){if(isConnected[i][j]==1){ufs.Union(i,j);}}}return ufs.SetSize();}
};

题目链接2：990. 等式方程的可满足性
题目描述：

class Solution {
public:bool equationsPossible(vector<string>& equations) {UnionFindSet _ufs(26);for(auto& str: equations){if(str[1]=='='){_ufs.Union(str[0]-'a',str[3]-'a');}}for(auto& str2: equations){if(str2[1]=='!'){if(_ufs.InSet(str2[0]-'a',str2[3]-'a')) return false;}}return true;}
};

02.图的介绍

并查集是后面的铺垫，这里我们对图进行讲解：

图是由顶点集合及顶点间的关系组成的一种数据结构：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>称为顶点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条边。

03.图的存储结构

因为图中既有节点，又有边(节点与节点之间的关系)，因此，在图的存储中，只需要保存：节点和边关系即可。节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢

03.1.邻接矩阵

因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系

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

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

邻接矩阵存储方式非常适合稠密图
邻接矩阵O(1)判断两个顶点的连接关系，并取到权值

用邻接矩阵存储图的有点是能够快速知道两个顶点是否连通，缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求，同时也不好求一个顶点连接的边数

03.2.邻接表

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

1. 无向图邻接表存储
   
   指针数组：自己连接顶点边全都挂在下面
2. 有向图邻接表存储
   
   注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的dst取值是i。

邻接表适合存储稀疏图，也适合查找一个顶点连接出去的边，不适合去确定两个顶点是否相连及权值

03.3.矩阵版本代码实现

template<class V,class W, W MAX_W = INT_MAX,bool Direction = false>
class Graph
{private:vector<V> _vertexs;//顶点集合;map<V, int> _indexMap;//顶点映射下标;vector<vector<W>> _matrix;// 存储边集合的矩阵
};

构造函数：

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

这是一个带顶点数组 a 和顶点数量 n 的构造函数，作用是：

• 初始化图的顶点集合 _vertexs。
• 使用一个映射 _indexMap 存储顶点到索引的映射关系，方便后续操作。
• 使用二维矩阵 _matrix 初始化边的权值集合

_vertexs.reserve(n)：为顶点集合预留容量，避免后续动态扩展的开销。

遍历顶点数组，将每个顶点添加到 _vertexs，并记录其在数组中的索引到 _indexMap，实现顶点到索引的快速查找

_matrix.resize(n)：将矩阵调整为 n×n大小。
每行使用 resize(n, MAX_W) 将所有初始值设置为 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, consy W& w)
{size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w; if (Direction == false){_matrix[dsti][srci] = w;}
}

这段代码实现了两个关键功能：

1. GetVertexIndex 函数：查找顶点的索引。
2. AddEdge 函数：在图中添加边（支持有向图和无向图）。

实现逻辑：

• 使用 _indexMap.find(v) 在映射 _indexMap 中查找顶点 v。
• 如果找到，返回对应的索引 it->second。
• 如果未找到，抛出异常 invalid_argument("不存在的顶点")，提示顶点不存在。

在图中添加一条边，支持有向图和无向图。

输入参数：

• const V& src：边的起点顶点。
• const V& dst：边的终点顶点。
• const W& w：边的权值，引用方式传递，避免复制。

处理方向性：

• 有向图：只设置 _matrix[srci][dsti]。
• 无向图：同时设置 _matrix[srci][dsti] 和 _matrix[dsti][srci]。

打印函数：

void Print()
{// 打印顶点和下标映射关系for (size_t i = 0; i < _vertexs.size(); ++i){cout << _vertexs[i] << "-" << i << " ";}cout << endl << endl;cout << "  ";for (size_t i = 0; i < _vertexs.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){if (_matrix[i][j] != MAX_W)cout << _matrix[i][j] << " ";elsecout << "#" << " ";}cout << endl;}cout << endl << 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;}}}
}

进行测试：

03.4.邻接表版本代码实现

template<class W>
struct LinkEdge
{int _srcindex;           // 边的起点索引int _dstindex;           // 边的终点索引W _w;                    // 边的权值LinkEdge<W>* _next;      // 指向下一个边的指针，用于链式存储LinkEdge(const W& w): _srcIndex(-1)      // 默认起点索引为 -1, _dstIndex(-1)      // 默认终点索引为 -1, _w(w)              // 初始化权值, _next(nullptr)     // 指向下一个边的指针初始化为 nullptr{}
};
template<class V, class W,  bool Direction = false>
class Graph
{typedef LinkEdge<W> Edge;
public:private:vector<V> _vertexs;//顶点集合;map<V, int> _indexMap;//顶点映射下标;vector<Edge*> _tables;// 邻接表
};

初始化：

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

增加边：

void AddEdge(const V& src, const V& dst, const W& w)
{size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);Edge* sd_edge = new Edge(w);sd_edge->_srcindex = srci;sd_edge->_dstindex = dsti;sd_edge->_next = _tables[srci];_tables[srci] = sd_edge;if (Direction == false){Edge* ds_edge = new Edge(w);ds_edge->_srcIndex = dstindex;ds_edge->_dstIndex = srcindex;ds_edge->_next = _tables[dstindex];_tables[dstindex] = ds_edge;}
}

下面是详细的步骤说明，基于图中有四个顶点 ( A, B, C, D )。我们逐步构建它们的邻接表，同时解释代码的详细逻辑。

---

假设

1. 图的顶点集合为：[A, B, C, D]。
2. 图的边集合为：
   • ( A \to B )（权值 1）
   • ( A \to C )（权值 2）
   • ( B \to D )（权值 3）
   • ( C \to D )（权值 4）
3. 图是 有向图（即 ( Direction = true )）。

---

初始状态
邻接表 _tables 是一个数组，初始时，每个顶点的邻接表为空：

_tables: [nullptr, nullptr, nullptr, nullptr]

• ( _tables[0] ) 表示顶点 ( A ) 的邻接表头。
• ( _tables[1] ) 表示顶点 ( B ) 的邻接表头。
• ( _tables[2] ) 表示顶点 ( C ) 的邻接表头。
• ( _tables[3] ) 表示顶点 ( D ) 的邻接表头。

---

Step 1: 插入边 ( A \to B )（权值 1）

1. 调用 AddEdge("A", "B", 1)。

2. 获取顶点索引：

   • GetVertexIndex("A") 返回 0。
   • GetVertexIndex("B") 返回 1。

3. 创建新边 sd_edge：

   sd_edge->_srcindex = 0;  // A 的索引
   sd_edge->_dstindex = 1;  // B 的索引
   sd_edge->_w = 1;         // 权值 1
   sd_edge->_next = _tables[0];  // 当前 A 的邻接表头（nullptr）
   _tables[0] = sd_edge;         // 更新 A 的邻接表头为 sd_edge
   

4. 更新邻接表：

   _tables:
   [sd_edge, nullptr, nullptr, nullptr]
   

   此时，邻接表内容为：

   A: B (权值 1) -> nullptr
   B: nullptr
   C: nullptr
   D: nullptr
   

---

Step 2: 插入边 ( A \to C )（权值 2）

1. 调用 AddEdge("A", "C", 2)。

2. 获取顶点索引：

   • GetVertexIndex("A") 返回 0。
   • GetVertexIndex("C") 返回 2。

3. 创建新边 sd_edge：

   sd_edge->_srcindex = 0;  // A 的索引
   sd_edge->_dstindex = 2;  // C 的索引
   sd_edge->_w = 2;         // 权值 2
   sd_edge->_next = _tables[0];  // 当前 A 的邻接表头（指向 B 的边）
   _tables[0] = sd_edge;         // 更新 A 的邻接表头为 sd_edge
   

4. 更新邻接表：

   _tables:
   [sd_edge, nullptr, nullptr, nullptr]
   

   此时，邻接表内容为：

   A: C (权值 2) -> B (权值 1) -> nullptr
   B: nullptr
   C: nullptr
   D: nullptr
   

---

Step 3: 插入边 ( B \to D )（权值 3）

1. 调用 AddEdge("B", "D", 3)。

2. 获取顶点索引：

   • GetVertexIndex("B") 返回 1。
   • GetVertexIndex("D") 返回 3。

3. 创建新边 sd_edge：

   sd_edge->_srcindex = 1;  // B 的索引
   sd_edge->_dstindex = 3;  // D 的索引
   sd_edge->_w = 3;         // 权值 3
   sd_edge->_next = _tables[1];  // 当前 B 的邻接表头（nullptr）
   _tables[1] = sd_edge;         // 更新 B 的邻接表头为 sd_edge
   

4. 更新邻接表：

   _tables:
   [sd_edge, sd_edge, nullptr, nullptr]
   

   此时，邻接表内容为：

   A: C (权值 2) -> B (权值 1) -> nullptr
   B: D (权值 3) -> nullptr
   C: nullptr
   D: nullptr
   

---

Step 4: 插入边 ( C \to D )（权值 4）

1. 调用 AddEdge("C", "D", 4)。

2. 获取顶点索引：

   • GetVertexIndex("C") 返回 2。
   • GetVertexIndex("D") 返回 3。

3. 创建新边 sd_edge：

   sd_edge->_srcindex = 2;  // C 的索引
   sd_edge->_dstindex = 3;  // D 的索引
   sd_edge->_w = 4;         // 权值 4
   sd_edge->_next = _tables[2];  // 当前 C 的邻接表头（nullptr）
   _tables[2] = sd_edge;         // 更新 C 的邻接表头为 sd_edge
   

4. 更新邻接表：

   _tables:
   [sd_edge, sd_edge, sd_edge, nullptr]
   

   此时，邻接表内容为：

   A: C (权值 2) -> B (权值 1) -> nullptr
   B: D (权值 3) -> nullptr
   C: D (权值 4) -> nullptr
   D: nullptr
   

---

最终邻接表

最终的邻接表结构如下：

A: C (权值 2) -> B (权值 1) -> nullptr
B: D (权值 3) -> nullptr
C: D (权值 4) -> nullptr
D: nullptr

邻接表的 _tables 数据结构是：

_tables:
[sd_edge (A->C), sd_edge (B->D), sd_edge (C->D), nullptr]

最后完成打印函数;

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

完整代码：

#pragma once
#include<vector>
#include<map>using namespace std;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 << _vertexs[i] << "-" << i << " ";}cout << endl << endl;cout << "  ";for (size_t i = 0; i < _vertexs.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){if (_matrix[i][j] != MAX_W)cout << _matrix[i][j] << " ";elsecout << "#" << " ";}cout << endl;}cout << endl << 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;}}}}private:vector<V> _vertexs;//顶点集合;map<V, int> _indexMap;//顶点映射下标;vector<vector<W>> _matrix;// 存储边集合的矩阵};
}
namespace LinkTable
{template<class W>struct LinkEdge{int _srcindex;int _dstindex;W _w;//权值LinkEdge<W>* _next;LinkEdge(const W& w): _srcindex(-1), _dstindex(-1), _w(w), _next(nullptr){}};template<class V, class W,  bool Direction = false>class Graph{typedef LinkEdge<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);Edge* sd_edge = new Edge(w);sd_edge->_srcindex = srci;sd_edge->_dstindex = dsti;sd_edge->_next = _tables[srci];_tables[srci] = sd_edge;if (Direction == false){Edge* ds_edge = new Edge(w);ds_edge->_srcindex = dsti;ds_edge->_dstindex = srci;ds_edge->_next = _tables[dsti];_tables[dsti] = ds_edge;}}void Print(){for (size_t i = 0; i < _vertexs.size(); ++i){cout << _vertexs[i] << "-" << i << " ";}cout << endl << endl;for (int i = 0; i < _tables.size(); i++){cout << _vertexs[i] << "[" << i << "]->";Edge* cur = _tables[i];while (cur){cout << _vertexs[cur->_dstindex] << "[" << cur->_dstindex << "]" << cur->_w << "->";cur = cur->_next;}cout << "nullptr" << endl;}}private:vector<V> _vertexs;//顶点集合;map<V, int> _indexMap;//顶点映射下标;vector<Edge*> _tables;// 邻接表};
}
void TestGraph()
{matrix::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 TestGraph2()
{string a[] = { "张三", "李四", "王五", "赵六" };LinkTable::Graph<string, int> g1(a, 4);g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 200);g1.AddEdge("王五", "赵六", 30);g1.Print();
}