-
图Graph
图的基本概念
1.图是什么？
图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)。其中：
- G表示图(Graph)。
- V表示顶点(Vertex)。
- E表示边(Edge)。
而：
- 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合。
- E = {(x,y)|x,y属于V}或者E = {
顶点和边：图中结点称为顶点，第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边，图中的第k条边记作ek，ek = (vi，vj)或
(x, y)表示x到y的一条双向通路，即(x, y)是无方向的；Path(x, y)表示从x到y的一条单向通路，即Path(x, y)是有方向的。(所以就有了图的两个结构，一个是有向图，一个是无向图)
2.有向图和无向图
①有向图和无向图：在有向图中，顶点对
②完全图：在有n个顶点的无向图中，若有n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图，比如下图G1；在n个顶点的有向图中，若有n * (n-1)条边，即任意两个顶点之间有且仅有方向相反的边，则称此图为有向完全图，比如下图G4。
所以：- 有向图是连接的线有方向。(要是两个节点只有一条通路，那么只通过这条路肯定是只有一个节点到达另一个节点，而另一个节点无法到达这个节点)
- 无向图是连接的线是无方向。(要是两个节点有一条通路，那么两个节点互通，就是两者都可以通过这个节点到达对方)
- 完全图就是图中每两个节点达到互通。
3.图的基本名词：
①邻接顶点：在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v；在有向图G中，若
②顶点的度：顶点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条边。
图的存储结构
因为在图中，它是一个由节点和边组成的结构，那么在图的存储结构中只需要保存节点和边就好了，那么就给出了以下两个结构取保存图：
邻接矩阵
1.邻接矩阵就可以解决这一问题，我们是这样设置的，让矩阵的长和宽成为其所在的顶点，而长和宽(也就是矩阵中某一个位置的长和宽)表示的是两个顶点间的关系，而该位置存储的大小就表示的是两个顶点间的长度。
所以是这样的：邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。
2.假设如下图示例：
这也就是我们所保存的情况。注意：
- 无向图的邻接矩阵是对称的，第i行或者i列元素之和，就是顶点i的度。
- 有向图的邻接矩阵则不一定是对称的，第i行或者i列元素之后就是顶点i的出或者入度。(行是出度，列是入度)
- 如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替(或者使用自己自定义的)。
- 用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通。
- 用邻接矩阵存储图的缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。(因为要遍历全部，对于大量的0的节点，那么就出现一些白遍历的情况，很浪费资源)
3.邻接矩阵的简单实现：
#include#include #include using namespace std; template<class T,class W,W MAX_W = INT_MAX,bool Direction = false> class Graph { public: Graph(const T* vertex,int n) //构造函数的主要内容，就是根据传入的顶点和尺寸进行成员 { //变量的尺寸安排 _vertex.reserve(n); for (int i = 0; i < n; ++i) { _vertex.push_back(vertex[i]); _vIndexMap[_vertex[i]] = i; } _matrix.resize(n); for (int i = 0; i < n; ++i) { _matrix[i].resize(n,MAX_W); } } size_t GetVerterIndex(const T& v) //查看该顶点是否存在 { auto ret = _vIndexMap.find(v); if (ret == _vIndexMap.end()) { throw invalid_argument("不存在的顶点"); return -1; } else { return ret->second; } } void AddEdge(const T src, const T dst, const W& w) { size_t srci = GetVerterIndex(src); size_t dsti = GetVerterIndex(dst); _matrix[srci][dsti] = w; if (Direction == false) //如果是无向图，那么就是对称的 { _matrix[dsti][srci] = w; } } void Print() { //打印顶点 for (int i = 0; i < _vertex.size(); ++i) { cout << "[" << i << "]" << "->" << _vertex[i] << endl; } //打印矩阵 for (int i = 0; i < _matrix.size(); ++i) { for (int j = 0; j < _matrix[i].size(); ++j) { if (_matrix[i][j] == MAX_W) { cout << "0 "; } else { cout << _matrix[i][j] << " "; } } cout << endl; } } private: vector<T> _vertex; unordered_map<T, int> _vIndexMap; vector<vector<int>> _matrix; }; - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
邻接表
邻接表：使用数组表示顶点的集合，使用链表表示边的关系。
1.无向图邻接表存储
如上图，对于邻接表的存储，无非就是使用一个向量结构保存每个节点的顶点，然后用链表去存储每个节点的顶点可以到达的其他顶点。注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点vi边链表集合中结点的数目即可。
2.有向图邻接表的存储
对于有向图，因为有了方向，所以每条边只在邻接表中出现了一次，而与顶点vi对应的邻接表所含结点的个数，就是该顶点的出度，也称出度，表如上图所示。而要得到vi顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的dst取值是i，或者直接在每个顶点的链表中找到自己要查看入度的顶点的个数，或者直接建立一个入度表。3.邻接表的实现
①要实现邻接表，我们必须要有一个结构体，去保存链表的节点，而这个节点中要保存的数据无非只有三个，一个是该节点的下标，一个是该边的权值大小，一个就是下一个节点的指针，所以实现如下：
template<class W> struct Edge //边 { int dsti; //目标点的下标 W _w; //权值大小 Edge<W>* _next; Edge(const int dst, const W& w) :dsti(dst) , _w(w) , _next(nullptr) {} };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
②邻接表整体的具体实现：
template<class T, class W, bool Direction = false> class Graph { typedef Edge<W> Edge; public: Graph(const T* vertex, int n) //构造函数的主要内容，就是根据传入的顶点和尺寸进行成员 { //变量的尺寸安排 _vertex.reserve(n); for (int i = 0; i < n; ++i) { _vertex.push_back(vertex[i]); _vIndexMap[_vertex[i]] = i; } _linktable.resize(n, nullptr); } size_t GetVerterIndex(const T& v) //查看该顶点是否存在 { auto ret = _vIndexMap.find(v); if (ret == _vIndexMap.end()) { throw invalid_argument("不存在的顶点"); return -1; } else { return ret->second; } } void AddEdge(const T src, const T dst, const W& w) { //获取正确的源端和目的端 size_t srci = GetVerterIndex(src); size_t dsti = GetVerterIndex(dst); //入表 Edge* sd_edge = new Edge(dsti,w); sd_edge->_next = _linktable[srci]; _linktable[srci] = sd_edge; //如果是无向图 if (Direction == false) { Edge* ds_edge = new Edge(srci, w); ds_edge->_next = _linktable[dsti]; _linktable[dsti] = ds_edge; } } void Print() { //打印顶点 for (int i = 0; i < _vertex.size(); ++i) { cout << "[" << i << "]" << "->" << _vertex[i] << endl; } //打印邻接表 for (int i = 0; i < _vertex.size(); ++i) { cout << "[" << i << "]" << "->"; Edge* ed = _linktable[i]; while (ed != nullptr) { cout << "[" << ed->dsti << "]" << "[" << ed->_w << "]" << "->"; ed = ed->_next; } cout << "nullptr" << endl; } } private: vector<T> _vertex; unordered_map<T, int> _vIndexMap; vector<Edge*> _linktable; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
图的遍历
给定一个图G和其中一个顶点v0，要求从v0出发，沿着边将图中所有的顶点都访问一遍，且每个顶点只被访问一次。(注意这个情况下，图一定是没有孤立顶点的)
而对于图的遍历，其实和树的遍历方法差不多，都是通过深度和广度两个方法进行的，如下：
图的广度优先遍历（BFS）
1.广度优先遍历，我们先看二叉树的广度优先遍历，它的遍历是从根节点开始，一层一层的往下遍历，也就是将一层的节点遍历完，然后遍历下一层的节点。
所以，图的广度优先遍历，也和其差不多，而图的广度优先遍历相比于二叉树的广度优先遍历，只是将二叉树的几层换成了图的几度，而几度也就对应的从该节点出发，通过几条线能到达我们目标的节点。
如下图：
2.广度优先遍历的实现
void BFS(const T& src) { size_t srci = GetVerterIndex(src); vector<bool> sign(_vertex.size(),false); //标记数组，标记当前这个位置是否遍历过 queue<int> q; //队列 q.push(srci); sign[srci] = true; while (!q.empty()) { int cur = q.front(); q.pop(); cout << "[" << cur << "]" << ":" << _vertex[cur] << "->"; for (int i = 0; i < _matrix[cur].size(); ++i) { if (_matrix[cur][i] != MAX_W && sign[i] != true) //是否可以入队 { q.push(i); sign[i] = true; } } } cout << "nullptr" << endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
图的深度优先遍历（DFS）
1.图的深度优先遍历：深度优先遍历我们在二叉树也学习过，是从一个节点出发，直接遍历到子节点，然后回来，再遍历其他的节点，也就是通过递归实现的，而图的深度优先遍历也是如此，从一个节点出发，一直遍历到不能遍历的节点，然后返回来重新选择新的路径继续遍历。
如下图：
2.深度优先遍历的实现：
void _DFS(size_t src, vector<bool>& sign) { cout << "[" << src << "]" << ":" << _vertex[src] << "->"; sign[src] = true; for (int i = 0; i < _matrix[src].size(); ++i) { if (_matrix[src][i] != MAX_W && sign[i] != true) //如果这条线存在，并且连接的点还没有被遍历 { _DFS(i, sign); } } } void DFS(const T& src) { size_t srci = GetVerterIndex(src); vector<bool> sign(_vertex.size(), false); _DFS(srci, sign); cout << "nullptr" << endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
最小生成树
生成树概念：连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不在连通；反之，在其中引入任何一条新边，都会形成一条回路。
所以，若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条：
- 只能使用图中的权值最小的边来构造最小生成树。
- 只能使用恰好n-1条边来连接图中的n个顶点。
- 选用的n-1条边不能构成回路。
所以构造最小生成树的方法：Kruskal算法和Prim算法。(这两个算法都使用了贪心算法的思想来实现的)
Kruskal算法
1.算法理解：
①：任给一个有n个顶点的连通网络N={V,E}。
②：首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分量。
③：其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。
2.通过上面的算法理解，我们看这个图：
在连通图中，每次选取的是权值最小的那个边，然后依次往后进行，直到所有的顶点通过顶点数量-1条边相连即可。注意，这个实现还是有难点的，因为在实现中不能出现环的情况，但是如果是按权值大小依次往后取，那么必然会出现环的情况，所以我们要解决这样的情况。而解决办法就是引入并查集结构，将以及连通的两个顶点放入到一个集合中，然后每次加入新的节点的时候，判断其是否已经在这个集合中了。
3.Kruskal算法的实现：
实现思路：
- 通过优先队列去给权值边排序。
- 依次选取权值边。
- 将不构成环的边加入到最小数中。(通过两个节点是否在同一集合中查看是否构成环，通过并查集实现)
struct Edge //为了更好的排序边，我们定义一个边的结构 { size_t srci; //起始边 size_t dsti; //终点边 W _w; //权值大小 Edge(int& src,int& dst,const int& w) :srci(src) ,dsti(dst) ,_w(w) {} bool operator>(const Edge& e)const //重载>号，因为默认是小于的 { return _w > e._w; } }; W Kruskal(Self& minTree) { int n = _vertex.size(); minTree._vertex = _vertex; minTree._vIndexMap = _vIndexMap; minTree._matrix.resize(n); for (int i = 0; i < n; ++i) { minTree._matrix[i].resize(n, MAX_W); } priority_queue<Edge,vector<Edge>,greater<Edge>> minque; //建立优先队列，排列带权值 for (int i = 0; i < n; ++i) { for (int j = 0; j < _matrix[i].size(); ++j) { if (i < j &&_matrix[i][j] != MAX_W) //i- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
Prim算法
1.算法理解:Prim算法的本质其实和Kruskal算法的本质是差不多的，但是Prim算法的提高的一点就是，它要给一个源顶点，然后我们通过这个源顶点出发，然后去寻找一个最小生成树。
2.通过图来看算法：
如上图，我们能看出Prim算法的操作：- 选取一个点，成为树的根节点，然后开始往下去连接点。
- 每次选取当前已在树中的节点中去取权值最小的节点去连接到数中。
注意：这样取的时候有可能会发生环的情况，所以我们在保存的时候直接用了一个向量进行保存：
vector<bool> X; //表示的是已经加入树中的节点- 1
这样每次就从Y中选择节点加入到X中，就不会出现环的情况，因为每次加入的节点都是新的节点，绝对不可能构成环。
- 直到Y中的节点个数为0了，那么就遍历出来最小生成树了。
3.Prim算法的实现：
①：首先，和Kruskal算法的实现一样，我们要先定义一个Edge的结构体，去保存一条边的同时，将这条边的顶点和权值大小也保存起来，方便优先队列对其进行排序和我们对取权值小的边时对顶点的选取变得方便起来。
struct Edge //为了更好的排序边，我们定义一个边的结构 { size_t srci; //起始边 size_t dsti; //终点边 W _w; //权值大小 Edge(size_t& src,size_t& dst,const int& w) :srci(src) ,dsti(dst) ,_w(w) {} bool operator>(const Edge& e)const //重载>号，因为默认是小于的 { return _w > e._w; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
②：Prim算法的实现：
W Prim(Self& minTree, const T& src) { size_t n = _vertex.size(); //初始化minTree结构，防止越界 minTree._vertex = _vertex; minTree._vIndexMap = _vIndexMap; minTree._matrix.resize(n); for (int i = 0; i < n; ++i) { minTree._matrix[i].resize(n, MAX_W); } size_t srci = GetVerterIndex(src); vector<bool> X(n,false); //定义一个向量，保存已经加入的节点 priority_queue<Edge, vector<Edge>, greater<Edge>> minque; for (size_t i = 0; i < n; ++i) { if (_matrix[srci][i] != MAX_W) { minque.push(Edge(srci, i, _matrix[srci][i])); } } X[srci] = true; W totalW = W(); size_t min_size = 0; while (!minque.empty()) { Edge e = minque.top(); minque.pop(); if (X[e.dsti] == true) //防止环，为true，证明该点已经在树中了 { continue; } else { minTree._AddEdge(e.srci, e.dsti, e._w); X[e.dsti] = true; totalW += e._w; min_size++; for (size_t i = 0; i < n; ++i) //加入目标点所连接的边 { if (X[i] != true && _matrix[e.dsti][i] != MAX_W) { minque.push(Edge(e.dsti, i, _matrix[e.dsti][i])); } } } } if (min_size != n - 1) { return W(); } return totalW; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
最短路径问题
最短路径问题：其实就是从带有权值的有向图G中的某一个顶点出发，找出一条路通路通往另外一条路，并且从该顶点出发，到达另一个顶点路径的权值最小。(其实就是给定一个顶点，从该顶点出发，找出到达每个顶点的所有最小权值和的路径)
单源最短路径–Dijkstra算法
1.单源最短路径问题：给定一个图G = ( V ， E )，求源结点s ∈ V到图中每个结点v ∈ V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。
注意：上面说到，Dijkstra算法只能适用于图中的所有权值的大小都是正数，不能存在有权值大小为负数的情况，我们下面会进行解释。
2.算法理解和大体过程：
①理解：对于Dijkstra算法来说，其实就是给定一个初始顶点，然后我们需要根据初始顶点去找路径，找到其到达其他任意一个顶点的最短路径(路径上的权值和最小)，然后找的办法其实就是从第一个顶点出发，然后选取该顶点所连接到的最小权值的边，然后找到下一个顶点，此时这两个顶点的最短路径已经找到了，然后根据新加入的边然后继续去以同样的步骤操作，直到找到所有的顶点的最小路径。（注意：其中有个更新节点，就是与已经确认节点直接相连的节点是否比通过其他拐弯的路径大，而要实行更新操作，这个会在下面步骤的时候讲到）
②步骤：
- 针对一个带权有向图G，将所有结点分为两组S和Q，S是已经确定最短路径的结点集合。（在初始时为空（初始时就可以将源节点s放入，毕竟源节点到自己的代价是0），Q 为其余未确定最短路径的结点集合）
- 每次从Q 中找出一个起点到该结点代价最小的结点u ，将u 从Q 中移出，并放入S中，对u 的每一个相邻结点v 进行松弛操作。
松弛操作：也就是上面的更新操作，对每一个相邻结点v ，判断源节点s到结点u的代价与u 到v 的代价之和是否比原来s 到v 的代价更小，若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和，否则维持原样。 - 如此一直循环直至集合Q 为空，即所有节点都已经查找过一遍并确定了最短路径，至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值，不发生变化。
③如下图：
该图的内容就是以s为起点，然后找到s点到其他任意顶点的最短路径。3.Dijkstra算法的具体实现：
void Dijkstra(const T& src,vector<W>& dist,vector<int>& pPath) { int n = _vertex.size(); size_t srci = GetVerterIndex(src); dist.resize(n, MAX_W); //目标节点到达其他任意节点的路径权值和 pPath.resize(n, -1); //每个节点的父节点，其实就是从哪个节点出发到自己的下标 dist[srci] = 0; vector<bool> S(n,false); //标记已经是最短路径的下标 S[srci] = true; for (int i = 0; i < n; ++i) { W min_w = MAX_W; size_t u = srci; for (int j = 0; j < n; ++j) //选择当前节点所连接的最小权值路径 { if (S[j] != true && min_w > dist[j]) //必须是没有确定的最小权值路径 { min_w = dist[j]; u = j; } } S[u] = true; //更新与u连的所有边的大小 for (size_t k = 0; k < n; ++k) { if (S[k] != true && _matrix[u][k] != MAX_W && dist[k] > dist[u] + _matrix[u][k]) { dist[k] = dist[u] + _matrix[u][k]; pPath[k] = u; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
然后我们再实现一个打印最短路径的函数：
// 打印最短路径的逻辑算法 void PrinrtShotPath(const T& src, const vector<W>& dist, const vector<int>& pPath) { size_t N = _vertex.size(); size_t srci = GetVerterIndex(src); for (size_t i = 0; i < N; ++i) { if (i == srci) continue; vector<int> path; int parenti = i; while (parenti != srci) { path.push_back(parenti); parenti = pPath[parenti]; } path.push_back(srci); reverse(path.begin(), path.end()); //反转的原因是因为每次添加该节点的上一个节点 for (auto pos : path) //都是尾插 { cout << _vertex[pos] << "->"; } cout << dist[i] << endl; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
然后我们打印上图的内容如下：
如上图，情况相同。4.为什么Dijkstra算法不适合有负权值路径？
答：因为对于Dijkstra算法的，它的开始是直接确定与连接初始节点的间权值最小的节点就是最小路径，但是如果说此时，存在负权路径，那么就会出现如下图这样的情况：
假设初始点是a，如果我们使用Dijkstra算法，那么第一步就会直接选择c节点，然后c节点的路径大小就被确定为4了(证明c不会再更改了)，但是如果a走到b再走到c，那么权值大小就为3，比4小，那么就出错了。单源最短路径–Bellman-Ford算法
1.Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而bellman—ford算法可以解决负权图的单源最短路径问题。它的优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显的缺点，它的时间复杂度 O(N*E) (N是点数，E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里如果我们使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是O(N^3)，这里也可以看出来Bellman-Ford就是一种暴力求解更新。 (Bellman-Ford算法出现的主要原因，就是为了去解决Dijkstra中出现负权值路径而不能解决的问题。)
2.Bellman-Ford算法的思想
①：主要是通过暴力遍历的方法进行，因为存在负数路径，所以一次遍历是无法确定这个节点是否已经是最短路径了，所以必须得循环一次后，才能进行，但是要注意的是，如果说只要权值路径中存在负权值路径，那么这个最短路径是绝对可以优化的，因为我们目前已经找到的都已经是我们目前存在的最小路径，而此时如果还存在负权值在路径中，那么肯定必须再循环，直到我们所找的权值路径中没有负权值的存在。‘②如下图：
3.Bellman-Ford算法的简单实现：bool BellmanFord(const T& src, vector<W>& dist, vector<int>& pPath) { size_t n = _vertex.size(); size_t srci = GetVerterIndex(src); dist.resize(n, MAX_W); //源点到每个点的路径大小，先初始化为最大 pPath.resize(n, -1); //该点的路径 dist[srci] = W(); //权值最小值 for (size_t k = 0; k < n; ++k) //三次遍历的原因是，如果说每次遍历完成后，如果该次遍历的最小 { //路径中存在负权值，那么就又必须得重新遍历，因为有负权值 bool exchage = false; //就有再次寻找最短路径的可能。 for (size_t i = 0; i < n; ++i) //对每个起点进行一次遍历(因为是二维，所以双循环) { //是必须的 for (size_t j = 0; j < n; ++j) { //如果说此时从srci到j的距离 大于srci 到i再到j的距离，那么就要更新 if (_matrix[i][j] != MAX_W && dist[j] > dist[i] + _matrix[i][j]) { dist[j] = dist[i] + _matrix[i][j]; pPath[j] = i; exchage = true; } } } if (exchage == 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[j] > _matrix[i][j] + dist[i]) { return false; } } } return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
然后我们测试上图结果，如下：
但是我们发现，Bellman-Ford算法的时间复杂度太高了，所以有专家就提供了一个可以让其降低时间复杂度的方法--------->SPFA算法(SPFA 算法是Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)。)
多源最短路径–Floyd-Warshall算法
1.Floyd-Warshall算法：是解决任意两点间的最短路径的一种算法。
①：Floyd算法考虑的是一条最短路径的中间节点，即简单路径p={v1,v2,…,vn}上除v1和vn的任意节点。
②：设k是p的一个中间节点，那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1，p2。p1是从i到k且中间节点属于{1，2，…，k-1}取得的一条最短路径。p2是从k到j且中间节点属于{1，2，…，k-1}取得的一条最短路径。
2.Floyd-Warshall算法的原理：
其实就是使用了动态规划的思想。
即Floyd算法本质是三维动态规划，D[i][j][k]表示从点i到点j只经过0到k个点最短路径，然后建立起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得到所以点的最短路。3.Floyd-Warshall算法的实现:
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath) { size_t n = _vertex.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] = 0; } } } for (size_t k = 0; k < n; ++k) //k为中间任意一个节点 { for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && vvDist[i][j] > vvDist[i][k] + vvDist[k][j]) //如果说通过k节点路径更短 { //就要替换 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) // { // //cout << "*" << " "; // printf("%3c", '*'); // } // else // { // //cout << vvDist[i][j] << " "; // 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) // { // //cout << vvParentPath[i][j] << " "; // printf("%3d", vvpPath[i][j]); // } // cout << endl; // } // cout << "=================================" << endl; //} }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
然后测试下图：
所得结果如下：
-
相关阅读:
使用element的过渡效果来做动效
WebView2 通过 PuppeteerSharp 实现爬取 王者 壁纸 (案例版)
【原创】ubuntu18修改IP地址
YbtOJ「动态规划」第2章 区间DP
integral函数Opencv源码理解-leetcode动态规划的使用场景
C++ 语法基础课 习题1 —— 变量、输入输出、顺序语句
今天跟蚂蚁金服安全同学聊聊WAF
算法学习笔记(21): 平衡树（二）
【完整解决方案】生产实战，数据库发生了死锁
Haproxy负载均衡
- 原文地址：https://blog.csdn.net/xiaobai_hellow/article/details/126651058
