🎬慕斯主页：修仙—别有洞天
♈️今日夜电波：アンビバレント—Uru
0:24━━━━━━️💟──────── 4:02
🔄 ◀️ ⏸ ▶️ ☰
💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍
目录
并查集
并查集的概述及原理
并查集的实现
完整代码
图的存储结构
邻接矩阵
邻接矩阵的概述及原理
邻接矩阵的实现
完整代码
邻接表
邻接表的概述及原理
邻接表的实现
完整代码
图的遍历
广度优先遍历
广度优先遍历的概述及原理
广度优先遍历的实现
深度优先遍历
深度优先遍历的概述及原理
深度优先遍历的实现
并查集
并查集的概述及原理
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。 大致可以按如下的图示进行理解：
通过概述以及图示可见，并查集一般可以解决以下问题：
- 查找元素属于哪个集合
沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)- 查看两个元素是否属于同一个集合
沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在- 将两个集合归并成一个集合
将两个集合中的元素合并
将一个集合名称改成另一个集合的名称- 集合的个数
遍历数组，数组中元素为负数的个数即为集合的个数。
该如何实现上述的要求呢？我们可以按照如下的步骤进行实现：
并查集的实现
实际上并查集的实现同我们之前实现堆的原理是很像的！都是在数组中进行实现的，下面详细的介绍并查集实现的原理：
- 数组的下标对应集合中元素的编号
- 数组中一个位置是负数，那他就是树的根，这个负数的绝对值就是这颗树的数据个数
- 数组中如果一个位置是正数，那他就是双亲的下标
可以根据下图进行理解：
我们根据原理，首先使用vector容器来储存元素，利用构造函数根据要给的元素的数量来初始化并查集中的元素都为-1：
class UnionFindSet
{
public:
UnionFindSet(int size)
: _set(size, -1)
{}
private:
std::vector<int> _set;
};
最主要的函数，找到该元素所在集合的名称，即根如果刚刚开始并没有连接只是单独的根，则该集合为自己：
size_t FindRoot(int x)
{
//如果数组中存储的是负数，找到，否则一直继续
while(_set[x] >= 0)
x = _set[x];
return x;
}根据两个数来将他们合并到同一个集合，可以看到先利用了上面找根的函数找到各自的根，再将对应根的值加上另外一个根的值（这步可以理解成将两个值进行集合，也可以理解为连个集合进行集合），接着将成为孩子节点的根改为对应根的下标：
void Union(int x1, int x2)
{
//找他们各自的根
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
//只有当根不同时才合并
if(root1 != root2)
{
_set[root1] += _set[root2];
_set[root2] = root1;
}
}
最后使用一个函数来统计数组中负数的个数，即为集合的个数：
size_t SetCount()
{
size_t count = 0;
for(size_t i = 0; i < _set.size(); ++i)
{
if(_set[i] < 0)
count++;
}
return count;
}判断该是否在同一个根节点，同时也是判是否成环的操作：
bool InSet(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2);
}完整代码
#include <vector>
class UnionFindSet
{
public:
UnionFindSet(int size)
: _set(size, -1)
{}
size_t FindRoot(int x)
{
while(_set[x] >= 0)
x = _set[x];
return x;
}
void Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if(root1 != root2)
{
_set[root1] += _set[root2];
_set[root2] = root1;
}
}
size_t SetCount()
{
size_t count = 0;
for(size_t i = 0; i < _set.size(); ++i)
{
if(_set[i] < 0)
count++;
}
return count;
}
bool InSet(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2);
}
private:
std::vector<int> _set;
};图的存储结构
邻接矩阵
邻接矩阵的概述及原理
邻接矩阵是一种用于表示图中顶点之间相邻关系的矩阵数据结构。
以下是对邻接矩阵的概述及原理的具体介绍：
- 图的定义：图是一种非线性的数据结构，由节点（也称为顶点）和连接节点的边组成。顶点之间的连接关系可以是单向的（有向图）或双向的（无向图）。图可以用来表示各种关系，如网络、社交关系、地图等，在计算机科学和现实生活中有着广泛的应用。
- 邻接矩阵的定义：对于一个图( G=(V,E) )，其中( V )是顶点集合，( E )是边的集合，图的邻接矩阵是一个二维数组，其行和列对应于图中的顶点。如果顶点( i )与顶点( j )相邻，则邻接矩阵中的元素( A[i][j] )为1（对于无权图），否则为0。对于有权图，该元素表示的是顶点( i )和( j )之间边的权重。
- 无向图与有向图：在无向图中，若存在边连接顶点( i )和( j )，则邻接矩阵是对称的，即( A[i][j]=A[j][i] )。而在有向图中，如果存在从顶点( i )指向顶点( j )的边，则( A[i][j] )可能不等于( A[j][i] )，因为方向不同。 大致图示如下（分别为不带权以及带权）：
- 邻接矩阵的性质：
- 对于无向图，邻接矩阵沿主对角线对称，并且主对角线上的元素都是0，因为顶点不与自己相邻。
- 对于有向图，主对角线上的元素也是0，但是矩阵一般不再对称，因为边的方向决定了邻接关系的方向性。
- 使用邻接矩阵的优点：
- 方便查询任意两个顶点之间是否存在边。
- 可以直观地表示出图的结构。
- 便于进行某些图算法的计算，如寻找图中的路径或者进行图的遍历。
- 使用邻接矩阵的缺点：
- 如果图不是非常稠密，即边的数量远小于顶点数量的平方，那么邻接矩阵会包含大量的零元素，这会造成存储空间的浪费。
- 对于稀疏图，邻接表等其他数据结构可能是更高效的选择。
邻接矩阵的实现
这里实现的邻接矩阵，根据给定的顶点以及顶点数来利用构造函数进行初始化构造，利用vector容器来按照对应的类型储存定点、二维的vector容器来存储边、map来存储对应顶点的下标。下面具体介绍成员变量以及初始化的构造：
利用模版定义V用于表示顶点、W表示边，W MAX_W = INT_MAX作为非类型参数，表示模板可以接受任何W类型的值作为MAX_W，如果没有提供，那么默认值为INT_MAX。bool Direction表示为是否为有向图，默认为false。接下来按照给的顶点以及顶点的数量来进行构造初始化，首先得到指定数量大小的空间，接着将顶点插入_vertexs顶点集合并使用_vIndexMap映射对应定点的下标，最后将_matrix的空间初始化，由于是矩阵，那么排和列的值是相同的。
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
public:
typedef Graph<V, W, MAX_W, Direction> Self;
Graph() = default;
Graph(const V* vertexs, size_t n)
{
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i)
{
_vertexs.push_back(vertexs[i]);
_vIndexMap[vertexs[i]] = i;
}
// MAX_W 作为不存在边的标识值
_matrix.resize(n);
for (auto& e : _matrix)
{
e.resize(n, MAX_W);
}
}
private:
map<V, size_t> _vIndexMap; //用于查找对应顶点的下标
vector<V> _vertexs; // 顶点集合
vector<vector<W>> _matrix; // 存储边集合的矩阵
};如下函数用于根据顶点值通过_vIndexMap的映射关系来查找对应的下标：
size_t GetVertexIndex(const V& v)
{
auto ret = _vIndexMap.find(v);
if (ret != _vIndexMap.end())
{
return ret->second;//找到了就返回储存的下标
}
else
{
throw invalid_argument("不存在的顶点");//没找到则抛异常
return -1;
}
}如下函数用于添加边，通过给两个顶点的值来使得他们在_matrix二维矩阵中建立联系：
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);
}完整代码
#pragma once#include<iostream>#include <vector>#include <map>using namespace std;template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>class Graph{public: typedef Graph<V, W, MAX_W, Direction> Self; Graph() = default; Graph(const V* vertexs, size_t n) { _vertexs.reserve(n); for (size_t i = 0; i < n; ++i) { _vertexs.push_back(vertexs[i]); _vIndexMap[vertexs[i]] = i; } // MAX_W 作为不存在边的标识值 _matrix.resize(n); for (auto& e : _matrix) { e.resize(n, MAX_W); } } size_t GetVertexIndex(const V& v) { auto ret = _vIndexMap.find(v); if (ret != _vIndexMap.end()) { return ret->second; } else { 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 << _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] << " "; else cout << "#" << " "; } 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: map<V, size_t> _vIndexMap; //用于查找对应顶点的下标 vector<V> _vertexs; // 顶点集合 vector<vector<W>> _matrix; // 存储边集合的矩阵};邻接表
邻接表的概述及原理
邻接表是图论中用于表示图结构的一种数据结构，它有效地描述了图中顶点之间的连接关系。
以下是对邻接表的概述和原理：
- 基本概念：邻接表是图的一种主要存储方式，用于描述图上每个顶点的邻接关系。对于图中的每个顶点，都建立一个容器（例如链表），该容器中的节点包含了与该顶点相邻的所有其他顶点的信息。
- 结构组成：通常，邻接表由两部分组成：一部分是顶点数组，每个索引对应一个顶点；另一部分是边表，包含所有边的信息。边表中的每条记录至少包含与顶点相连接的另一顶点的引用或索引。
- 有向图与无向图：在有向图中，边表记录的是单向连接，即从一点指向另一点的边；而在无向图中，边表中会同时记录两个方向的连接。如下分别是无向图以及有向图的图解：
注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点vi边链表集合中结点的数目即可 。
注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的dst取值是i。 （实际上，我们根据需求来确定是否需要入边表，正常一个出边即可）
- 空间效率：邻接表相对于邻接矩阵来说，在存储空间上更为高效，尤其是对于稀疏图（边数远小于顶点平方数的图）。这是因为邻接表仅存储存在的边，而不是像邻接矩阵那样为每对顶点分配空间，无论它们之间是否存在边。
- 不唯一性：由于边表中边的记录顺序可以互换，因此邻接表的表示不是唯一的。
- 实现步骤：创建邻接表时，首先需要定义图的结构体，包括顶点和边数。然后通过一维数组保存顶点信息，并通过结构体中的指针域建立边表，这些边表通常以链表的形式存在，每个链表节点代表一条边，并指向邻接的顶点。
- 适用场景：由于其空间效率，邻接表特别适合于表示边数较少的稀疏图。而对于稠密图（边数接近顶点数平方的图），邻接矩阵可能是更合适的选择。
邻接表的实现
首先实现边的结构体，给定两个int类型表示源地址_srcIndex以及目标地址_dstIndex（实际上就是对应顶点的下标），根据模版类型W来存储边的权值_w，给定一个_next来链接下一个边关系，最后使用构造函数初始化一下对应的值。如下：
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)
{}
};根据上述给出来的边关系来给定成员变量以及构造函数，模版中V表示顶点类型，W表示边的类型，Direction表示是否为有向图，默认为无向图，接下来，_vertexs首先是获得对应的大小的空间，将定点装入顶点集合，在搞定_vIndexMap映射对应的顶点下标，最后按照顶点的数量让_linkTable边集合初始化：
template<class V, class W, bool Direction = false>
class Graph
{
typedef LinkEdge<W> Edge;
public:
Graph(const V* vertexs, size_t n)
{
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i)
{
_vertexs.push_back(vertexs[i]);
_vIndexMap[vertexs[i]] = i;
}
_linkTable.resize(n, nullptr);
}
private:
map<V, int> _vIndexMap;//用于查找对应顶点的下标
vector<V> _vertexs; // 顶点集合
vector<Edge*> _linkTable; // 边的集合的临接表
};如下函数用于根据顶点值通过_vIndexMap的映射关系来查找对应的下标：
size_t GetVertexIndex(const V& v)
{
auto ret = _vIndexMap.find(v);
if (ret != _vIndexMap.end())
{
return ret->second;/找到了就返回储存的下标
}
else
{
throw invalid_argument("不存在的顶点");//没找到则抛异常
return -1;
}
}如下函数根据给定的源地址_srcIndex以及目标地址_dstIndex（实际上就是对应顶点的下标）、权值来链接对应的边。首先回去对应顶点的下标，然后，先是存储有向图的情况，储存权值、源地址和目标地址，再以头插的方式插入边的集合的临接表。需要注意是否为有向图，Direction == false这个判断条件即可：
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srcindex = GetVertexIndex(src);
size_t dstindex = GetVertexIndex(dst);
// 0 1
Edge* sd_edge = new Edge(w);
sd_edge->_srcIndex = srcindex;
sd_edge->_dstIndex = dstindex;
sd_edge->_next = _linkTable[srcindex];//头插
_linkTable[srcindex] = sd_edge;
// 1 0
// 无向图
if (Direction == false)
{
Edge* ds_edge = new Edge(w);
ds_edge->_srcIndex = dstindex;
ds_edge->_dstIndex = srcindex;
ds_edge->_next = _linkTable[dstindex];
_linkTable[dstindex] = ds_edge;
}
}完整代码
#pragma once#include<iostream>#include <vector>#include <map>using namespace std;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* vertexs, size_t n) { _vertexs.reserve(n); for (size_t i = 0; i < n; ++i) { _vertexs.push_back(vertexs[i]); _vIndexMap[vertexs[i]] = i; } _linkTable.resize(n, nullptr); } size_t GetVertexIndex(const V& v) { auto ret = _vIndexMap.find(v); if (ret != _vIndexMap.end()) { return ret->second; } else { throw invalid_argument("不存在的顶点"); return -1; } } void AddEdge(const V& src, const V& dst, const W& w) { size_t srcindex = GetVertexIndex(src); size_t dstindex = GetVertexIndex(dst); // 0 1 Edge* sd_edge = new Edge(w); sd_edge->_srcIndex = srcindex; sd_edge->_dstIndex = dstindex; sd_edge->_next = _linkTable[srcindex];//头插 _linkTable[srcindex] = sd_edge; // 1 0 // 无向图 if (Direction == false) { Edge* ds_edge = new Edge(w); ds_edge->_srcIndex = dstindex; ds_edge->_dstIndex = srcindex; ds_edge->_next = _linkTable[dstindex]; _linkTable[dstindex] = ds_edge; } }private: map<V, int> _vIndexMap; vector<V> _vertexs; // 顶点集合 vector<Edge*> _linkTable; // 边的集合的临接表};图的遍历
广度优先遍历
广度优先遍历的概述及原理
图的广度优先遍历（Breadth-First Search, BFS）是一种用于图的遍历或搜索算法，它从一个指定的起始点开始，逐层向外访问图中的顶点。
以下是广度优先遍历的主要原理和步骤：
- 初始化：将起始节点入队，并标记为已访问。
- 队列操作：使用一个队列来记录待访问的节点。在队列非空的情况下，执行以下操作：
- 从队列中取出一个节点，这个节点是当前层的节点。
- 访问该节点，对于图来说，可以是输出节点信息、检查节点属性等。
- 查找所有与该节点相邻且未被访问过的节点，并将它们加入队列尾部，同时标记为已访问。
- 重复过程：重复上述过程，直到队列为空，即所有可以到达的节点都被访问过。
大致图示：
广度优先遍历的特点包括：
- 层次性：它按照距离源节点的近远来进行遍历，因此可以用于找到最短路径或者理解图的层次结构。
- 非递归性：不同于深度优先搜索（DFS），BFS通常不采用递归实现，而是使用循环和队列来实现。
- 空间复杂度：由于需要存储待访问节点，BFS的空间复杂度可能较高，特别是在稠密图中。
- 唯一性：当使用邻接矩阵表示图时，BFS的遍历序列是唯一的；而使用邻接表时，由于边的列表顺序可能不同，遍历序列可能不唯一。
需要注意的是：图的广度优先遍历同我们之前二叉树的广度优先遍历是有一点不同的：我们都知道顶点出队列都会将他的邻接顶点也放入队列，二叉树是单向的，但是图确是双向的（有向图也可能两边顶点都互相指向）。因此，当图的顶点进队列时，可能会出现重复的顶点入队列的情况。因此，我们需要使用一个数组根据上面对于图的存储结构提到的“下标”映射关系来标记是否入过队列！因此，每次入队时都会更新是否入队。
广度优先遍历的实现
在这里广度优先实现是基于邻接矩阵的基础上的！我们通过给起始的顶点，然后根据上述邻接矩阵的函数获取srcindex（对应顶点的下标），创建访问数组visited 并初始化，创建队queue，需要注意的是：我们每次入队列都要标记一下！ d用于表示为第几度，dSize 记录队列中有多少个值，当所有队列的值都出完了，才能进入下一个度！
void BFS(const V& src)
{
size_t srcindex = GetVertexIndex(src);
vector<bool> visited;
visited.resize(_vertexs.size(), false);
queue<int> q;
q.push(srcindex);
visited[srcindex] = true;
size_t d = 1;
size_t dSize = 1;
while (!q.empty())
{
printf("%s的%d度好友:", src.c_str(), d);
while (dSize--)
{
size_t front = q.front();
q.pop();
for (size_t i = 0; i < _vertexs.size(); ++i)
{
if (visited[i] == false && _matrix[front][i] != MAX_W)
{
printf("[%d:%s] ", i, _vertexs[i].c_str());
visited[i] = true;
q.push(i);
}
}
}
cout << endl;
dSize = q.size();
++d;
}
cout << endl;
}深度优先遍历
深度优先遍历的概述及原理
图的深度优先遍历（Depth-First Search, DFS）是一种递归的图遍历算法，它从一个指定的起始节点出发，探索尽可能深的分支，直到到达一个节点，该节点没有未被访问的相邻节点，然后回溯到上一个节点继续探索其他分支，直至所有节点都被访问过。
以下是深度优先遍历的主要原理和步骤：
- 选择起始节点：从图中选择一个节点作为起始点开始遍历。
- 标记访问过的节点：在访问过程中，为了避免重复访问和无限循环，需要将访问过的节点做上标记。
- 递归访问：从当前节点出发，选择一个未被访问的相邻节点进行访问，并标记为已访问。如果存在多个选择，可以根据特定规则（如右手原则）来选择。
- 回溯：当无法找到未访问的相邻节点时，返回上一节点，继续尝试访问其他未被探索的路径。
- 重复过程：重复上述过程，直到所有节点都被访问过。
大致图示如下：
深度优先遍历的特点包括：
- 递归性：DFS通常使用递归来实现，这使得代码简洁且易于理解。
- 空间复杂度：由于采用递归，DFS的空间复杂度与递归栈的深度有关，因此在最坏情况下可能较高。
- 非唯一性：遍历的顺序可能不唯一，因为它依赖于相邻节点的选择顺序。
深度优先遍历的实现
在这里图的深度优先的实现是基于邻接表的基础上的！对于刷过很多BFS以及回溯题的我们估计也是洒洒水啦！我们在邻接表中定义的边的结构体的优越性就体现出来了，其中储存的_dst就很好的帮助我们找到了目标节点，_DFS 中pCur = pCur->_pNext; 表示的就是回溯的过程，代码实现如下：
void _DFS(int index, vector<bool>& visited)
{
if (!visited[index])
{
cout << _v[index] << " ";
visited[index] = true;
LinkEdge* pCur = _linkEdges[index];
while (pCur)
{
_DFS(pCur->_dst, visited);
pCur = pCur->_pNext;
}
}
}
void DFS(const V& v)
{
cout << "DFS:";
vector<bool> visited(_v.size(), false);
_DFS(GetIndexOfV(v), visited);
for (size_t index = 0; index < _v.size(); ++index)
_DFS(index, visited);
cout << endl;
}感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
给个三连再走嘛~
版权声明：本文为博主作者：慕斯( ˘▽˘)っ原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/weixin_64038246/article/details/136848608
