产品营销推广方式_室内设计网站集合_抖音seo怎么收费_百度一下你就知道了

  博客主页：花果山~程序猿-CSDN博客

文章分栏：高阶数据结构_花果山~程序猿的博客-CSDN博客

关注我一起学习，一起进步，一起探索编程的无限可能吧！让我们一起努力，一起成长！

目录

一，并查集

查找

合并

应用题

二，图

图的基本概念

图的存储结构

1.邻接矩阵

优势

缺点

2.邻接表

优势

图的遍历（邻接矩阵）

1.广度优先遍历

2.深度优先遍历

三，最小生成树

Kruskal算法 

Prim算法

两种算法为什么能保证得到最小生成树？

前提

四，最短路径

1.Dijkstra算法

2.Bellman-Ford算法

3.floyd-warshall算法

嗨！收到一张超美的图，愿你每天都能顺心！

一，并查集

        并查集（Union-Find）是一种数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。它在算法中非常有用，尤其是在图论中处理连通性问题时。

并查集能够高效地支持两种操作：

1. 查找（Find）：确定元素属于哪一个子集。它可以用来确定两个元素是否位于同一个子集中。
2. 合并（Union）：将两个子集合并成一个单一的集合。

关于理解 树 与 树之间的合并：

1.当数据量比较少时，让一个树的根作为另一棵树的子树，并修改val值即可。

2.如果按照1方法进行树与树之间合并，当数据量比较大时，调用查找获取所在树时，需要经历多次"跳跃"，因此在该情况下，应将子树拆散，直接作为孩子，提高效率（这也是路径压缩的算法思路）。

查找

寻找到目标的根下标

size_t GetRoot(size_t order)
{int root = order;while (_union_set[root] >= 0){root = _union_set[root];}// 开始向上压缩---数据量打时采用压缩算法while (_union_set[order] >= 0){int parent = _union_set[order];_union_set[order] = root;order = parent;}return root;
}

合并

    void _union(size_t a, size_t b){a = GetRoot(a);b = GetRoot(b);if (a == b) return; // 相同树，不合并if (a > b)swap(a, b);_union_set[a] += _union_set[b];_union_set[b] = a;}

应用题

LCR 116. 省份数量 - 力扣（LeetCode）

990. 等式方程的可满足性 - 力扣（LeetCode）

二，图

图是一种非线性数据结构，它由顶点（Vertices）和边（Edges）组成，用于表示对象之间的多对多关系。图在许多领域都有广泛的应用，比如社交网络分析、路由算法、编译器优化等。

图的基本概念

• 顶点（Vertex/Node）：图中的基本单位，代表一个实体。
• 边（Edge）：连接两个顶点的线，表示这两个顶点之间存在某种关系。
• 有向图（Directed Graph）：边是有方向的，从一个顶点指向另一个顶点。

• 无向图（Undirected Graph）：边是没有方向的，表示两个顶点是相互连接的。

• 加权图（Weighted Graph）：每条边上都关联有一个权重值，通常用来表示成本或距离，这个可以灵活多变的。
• 路径（Path）：一系列相连的边，构成从一个顶点到另一个顶点的路线。
• 连通图（Connected Graph）：对于无向图，如果任意两个顶点之间都存在一条路径，则称该图为连通图；
• 对于有向图，若存在一条从任何顶点到其他所有顶点的路径，则称为强连通图。
• 环（Cycle）：一条起始顶点和结束顶点相同的路径。
• 度（Degree）：与某个顶点相连的边的数量。在有向图中分为入度（进入顶点的边数）和出度（离开顶点的边数）。

图的存储结构

1.邻接矩阵

注意：

优势

1. 邻接矩阵适合稠密图，即：相同成本下，边(关系越复杂)越多，矩阵利用率越高。
2. 矩阵能在O（1）内判断两 顶点的关系，并获取到 权值。

缺点

无法快速获取一个顶点所连接的所有顶点——O（n），遍历一层。

具体代码：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

2.邻接表

优势

1. 适合稀疏图(边少 |  关系简单)
2. 适合查找一个顶点的所有关系 ——O(1)效率

框架：

具体代码：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

总结：两数据结构相辅相成，互为互补关系；

图的遍历（邻接矩阵）

1.广度优先遍历

 难点：

1. 如何处理好一次存储层顶点？——采用队列保存层顶点，这里下标代表顶点。

2. 如何避免重复访问顶点？ ——采用set思想，访问顶点就标记，避免形成环。

// 层序遍历————默认从0开始层序遍历void BFS(const V &v){auto index = GetIndex(v);queue<int> q;                vector<bool> _set(_vertices.size(), false);q.push(index);cout << _vertices[index] << "->";_set[index] = true;while (q.empty() != true){int tmp = q.front();q.pop();// 获取所有连接点,并判断载入队列int time = 0;while (time < _matrix[tmp].size()){if (_matrix[tmp][time] != INT_MAX && _set[time] == false){q.push(time);cout << _vertices[time] << " ";_set[time] = true;}time++;}cout << "->";}cout << endl;}

2.深度优先遍历

深度优先遍历较广度，逻辑难度复杂，代码简单。在效率方面，在深度较深时，效率下降，甚至会出现栈溢出现象。

方法：递归 

void _dfs(int index, vector<bool> &_set)
{cout << _vertices[index] << "--";for (int i = 0; i < _matrix[index].size(); i++){if (_set[i] != true && _matrix[index][i] != INT_MAX){_set[i] = true;_dfs(i, _set);}}
}void DFS(const V &v){auto index = GetIndex(v);vector<bool> _set(_vertices.size(), false);_set[index] = true;_dfs(index, _set);cout << endl;}

具体代码见代码仓库：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

三，最小生成树

在连通图中，有n 个顶点，如果通过 n - 1将这n个顶点连接起来，那个形成的树就是生成树。

最小生成树的三个准则：

• 只能使用图中的边来构造最小生成树
• 只能使用恰好n-1条边来连接图中的n个顶点
• 选用的n-1条边不能构成回路

Kruskal算法 

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边（贪心算法），加入到最小生成树的边集合（并查集中）里。

思路解析： 

1. 把图中的所有边按权值从小到大排序（这里采用优先级队列 + 仿函数，也可以采用其他容器 + 排序）； 
2. 把图中的n个顶点看成独立的n棵树组成的森林； 
3. 按权值从小到大选择边，所选的边连接的两个顶点v1,v2。 v1与 v2 应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。 
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

代码：

W Kruskal(Graph<V, W>& minfree){priority_queue<edge, vector<edge>, greater<edge>> greater_queue;// 队列载入边信息for (int i = 0; i < _matrix.size(); i++){for (int j = 0; j < _matrix[i].size(); j++){if (i >= j && _matrix[i][j] != INT_MAX)greater_queue.push(edge(i, j, _matrix[i][j]));}}size_t sum_edge = 0;W sum_w = W();// 初始化并查集UnionFindSet it(_vertices.size());int time = _vertices.size() - 1;// 只连接 n - 1次，判断该无向图是否有最小生成树while (sum_edge < time){edge tmp = greater_queue.top();// 防止出现闭环，原理：并查集同树if (it.IsSameRoot(tmp._v1, tmp._v2)){greater_queue.pop();continue;}// cout << _vertices[tmp._v1] << "->" << _vertices[tmp._v2] << ": " << tmp._w << endl;//单独构建一个外部最小生成树minfree.size_t_addedge(tmp._v1, tmp._v2, tmp._w);it._union(tmp._v1, tmp._v2);greater_queue.pop();sum_w += tmp._w;sum_edge++;}// cout << "w : " << sum_w << endl;// cout << "sum_edge : " << sum_edge << endl;// cout << "_vertice : " << _vertices.size() << endl;// 经过n - 1次连接边，如果所有顶点都在树中，则有最小生成树；// 如何判断？ 并查集，由于我们实现了压缩路径算法，所以所有孩子只有一个根。int root = it.GetRoot(0);for (int i = 1; i < it.size(); i++){   // 如果根不相同，说明还有孤岛顶点，即不是最小生成树if (root != it.GetRoot(i))return W();}return sum_w;}

具体代码 & 测试用例，见代码仓库：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

Prim算法

普里姆算法其实是在U和V-U两个阵营中不停的找一条最短的（代价最低的）可连通的边，然后将该边附着的在V-U阵营中的顶点加入U阵营中。

思路解析:

1. 需要两个容器负责X, Y集合的快速插入 & 检测存在功能（这里我采用set<size_t>）
2. 选择一个初始顶点加入到生成树中。
3. 初始化一个优先队列（或最小堆），存储不在生成树中的顶点及其到当前生成树的最小边权。
4. 从未加入生成树的顶点中选择一个与生成树相连的边权最小的顶点，加入到生成树中。
5. 更新优先队列，反映新加入顶点带来的影响。
6. 重复步骤 4 和 5 直到所有顶点都被加入到生成树中。直到优先级队列中没有边为止；如果记录的  边数量 == 顶点 - 1 （n - 1）则为最小生成树

下面采用另一位大佬的图解：

代码:

W Prim(Graph<V, W> &minfree, const V &start){size_t ptr = GetIndex(start);set<size_t> X;set<size_t> Y;for (int i = 0; i < _vertices.size(); i++)Y.insert(i);priority_queue<edge, vector<edge>, greater<edge>> greater_queue;// 先载入开始顶点X.insert(ptr);Y.erase(ptr);// 队列载入与顶点相连边的顶点信息for (int i = 0; i < _matrix.size(); i++){if (_matrix[ptr][i] != INT_MAX)greater_queue.push(edge(ptr, i, _matrix[ptr][i]));}size_t edge_sum = 0;W w_sum = 0;while (greater_queue.empty() != true){edge tmp = greater_queue.top();if (X.find(tmp._v1) != X.end() && X.find(tmp._v2) != X.end()){greater_queue.pop();continue;}// 不都在X中都载入size_t new_X;if (X.find(tmp._v1) == X.end())new_X = tmp._v1;elsenew_X = tmp._v2;// cout << _vertices[tmp._v1] << "->" << _vertices[tmp._v2] << ": " << tmp._w << endl;minfree.size_t_addedge(tmp._v1, tmp._v2, tmp._w);greater_queue.pop();w_sum += tmp._w;edge_sum++;X.insert(new_X);Y.erase(new_X);for (int i = 0; i < _matrix.size(); i++){if (_matrix[new_X][i] != INT_MAX)greater_queue.push(edge(new_X, i, _matrix[new_X][i]));}}// cout << "w : " << w_sum << endl;// cout << "sum_edge : " << edge_sum << endl;// cout << "_vertice : " << _vertices.size() << endl;if (edge_sum != _vertices.size() - 1)return W();return w_sum;}

具体代码 & 测试用例，见代码仓库：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

两种算法为什么能保证得到最小生成树？

这两种算法都基于贪心策略，但在理论上已经被证明能够找到最小生成树。这是因为最小生成树问题满足贪心选择性质和最优子结构性质。也就是说，在每一步中选择当前最优解（局部最优解），最终能得到全局最优解。

前提

只要图中的边权是非负的，Kruskal 算法和 Prim 算法就能正确地找到最小生成树。如果存在负权边，那么最小生成树的概念就不再适用，因为负权边可能会导致循环，从而使得没有明确的最小生成树。

四，最短路径

1.Dijkstra算法

特点：Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径。

时间复杂度：O(N^2)

算法原理可以查看该作者博客，通俗易懂：

【看完必懂】Dijkstra算法（附案例详解） - 知乎

流程图： 

代码：

void Dijkstra(const V &v){vector<W> dij_vec(_vertices.size(), INT_MAX);vector<bool> exist(_vertices.size(), true);int exist_sum = _vertices.size();auto start_index = GetIndex(v);dij_vec[start_index] = 0;exist[start_index] = false;exist_sum--;while (exist_sum > 0){// 在未被标记顶点内寻找for (int i = 0; i < _matrix[start_index].size(); i++){if (exist[i] && _matrix[start_index][i] != INT_MAX){dij_vec[i] = min(dij_vec[i], (_matrix[start_index][i] + dij_vec[start_index]));}}// 开始删除目前最小值//获取最小值下标int index = -1;size_t min_index = INT_MAX;for (int i = 0; i < dij_vec.size(); i++){if (exist[i] && dij_vec[i] < min_index){min_index = dij_vec[i];index = i;}}// 删除已经确定的顶点if (index != -1){//    cout << "delete: " << _vertices[index] << endl;exist[index] = false;start_index = index;exist_sum--;}        }cout << "结果：" << endl;for (int i = 0; i < dij_vec.size(); i++){cout << _vertices[i] << " min:" << dij_vec[i] << endl;}}

全部代码，见代码仓库：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

2.Bellman-Ford算法

bellman—ford算法可以解决负权图的单源最短路径问题 

特点： 

• 适用于含有负权边的图（Dijkstra不适用）
• 简单粗暴，但效率慢（N^3）
• 如果对应路径存在负权回路则没有最短路径（可用于判断图中是否存在负权回路）

基本步骤 

void Bellman_Ford(const V &v){vector<W> bell_vec(_vertices.size(), INT_MAX);vector<size_t> last_index(_vertices.size(), -1);auto start_index = GetIndex(v);bell_vec[start_index] = 0;last_index[start_index] = 0;int n = _vertices.size();for (int z = 0; z < n; z++){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (_matrix[i][j] != INT_MAX && bell_vec[i] + _matrix[i][j] < bell_vec[j]){bell_vec[j] = bell_vec[i] + _matrix[i][j];last_index[j] = i;}}}}for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (_matrix[i][j] != INT_MAX && bell_vec[i] + _matrix[i][j] < bell_vec[j]){return false;}}}return true;}

3.floyd-warshall算法

loyd-Warshall算法是一种解决全网最短路径问题（All-Pairs Shortest Path, APSP）的动态规划算法。它可以在有向或无向图中找到任意两点之间的最短路径，即使图中包含负权重的边也可以处理。

特点

• 适用于密集图或当需要知道所有顶点对之间的最短路径时使用（在稀疏图非负权图上，不如多次调用dijkstra速度快）
• 代码简单，逻辑暴力，时间复杂度——O(n^3)
• 无法解决负权回路问题

以下是Floyd-Warshall算法的主要步骤：

1. 初始化距离矩阵：

   • 对于所有顶点对(i, j)，如果(i, j)直接相连，则d[i][j]设置为边的权重。
   • 如果i = j，则d[i][j] = 0。
   • 否则，如果不存在直接连接，则d[i][j]设置为无穷大（+∞）。

2. 动态规划：

   • 逐步考虑每一个顶点k作为中间顶点，尝试通过k来改进i到j之间的最短路径。
   • 使用以下更新规则：对于每一对顶点(i, j)，如果d[i][k] + d[k][j] < d[i][j]，则更新d[i][j]为d[i][k] + d[k][j]。
   • 以上更新操作对所有可能的k（从1到n，n为顶点数）进行迭代。

代码：

void Floyd_warshall(){vector<vector<W>> dis;vector<vector<int>> parentpath;int n = _vertices.size();dis.resize(n);parentpath.resize(n);// 初始化权值图// 初始化父路径图for (int i = 0; i < n; i++){dis[i].resize(n, INT_MAX);parentpath[i].resize(n, -1);}for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (_matrix[i][j] != INT_MAX){dis[i][j] = _matrix[i][j];// 默认i->j就是最短路径，所以j的上一级就是iparentpath[i][j] = i;}if (i == j)dis[i][j] = 0;}   }// 用k作为中转点，试图获取i->k->j的最短路径for (int k = 0; k < n; k++){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (dis[i][k] != INT_MAX && dis[k][j] != INT_MAX && dis[i][k] + dis[k][j] < dis[i][j]){dis[i][j] = dis[i][k] + dis[k][j];parentpath[i][j] = parentpath[k][j];}}}}}

结语

   本小节就到这里了，感谢小伙伴的浏览，如果有什么建议，欢迎在评论区评论，如果给小伙伴带来一些收获，请动动你发财的小手点个免费的赞，你的点赞和关注永远是博主创作的动力源泉。