免费搭建公司网站,网站群建设指南,百度seo关键词优化排行,网站建设费用 多少文章目录 前言并查集图遍历方法广度优先遍历深度优先遍历 最小生成树算法Kruskal算法Prim算法 最短路径算法Dijkstra算法BellmanFord算法FloydWarshall算法 全部代码链接 前言
图是真的难#xff0c;即使这些我都学过一遍#xff0c;再看还是要顺一下过程#xff1b;说明方… 文章目录 前言并查集图遍历方法广度优先遍历深度优先遍历 最小生成树算法Kruskal算法Prim算法 最短路径算法Dijkstra算法BellmanFord算法FloydWarshall算法 全部代码链接 前言
图是真的难即使这些我都学过一遍再看还是要顺一下过程说明方式按照 概念- 实现思想 - 代码逻辑 — 代码 的方式进行 图片多来自于《算法导论》 等书 后续可能会做更详细的补充
并查集
概念 并查集Disjoint Set是一种用于处理集合合并与查询问题的数据结构。它主要支持两种操作合并Union和查找Find。
在并查集中每个元素都被看作一个节点多个节点组成一个集合。每个集合通过一个代表元素来表示通常选择集合中的某个元素作为代表元素。
合并操作将两个不相交的集合合并成一个集合即将其中一个集合的代表元素指向另一个集合的代表元素。
查找操作用于确定某个元素所属的集合即找到该元素所在集合的代表元素。
通过这两种操作可以高效地判断两个元素是否属于同一个集合以及将不相交的集合合并成一个集合。
实现逻辑
下标代表节点下标内的值为负代表为根节点根节点的绝对值为该树的总节点个数下标内的值为正值代表的是其父亲节点的下标 实现代码
// 并查集代码
#include vectorclass DisiointSetUnion
{
private:std::vectorint _set; public://数组下标本身就是存储的内容//DSU为用一维数组抽象的森林可含多棵树//默认 -1 表示默认全为单独的根节点DisiointSetUnion(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;}}//判断两节点是否一颗树中bool InSet(int x1, int x2){int root1 FindRoot(x1);int root2 FindRoot(x2);if (root1 root2){return true;}else{return false;}}//计算有几个树// 通过计算负值数size_t SetCount(){size_t count 0 ;for (size_t i 0; i _set.size(); i){if (_set[i] 0){count;}}return count; }};图
基本概念 节点Vertex也称为顶点表示图中的元素。节点可以有附加的属性如权重、颜色等。
边Edge表示节点之间的连接关系。边可以是有向的有方向性或无向的无方向性。有向边由起始节点指向目标节点无向边没有方向。
路径Path是由边连接的节点序列。路径的长度是指路径上边的数量。
环Cycle是一条起始节点和终止节点相同的路径。
连通图Connected Graph如果图中任意两个节点之间都存在路径则称该图为连通图。
子图Subgraph由图中一部分节点和边组成的图。
权重Weight边可以有权重表示节点之间的关联程度或距离。
入度In-degree和出度Out-degree对于有向图入度表示指向该节点的边的数量出度表示从该节点出发的边的数量。
邻接点Adjacent Vertex与给定节点直接相连的节点
实现逻辑 代码实现
//邻接矩阵实现图//Direction为是否为有向图的标志位//INT_MAX为不存在的边的标识值// V 为顶点名类型 templateclass V, class W, W MAX_W INT_MAX, bool Direction falseclass Graph{private: //成员变量mapV, size_t _vIndexMap; // 存储顶点名与顶点在数组中的下标 顶点名-数组中下标vectorV _vertexs; // 存储顶点 下标—数组名vectorvectorW _matrix; // 图 //临界矩阵 // 此中建立边的关系public: //类内类//类内定义类Edge类是Graph类的友元struct Edge{size_t _srci; // 在有向图时为出发顶点size_t _dsti; // 在有向图时为目的顶点W _w; //权重Edge(size_t srci, size_t dsti, const W w):_srci(srci), _dsti(dsti), _w(w){}bool operator(const Edge eg){return _w eg._w;}bool operator(const Edge eg){return _w eg._w;}};public: // 成员方法 typedef GraphV, W, MAX_W, Direction Self;Graph() default;//只初始化节点没有边Graph(const V* vertexs, size_t n){_vertexs.reserve(n);// 对_vIndexMap 、 _vertexs 初始化for (size_t i 0; i n; i){_vertexs.push_back(vertexs[i]);_vIndexMap[vertexs[i]] i;}// 对 _matrix 初始化_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{printf( 查找顶点不存在\n);return -1;}}// 添加边被AddEdge函数调用void _AddEdge(size_t srci, size_t dsti, const W w){//发生了越界错误 //代码的逻辑有问题 _matrix[srci][dsti] w;if (Direction false){_matrix[dsti][srci] w;}}// 调用_AddEdge函数添加边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);}}遍历方法
广度优先遍历
实现逻辑 代码逻辑
代码实现 //测试运行成功//如果为不完全连通的图怎么办//src 为遍历的起始顶点//广度优先遍历//利用 队列 标记数组void BFS(const V src){size_t srcindex GetVertexIndex(src);vectorbool visted;visted.resize(_vertexs.size(), false);// true代表已经被遍历过//队列的作用类似与二叉树层序遍历中队列的作用queueint q;q.push(srcindex);visted[srcindex] true;size_t d 1; //代表广度遍历的层数 size_t dSize 1; //队列中剩余的顶点数while (!q.empty()){//只有当V为基础类型时此行代码才通用 cout src 的 d 度的好友 ;while (dSize--){size_t front q.front();q.pop();for (size_t i 0; i _matrix.size(); i){if (visted[i] false _matrix[front][i] ! MAX_W){只有当V为基础类型时此行代码才通用cout [ i : _vertexs[i] ];visted[i] true;q.push(i);}}}cout endl;dSize q.size();d;}cout endl;}深度优先遍历
实现逻辑 代码实现
//测试成功// 递归实现 //思想也是类似与二叉树的递归遍历//深度优先遍历void DFS(const V src){size_t srcindex GetVertexIndex(src);vectorbool visted;visted.resize(_vertexs.size(), false);_DFS(srcindex, visted);}//可以遍历不连通的树吗 //visited用于标志是否已经遍历过//深度优先遍历辅助函数void _DFS(size_t srcIndex, vectorbool visited){cout [ srcIndex _vertexs[srcIndex] ];visited[srcIndex] true;for (size_t i 0; i _vertexs.size(); i){if (visited[i] false _matrix[srcIndex][i] ! MAX_W){_DFS(i, visited);}}}最小生成树算法
概念 最小生成树Minimum Spanning Tree简称MST是一种在连通无向图中生成一棵树的算法使得这棵树包含了图中的所有节点并且边的权重之和最小。
最小生成树的特点是它是一个无环的连通子图其中包含了图中的所有节点并且边的权重之和最小。
Kruskal算法
概念: Kruskal算法Kruskal算法是一种贪心算法它按照边的权重从小到大的顺序逐步选择边如果选择某条边不会形成环则将该边加入到最小生成树中直到最小生成树中包含了所有的节点。
实现逻辑 代码实现
// Kruskal算法寻找最小生成树// 最小生成树是在已存在的连通图上找到把所有点连起来且总权重最小的N-1条边N为节点总数// 每次先找最小边再经判断是否构成回路确定是否连接顶点// 判断是否构成回路用并查集// 贪心算法寻找局部最优解 W Kruskal(Self minTree){size_t n _vertexs.size();minTree._vertexs _vertexs;minTree._vIndexMap _vIndexMap;minTree._matrix.resize(n); // 注意深浅拷贝for (size_t i 0; i n; i){//! ! ! ! !minTree._matrix[i].resize(n, MAX_W);}//创建一个堆用来快速找出最小路径priority_queueEdge, vectorEdge, Mygreater minque;for (size_t i 0; i n; i){for (size_t j 0; j n; j){//i j 这个条件的原因是: 生成最小生成树的依据原图为无向图//最小生成树本身也是无向的if (i j _matrix[i][j] ! MAX_W){minque.push(Edge(i, j, _matrix[i][j]));}}}//开始选边 判是否成环int size 0; // 计算是否满足 N - 1条边的条件W total W(); // 计算生成的最小生成树的总权重 并查集类对象DisiointSetUnion dsf(n);while (!minque.empty()){Edge min minque.top();minque.pop();if (!dsf.InSet(min._dsti, min._srci)){cout _vertexs[min._srci] - _vertexs[min._dsti] : min._w endl;minTree._AddEdge(min._srci, min._dsti, min._w);dsf.Union(min._srci, min._dsti);size;total min._w;}else{// 构成了环cout 成环: _vertexs[min._srci] - _vertexs[min._dsti] : min._w endl;}}if (size n - 1){return total;}else{return W();}}Prim算法
概念Prim算法Prim算法也是一种贪心算法它从一个起始节点开始逐步选择与当前最小生成树相邻的边中权重最小的边并将其加入到最小生成树中直到最小生成树中包含了所有的节点。
实现逻辑 代码实现
//Prim算法寻找最小生成树//src为生成最小生成树的起始点W Prim(Self minTree, const V src){size_t srci GetVertexIndex(src); // 不是给顶点名找下标的函数么…… // size_t n _vertexs.size(); minTree._vertexs _vertexs ;minTree._vIndexMap _vIndexMap; minTree._matrix.resize(n);for (size_t i 0; i n; i){minTree._matrix[i].resize(n, MAX_W);}// 记录是否已经被连接//为什么要有两个vectorbool X(n, false);vectorbool Y(n, true);X[srci] true; Y[srci] false;priority_queueEdge, vectorEdge, Mygreater minq;for (size_t i 0; i n; i){if (_matrix[srci][i] ! MAX_W){minq.push(Edge(srci, i, _matrix[srci][i]));}}//开始选边size_t size 0;W total W();while (!minq.empty()){Edge min minq.top();minq.pop();if (X[min._dsti]){//成环}else{minTree._AddEdge(min._srci, min._dsti, min._w);X[min._dsti] true;Y[min._srci] false;size;total min._w;if (size n - 1){//最多n-1条路break;}for (int i 0; i n; i){if (_matrix[min._dsti][i] ! MAX_W Y[i]) // ? ? ? Y[i]? ? ? {minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));}}}}if (size n - 1){return total;}else{return W();}}最短路径算法
概念最短路径算法用于找到两个节点之间的最短路径即路径上边的权重之和最小的路径。
Dijkstra算法
概念 Dijkstra算法Dijkstra算法是一种贪心算法用于解决单源最短路径问题即从一个给定的起始节点到图中所有其他节点的最短路径。算法维护一个距离数组记录从起始节点到每个节点的当前最短距离。算法每次选择距离起始节点最近的未访问节点并更新其邻接节点的最短距离。重复这个过程直到所有节点都被访问
注意不可处理存在负权值的图
实现逻辑 代码实现
//时间复杂度为多少 // Dijkstra 不考虑负路径的问题或者说无法处理父权值路径的图//Dijkstra 为最短路径算法//最短路径:即计算指定出发点到任意点的距离// dist 记录从出发点到该点的当前已更新的最短路径,注意是当前已更新的。 dist pPath 为输出参数void Dijkstra(const V src, vectorW dist, vectorint pPath){size_t srci GetVertexIndex(src);size_t n _vertexs.size();dist.resize(n, MAX_W);pPath.resize(n, -1);dist[srci] 0;pPath[srci] srci;// 已经确定的最短路径的集合// 满足什么条件确定最短路径不再更新 // 被置为true后就不会再更新吗 是 vectorbool S(n, false);for (size_t j 0; j n; j){// 1. 找出起始点直接连接的最短路径节点和其对应的权重// 用于记录/更新最短路径和该最短路劲对应的权重int u 0;W min MAX_W;// size_t v的for循环更新后会影响该循环结束时u的值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 dist[u] _matrix[u][v] dist[v]) /* 关键 */{dist[v] dist[u] _matrix[u][v];pPath[v] u; }}}}//不可用于打印FloydWarshall的结果//辅助打印最短路径结果void PrintShortPath(const V src, vectorW dist, vectorint pPath){size_t srci GetVertexIndex(src); size_t n _vertexs.size();for (size_t i 0; i n; i){size_t parent pPath[i];cout _vertexs[i] 到起始顶点 src 最小总权值为: dist[i] ——最短路径为:;cout _vertexs[i] -;while (parent ! srci){cout _vertexs[parent] - ;parent pPath[parent];}cout src endl;}}BellmanFord算法
概念 Bellman-Ford算法Bellman-Ford算法是一种动态规划算法用于解决单源最短路径问题可以处理带有负权边的图。算法维护一个距离数组记录从起始节点到每个节点的当前最短距离。算法通过对所有边进行松弛操作即尝试通过更新路径来减小距离数组中的值。重复这个过程直到没有可以更新的路径或者存在负权环。
时间复杂度分析 Dijkstra算法适用于没有负权边的图时间复杂度为O(V^2)或O((V E)logV)其中V是节点数E是边数。Bellman-Ford算法适用于带有负权边的图时间复杂度为O(VE)其中V是节点数E是边数。
实现逻辑 代码实现
/ BellmanFord的时间复杂度为多少 如何计算的 // BellmanFord可以处理负权值路径存在的场景 // 关于负权值环路的问题 : 不做考虑这种情况就没有最小权值路径权值延着负权值环路走会无限减小直到负无穷大// BellmanFord和Dijkstra的区别在于无确认该点为最短路径的这一动作 ;// 停止更新的条件: 1.是依据图的最大可更新次数停止更新 || 2.本次更新没有新的最短路径出现bool BellmanFord(const V src, vectorW dist, vectorint pPath){size_t n _vertexs.size(); size_t srci GetVertexIndex(src); dist.resize(n, MAX_W); pPath.resize(n, -1);// 更新出发顶点 srci 为缺省值0dist[srci] W();// 最多更新n轮 因为极端情况为所有顶点排成一条线for (size_t k 0; k n; k){bool update false;cout 第 k 轮更新 endl;for (size_t i 0; i n; i){for (size_t j 0; j n; j){// 实际上这个判断还隐含了条件 dist[i] MAX_W ! ! ! ! ! ! !// 因为这个隐含条件达到了类似广度优先向外遍历更新最短路径的效果if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]){update true;cout _vertexs[i] - _vertexs[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){if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]){cout 存在负权回路 endl;return false; }}}return true; }FloydWarshall算法
Floyd-Warshall算法的基本思想是通过中间节点逐步更新节点对之间的最短路径。算法维护一个二维数组D其中D[i][j]表示节点i到节点j的最短路径长度。算法的核心是使用三重循环对于每一对节点(i, j)和每一个可能的中间节点k尝试更新D[i][j]的值即通过节点k来缩短节点i到节点j的路径长度。
算法的具体步骤如下 初始化二维数组D将所有节点对之间的距离初始化为无穷大但将节点自身到自身的距离初始化为0。 对于每一个中间节点k遍历所有的节点对(i, j)尝试更新D[i][j]的值。更新的方式是比较D[i][j]的当前值和D[i][k] D[k][j]的和将较小的值赋给D[i][j]。 重复步骤2对于每一个中间节点k直到所有的节点对都被考虑过。 最终得到的二维数组D中D[i][j]表示节点i到节点j的最短路径长度。
Floyd-Warshall算法的时间复杂度为O(V^3)其中V是节点数。由于需要遍历所有的节点对和中间节点因此算法在处理大规模图时的效率可能较低。但它的优点是能够同时计算出所有节点对之间的最短路径适用于需要获取全局最短路径信息的场景例如网络路由算法中的链路状态路由协议。
实现逻辑
// FloydWarshall算法求最短路径// vvpPath 中的值的含义为 中间节点 如果不存在中间节点就是指原本直接相连的点 ? void FloydWarshall(vectorvectorW vvDist, vectorvectorint vvpPath){size_t n _vertexs.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();}}}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 为中间节点 if (vvDist[i][k] ! MAX_W vvDist[k][j] ! MAX_W vvDist[i][k] vvDist[k][j] vvDist[k][j]){vvDist[i][j] vvDist[i][k] vvDist[k][j]; vvpPath[i][j] vvpPath[k][j]; // ! ! ! ! !}}}//打印权值和路径for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (vvDist[i][j] MAX_W){printf(%3c, *);}else{printf(%3d, vvDist[i][j]);}}cout endl; }cout endl; for (size_t i 0; i n; i){for (size_t j 0; j n; j){printf(%3d, vvpPath[i][j]);}cout endl; }cout ———————————————— endl;}}全部代码链接
代码链接——gitee
