【数据结构】图
🌈个人主页：秦jh_-ZEEKLOG博客
🔥 系列专栏：《数据结构》https://blog.ZEEKLOG.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482
目录
前言
💬 hello! 各位铁子们大家好哇。
今日更新了图的相关内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
续上一篇《图和并查集》
图的遍历
广度优先遍历
广度优先遍历即BFS，相当于二叉树的层序遍历，一层一层往下遍历。BFS需要借助队列实现。如上图，先入A，然后把A拿出来，将他的邻接节点都入队列，即B、C、D入队列。再拿出队头B，入它的邻接节点E。注意：这里需要一个标记数组，当节点入队列时就标记，这样后面再遇到时就不要入队列了。
代码实现
void BFS(const V& src) { size_t srci = GetVertexIndex(src); //队列和标记数组 queue<int> q; vector<bool> visited(_vertexs.size(), false); q.push(srci); visited[srci] = true; size_t n = _vertexs.size(); while (!q.empty()) { int front = q.front(); q.pop(); cout << front << ":" << _vertexs[front] << endl; //把front顶点的邻接顶点入队列 for (size_t i = 0; i < n; i++) { if (_matrix[front][i] != MAX_W) { if (visited[i] == false) { q.push(i); visited[i] = true; } } } } cout << endl; }深度优先遍历
深度优先遍历即DFS，是将某一个节点的以某条路线一直遍历下去，直到无法继续遍历，就返回到上一层。这里需要用到递归。
代码实现
void _DFS(size_t srci, vector<bool>& visited) { cout << srci << ":" << _vertexs[srci] << endl; visited[srci] = true; //找一个srci相邻的没有访问过的点，去往深度遍历 for (size_t i = 0; i < _vertexs.size(); i++) { if (_matrix[srci][i] != MAX_W && visited[i] == false) _DFS(i, visited); } } void DFS(const V& src) { size_t srci = GetVertexIndex(src); vector<bool> visited(_vertexs.size(), false); _DFS(srci, visited); } 最小生成树
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树 就不在连通；反之，在其中引入任何一条新边，都会形成一条回路。
若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条：
- 只能使用图中权值最小的边来构造最小生成树
- 只能使用恰好n-1条边来连接图中的n个顶点
- 选用的n-1条边不能构成回路
构造最小生成树的方法：Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。 贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是 整体 最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。
Kruskal算法
任给一个有n个顶点的连通网络N={V,E}， 首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分量， 其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。
加了阴影的边属于不断增长的森林A。该算法按照边的权重大小依次进行考虑。箭头指向的边是算法每一步所考察的边。如果该条边将两棵不同的树连接起来，它就被加入到森林里，从而完成对两棵树的合并 。
部分代码实现:
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false> class Graph { typedef Graph<V, W, MAX_W, Direction> Self; public: 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); } 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& e) const { return _w > e._w; } }; //返回值：最小生成树的权值 W Kruskal(Self& minTree) { size_t n = _vertexs.size(); minTree._vertexs = _vertexs; minTree._indexMap = _indexMap; minTree._matrix.resize(n); for (size_t i = 0; i < n; i++) { minTree._matrix[i].resize(n, MAX_W); } priority_queue<Edge, vector<Edge>, greater<Edge>> minque; for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { if (i < j && _matrix[i][j] != MAX_W)//i<j:因为是无向图，主对角线是对称的，所以只需入一半即可，避免重复 { minque.push(Edge(i, j, _matrix[i][j])); } } } //选出n-1条边 int size = 0; W totalW = W(); UnionFindSet ufs(n); while (!minque.empty()) { Edge min = minque.top(); minque.pop(); if (!ufs.InSet(min._srci, min._dsti)) { //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] <<":" << min._w<< endl; minTree._AddEdge(min._srci, min._dsti, min._w); ufs.Union(min._srci, min._dsti); ++size; totalW += min._w; } else { //cout << "构成环:" ; //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl; } } if (size == n - 1) { return totalW; } else return W(); } private: vector<V> _vertexs;//顶点集合 map<V, int> _indexMap;//顶点映射下标 vector<vector<W>> _matrix;//邻接矩阵 };Prim算法
Prim算法的工作原理与Dijkstra的最短路径算法相似。Prim算法所具有的一个性质是集合A中的边总是构成一棵树。如下图所示，这棵树从一个任意的根结点r开始，一直长大到覆盖V中的所有结点时为止。算法每一步在连接集合A和A之外的结点的所有边中，选择一条轻量级边加人到A中。这条规则所加入的边都是对A安全的边。因此，当算法终止时，A中的边形成一棵最小生成树。本策略也属于贪心策略，因为每一步所加入的边都必须是使树的总权重增加量最小的边。
上图是执行Prim算法的过程。初始的根结点为α。加阴影的边和黑色的结点都属于树A。在算法每一步，树中的结点就决定了图的一个切割，横跨该切割的一条轻量级边被加入到树中。例如，在图中的第2步，该算法可以选择将边(b，c)加入到树中，也可以选择将边(a，h)加入到树中，因为这两条边都是横跨该切割的轻量级边。
Prim算法是局部的贪心，Kruskal算法是全局的贪心。
Prim算法的优势是，选的边不会形成环，不需要像Kruskal一样用并查集。因为他是从两个集合里来选的，已经选过的顶点就不会再选了，这样就能避开形成环了。
部分代码实现
W Prim(Self& minTree,const W& src) { size_t srci = GetVertexIndex(src); size_t n = _vertexs.size(); minTree._vertexs = _vertexs; minTree._indexMap = _indexMap; minTree._matrix.resize(n); for (size_t i = 0; i < n; i++) { minTree._matrix[i].resize(n, MAX_W); } /*set<int> X; set<int> Y; X.insert(srci); for (size_t i = 0; i < n; i++) { if (i != srci) { Y.insert(i); } }*/ vector<bool> X(n,false); vector<bool> Y(n,true); X[srci] = true; Y[srci] = false; //X->Y集合中连接的边里面选出最小的边 priority_queue<Edge, vector<Edge>, greater<Edge>> minq; //先把srci连接的边添加到队列中 for (size_t i = 0; i < n; i++) { if (_matrix[srci][i] != MAX_W) { minq.push(Edge(srci, i, _matrix[srci][i])); } } cout << "Prim开始选边" << endl; size_t size = 0; W totalW = W(); while (!minq.empty()) { Edge min = minq.top(); minq.pop(); //最小边的目标点也在x集合，则构成环 if (X[min._dsti]) { //cout << "构成环："; //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl; } else { minTree._AddEdge(min._srci, min._dsti, min._w); //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl; X[min._dsti]=true; Y[min._dsti]=false; ++size; totalW += min._w; if (size == n - 1) break; //把目标点的邻接边添加到队列中 for (size_t i = 0; i < n; i++) { if (_matrix[min._dsti][i] != MAX_W && Y[i]) { minq.push(Edge(min._dsti, i, _matrix[min._dsti][i])); } } } } if (size == n - 1) { return totalW; } else { return W(); } }最短路径
最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。
单源最短路径--Dijkstra算法
单源最短路径问题：给定一个图G = ( V ， E )，求源结点s ∈ V 到图中每个结点v ∈ V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用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 为空，即所有节点都已经查找过一遍并确定了最短路径，至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值，不发生变化。Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新，并加入S中，所以该算法使用的是贪心策略。
Dijkstra算法存在的问题是不支持图中带负权路径。
Dijkstra算法的执行过程。源结点s为最左边的结点。每个结点中的数值为该结点的最短路径的估计值，加了阴影的边表明前驱值。黑色的结点属于集合S。
过程解释：先选起始点s，s到s的最短路径是0，所以s的节点的值是0。接着找出它的邻接节点，分别是t和y，更新他们的节点值。然后从y和t中选最短路径的节点(即y)，找y的邻接节点，分别是t，z，x（注意：已经确定是最短路径的节点不用考虑，这里不用考虑s），因为y->t+s->y的距离小于s->t的距离，所以要更新t节点的值。后面的过程跟前面一样。
代码模拟
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath) { size_t srci = GetVertexIndex(src); size_t n = _vertexs.size(); dist.resize(n, MAX_W); //srci->其他顶点最短路径权值数组 pPath.resize(n, -1);//srci->其他顶点最短路径父顶点数组 dist[srci] = 0; pPath[srci] = srci; //已经确定最短路径的顶点集合 vector<bool> S(n, false); // n个顶点更新n次 for(size_t j=0;j<n;j++) { //选最短路径且不在S的顶点更新其他路径 int u = 0; W min = MAX_W; for (size_t i = 0; i < n; i++) { if (S[i] == false && dist[i] < min) { u = i; min = dist[i]; } } S[u] = true; //松弛更新u连接顶点v srci->u + u->v < srci->v 更新 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;//找到更短的路径后，更新该点的父亲 } } } }单源最短路径--Bellman-Ford算法
Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法 就不能帮助我们解决问题了，而bellman—ford算法可以解决负权图的单源最短路径问题。它的 优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显 的缺点，它的时间复杂度 O(N*E) (N是点数，E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里 如果我们使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是O(N^3)，这里也可以看出来Bellman-Ford就是一种暴力求解更新，缺点是效率比 Dijkstra算法低。
过程解释：Bellman-Ford算法是暴力的，每一次的松弛操作对边的处理次序都是:(t，x)，(t， y)，(t，z)，(y，x)，(y，z)，(z，x)，（z，s)，(s，t)，(s，y)。(a)在第1次松弛操作前的场景。(b)～(e)在对边进行每次松弛操作后的场景。图(e)为最终值。假设i->j表示图中所有的边，i->j是终止边，有路径s->i,i->j，如果s->i+i->j的距离小于s->j,就松弛更新，也就是把图中所有的边都暴力更新一遍。
注意：只要更新出了一条更短的路径，就可能影响其他路径，所以就要再更新一次来修正。
如果存在负权回路就会一直更新下去，因为会一直更新出更短的路径。
代码实现：
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath) { size_t n = _vertexs.size(); size_t srci = GetVertexIndex(src); // vector<W> dist,记录srci-其他顶点最短路径权值数组 dist.resize(n, MAX_W); // vector<int> pPath 记录srci-其他顶点最短路径父顶点数组 pPath.resize(n, -1); // 先更新srci->srci为缺省值 dist[srci] = W(); //cout << "更新边：i->j" << endl; //总体最多更新n轮，进行修正 for (size_t k = 0; k < n; k++) { //i->j更新松弛 bool update = false; cout << "跟新第:" << k << "轮" << endl; for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { //srci->i+i->j 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++) { //srci->i+i->j if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) { return false; } } } return true; }多源最短路径--Floyd-Warshall算法
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}取得的一条最短路径。
原理：
Floyd-Warshall算法的原理是动态规划。
设D [i][j][k]为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
1.若最短路径经过点k，则D [i][j][k] = D[i][k][k-1]+ D[k][j][k-1];
2.若最短路径不经过点k，则D [i][j][k]=D[i][j][k-1]。
因此，D [i][j][k] = min( D [i][j][k-1], D[i][k][k-1]＋D[k][j][k-1] )。
代码实现
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& 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] = 0; } } } //最短路径的更新i->{其他顶点}->j 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作为中间点尝试去更新i->j的路径 if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && vvDist[i][k] + vvDist[k][j] < vvDist[i][j]) { vvDist[i][j] = vvDist[i][k] + vvDist[k][j]; //找跟j相连的上一个邻接顶点 //如果k->j直接相连，上一个点就是k，vvpPath[k][j]存的就是k //如果k->j没有直接相连，k->...->x->j，vvpPath[k][j]存的就是x 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 << vvpPath[i][j] << " "; printf("%3d", vvpPath[i][j]); } cout << endl; } cout << "=================================" << endl; } }代码
本篇文章和上一篇文章有关图的所有代码如下：
#pragma once #include<vector> #include<map> #include<set> #include<string> #include<queue> #include<functional> namespace matrix { template<class V, class W, W MAX_W = INT_MAX, bool Direction = false> class Graph { typedef Graph<V, W, MAX_W, Direction> Self; public: Graph() = default; //图的创建 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 { cout << "不存在顶点:" << v << endl; 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 << "[" << i << "]" << "->" << _vertexs[i] << endl; } cout << endl; //矩阵 //横下标 cout << " "; for (size_t i = 0; i < _matrix.size(); i++) //cout << i << " "; printf("%4d", i); cout << endl; for (size_t i = 0; i < _matrix.size(); i++) { cout << i << " ";//竖下标 for (size_t j = 0; j < _matrix[i].size(); j++) { //cout << _matrix[i][j] << " "; if (_matrix[i][j] == MAX_W) //cout << "* "; printf("%4c", '*'); else //cout << _matrix[i][j] << " "; printf("%4d", _matrix[i][j]); } cout << endl; } cout << 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; } } } } void BFS(const V& src) { size_t srci = GetVertexIndex(src); //队列和标记数组 queue<int> q; vector<bool> visited(_vertexs.size(), false); q.push(srci); visited[srci] = true; size_t n = _vertexs.size(); while (!q.empty()) { int front = q.front(); q.pop(); cout << front << ":" << _vertexs[front] << endl; //把front顶点的邻接顶点入队列 for (size_t i = 0; i < n; i++) { if (_matrix[front][i] != MAX_W) { if (visited[i] == false) { q.push(i); visited[i] = true; } } } } cout << endl; } void _DFS(size_t srci, vector<bool>& visited) { cout << srci << ":" << _vertexs[srci] << endl; visited[srci] = true; //找一个srci相邻的没有访问过的点，去往深度遍历 for (size_t i = 0; i < _vertexs.size(); i++) { if (_matrix[srci][i] != MAX_W && visited[i] == false) _DFS(i, visited); } } void DFS(const V& src) { size_t srci = GetVertexIndex(src); vector<bool> visited(_vertexs.size(), false); _DFS(srci, visited); } 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& e) const { return _w > e._w; } }; //返回值：最小生成树的权值 W Kruskal(Self& minTree) { size_t n = _vertexs.size(); minTree._vertexs = _vertexs; minTree._indexMap = _indexMap; minTree._matrix.resize(n); for (size_t i = 0; i < n; i++) { minTree._matrix[i].resize(n, MAX_W); } priority_queue<Edge, vector<Edge>, greater<Edge>> minque; for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { if (i < j && _matrix[i][j] != MAX_W)//i<j:因为是无向图，主对角线是对称的，所以只需入一半即可，避免重复 { minque.push(Edge(i, j, _matrix[i][j])); } } } //选出n-1条边 int size = 0; W totalW = W(); UnionFindSet ufs(n); while (!minque.empty()) { Edge min = minque.top(); minque.pop(); if (!ufs.InSet(min._srci, min._dsti)) { //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] <<":" << min._w<< endl; minTree._AddEdge(min._srci, min._dsti, min._w); ufs.Union(min._srci, min._dsti); ++size; totalW += min._w; } else { //cout << "构成环:" ; //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl; } } if (size == n - 1) { return totalW; } else return W(); } W Prim(Self& minTree,const W& src) { size_t srci = GetVertexIndex(src); size_t n = _vertexs.size(); minTree._vertexs = _vertexs; minTree._indexMap = _indexMap; minTree._matrix.resize(n); for (size_t i = 0; i < n; i++) { minTree._matrix[i].resize(n, MAX_W); } /*set<int> X; set<int> Y; X.insert(srci); for (size_t i = 0; i < n; i++) { if (i != srci) { Y.insert(i); } }*/ vector<bool> X(n,false); vector<bool> Y(n,true); X[srci] = true; Y[srci] = false; //X->Y集合中连接的边里面选出最小的边 priority_queue<Edge, vector<Edge>, greater<Edge>> minq; //先把srci连接的边添加到队列中 for (size_t i = 0; i < n; i++) { if (_matrix[srci][i] != MAX_W) { minq.push(Edge(srci, i, _matrix[srci][i])); } } cout << "Prim开始选边" << endl; size_t size = 0; W totalW = W(); while (!minq.empty()) { Edge min = minq.top(); minq.pop(); //最小边的目标点也在x集合，则构成环 if (X[min._dsti]) { //cout << "构成环："; //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl; } else { minTree._AddEdge(min._srci, min._dsti, min._w); //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl; X[min._dsti]=true; Y[min._dsti]=false; ++size; totalW += min._w; if (size == n - 1) break; //把目标点的邻接边添加到队列中 for (size_t i = 0; i < n; i++) { if (_matrix[min._dsti][i] != MAX_W && Y[i]) { minq.push(Edge(min._dsti, i, _matrix[min._dsti][i])); } } } } if (size == n - 1) { return totalW; } else { return W(); } } void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath) { size_t srci = GetVertexIndex(src); size_t n = _vertexs.size(); //找到以每个点为起点的最短路径进行逆置 for (size_t i = 0; i < n; i++) { if (i != srci) { //找出i顶点的路径 vector<int> path; size_t parenti = i; while (parenti != srci) { path.push_back(parenti); parenti = pPath[parenti]; } path.push_back(srci); reverse(path.begin(), path.end()); for (auto index : path) { cout << _vertexs[index] << "->"; } cout << "权值和：" << dist[i] << endl; } } } void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath) { size_t srci = GetVertexIndex(src); size_t n = _vertexs.size(); dist.resize(n, MAX_W); //srci->其他顶点最短路径权值数组 pPath.resize(n, -1);//srci->其他顶点最短路径父顶点数组 dist[srci] = 0; pPath[srci] = srci; //已经确定最短路径的顶点集合 vector<bool> S(n, false); // n个顶点更新n次 for(size_t j=0;j<n;j++) { //选最短路径且不在S的顶点更新其他路径 int u = 0; W min = MAX_W; for (size_t i = 0; i < n; i++) { if (S[i] == false && dist[i] < min) { u = i; min = dist[i]; } } S[u] = true; //松弛更新u连接顶点v srci->u + u->v < srci->v 更新 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;//找到更短的路径后，更新该点的父亲 } } } } bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath) { size_t n = _vertexs.size(); size_t srci = GetVertexIndex(src); // vector<W> dist,记录srci-其他顶点最短路径权值数组 dist.resize(n, MAX_W); // vector<int> pPath 记录srci-其他顶点最短路径父顶点数组 pPath.resize(n, -1); // 先更新srci->srci为缺省值 dist[srci] = W(); //cout << "更新边：i->j" << endl; //总体最多更新n轮，进行修正 for (size_t k = 0; k < n; k++) { //i->j更新松弛 bool update = false; cout << "跟新第:" << k << "轮" << endl; for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { //srci->i+i->j 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++) { //srci->i+i->j if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) { return false; } } } return true; } void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& 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] = 0; } } } //最短路径的更新i->{其他顶点}->j 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作为中间点尝试去更新i->j的路径 if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && vvDist[i][k] + vvDist[k][j] < vvDist[i][j]) { vvDist[i][j] = vvDist[i][k] + vvDist[k][j]; //找跟j相连的上一个邻接顶点 //如果k->j直接相连，上一个点就是k，vvpPath[k][j]存的就是k //如果k->j没有直接相连，k->...->x->j，vvpPath[k][j]存的就是x 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 << vvpPath[i][j] << " "; printf("%3d", vvpPath[i][j]); } cout << endl; } cout << "=================================" << endl; } } private: vector<V> _vertexs;//顶点集合 map<V, int> _indexMap;//顶点映射下标 vector<vector<W>> _matrix;//邻接矩阵 }; void TestGraph1() { 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 TestDBFS() { string a[] = { "张三", "李四", "王五", "赵六", "周七" }; Graph<string, int> g1(a, sizeof(a) / sizeof(string)); g1.AddEdge("张三", "李四", 100); g1.AddEdge("张三", "王五", 200); g1.AddEdge("王五", "赵六", 30); g1.AddEdge("王五", "周七", 30); g1.Print(); g1.BFS("张三"); g1.DFS("张三"); } void TestGraphMinTree() { const char str[] = "abcdefghi"; Graph<char, int> g(str, strlen(str)); g.AddEdge('a', 'b', 4); g.AddEdge('a', 'h', 8); //g.AddEdge('a', 'h', 9); g.AddEdge('b', 'c', 8); g.AddEdge('b', 'h', 11); g.AddEdge('c', 'i', 2); g.AddEdge('c', 'f', 4); g.AddEdge('c', 'd', 7); g.AddEdge('d', 'f', 14); g.AddEdge('d', 'e', 9); g.AddEdge('e', 'f', 10); g.AddEdge('f', 'g', 2); g.AddEdge('g', 'h', 1); g.AddEdge('g', 'i', 6); g.AddEdge('h', 'i', 7); Graph<char, int> kminTree; cout << "Kruskal:" << g.Kruskal(kminTree) << endl; kminTree.Print(); cout << endl << endl; Graph<char, int> pminTree; cout << "Prim:" << g.Prim(pminTree,'a') << endl; pminTree.Print(); cout << endl; //分别以所有的点为起点走一遍，发现结果都是一样的。 for (size_t i=0;i<strlen(str);i++) { cout << "Prim:" << g.Prim(pminTree, str[i]) << endl; } } void TestGraphDijkstra() { //const char* str = "syztx"; //Graph<char, int, INT_MAX, true> g(str, strlen(str)); //g.AddEdge('s', 't', 10); //g.AddEdge('s', 'y', 5); //g.AddEdge('y', 't', 3); //g.AddEdge('y', 'x', 9); //g.AddEdge('y', 'z', 2); //g.AddEdge('z', 's', 7); //g.AddEdge('z', 'x', 6); //g.AddEdge('t', 'y', 2); //g.AddEdge('t', 'x', 1); //g.AddEdge('x', 'z', 4); //vector<int> dist; //vector<int> parentPath; //g.Dijkstra('s', dist, parentPath); //g.PrintShortPath('s', dist, parentPath); // 图中带有负权路径时，贪心策略则失效了。 //测试结果可以看到s->t->y之间的最短路径没更新出来 const char* str = "sytx"; Graph<char, int, INT_MAX, true> g(str, strlen(str)); g.AddEdge('s', 't', 10); g.AddEdge('s', 'y', 5); g.AddEdge('t', 'y', -7); g.AddEdge('y', 'x', 3); vector<int> dist; vector<int> parentPath; g.Dijkstra('s', dist, parentPath); g.PrintShortPath('s', dist, parentPath); } void TestGraphBellmanFord() { //const char* str = "syztx"; //Graph<char, int, INT_MAX, true> g(str, strlen(str)); //g.AddEdge('s', 't', 6); //g.AddEdge('s', 'y', 7); //g.AddEdge('y', 'z', 9); //g.AddEdge('y', 'x', -3); //g.AddEdge('z', 's', 2); //g.AddEdge('z', 'x', 7); //g.AddEdge('t', 'x', 5); //g.AddEdge('t', 'y', 8); //g.AddEdge('t', 'z', -4); //g.AddEdge('x', 't', -2); //vector<int> dist; //vector<int> parentPath; //g.BellmanFord('s', dist, parentPath); //g.PrintShortPath('s', dist, parentPath); // 微调图结构，带有负权回路的测试 const char* str = "syztx"; Graph<char, int, INT_MAX, true> g(str, strlen(str)); g.AddEdge('s', 't', 6); g.AddEdge('s', 'y', 7); g.AddEdge('y', 'x', -3); g.AddEdge('y', 'z', 9); g.AddEdge('y', 'x', -3); g.AddEdge('y', 's', 1); // 新增 g.AddEdge('z', 's', 2); g.AddEdge('z', 'x', 7); g.AddEdge('t', 'x', 5); g.AddEdge('t', 'y', -8); // 更改 g.AddEdge('t', 'z', -4); g.AddEdge('x', 't', -2); vector<int> dist; vector<int> parentPath; if (g.BellmanFord('s', dist, parentPath)) { g.PrintShortPath('s', dist, parentPath); } else { cout << "存在负权回路" << endl; } } void TestFloydWarShall() { const char* str = "12345"; Graph<char, int, INT_MAX, true> g(str, strlen(str)); g.AddEdge('1', '2', 3); g.AddEdge('1', '3', 8); g.AddEdge('1', '5', -4); g.AddEdge('2', '4', 1); g.AddEdge('2', '5', 7); g.AddEdge('3', '2', 4); g.AddEdge('4', '1', 2); g.AddEdge('4', '3', -5); g.AddEdge('5', '4', 6); vector<vector<int>> vvDist; vector<vector<int>> vvParentPath; g.FloydWarshall(vvDist, vvParentPath); // 打印任意两点之间的最短路径 for (size_t i = 0; i < strlen(str); ++i) { g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]); cout << endl; } } } namespace link_table { template<class W> struct Edge { //int _srci; int _dsti;//目标点的下标 W _w;//权值 Edge<W>* _next; Edge(int dsti,const W& w) :_dsti(dsti) ,_w(w) ,_next(nullptr) {} }; template<class V, class W,bool Direction = false> class Graph { typedef Edge<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); //1->2 //头插 Edge* eg = new Edge(dsti,w); eg->_next = _tables[srci]; _tables[srci] = eg; //2->1 if (Direction == false) { Edge* eg = new Edge(srci, w); eg->_next = _tables[dsti]; _tables[dsti] = eg; } } void Print() { //顶点 for (size_t i = 0; i < _vertexs.size(); i++) { cout << "[" << i << "]" << "->" << _vertexs[i] << endl; } cout << endl; for (size_t i = 0; i < _tables.size(); i++) { cout << _vertexs[i] << "[" << i << "]->"; Edge* cur = _tables[i]; while (cur) { cout <<"[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->"; cur = cur->_next; } cout << "nullptr" << endl; } } private: vector<V> _vertexs;//顶点集合 map<V, int> _indexMap;//顶点映射下标 vector<Edge*> _tables;//邻接表 }; void TestGraph1() { /*Graph<char, int, 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();*/ string a[] = { "张三", "李四", "王五", "赵六" }; Graph<string, int> g1(a, 4); g1.AddEdge("张三", "李四", 100); g1.AddEdge("张三", "王五", 200); g1.AddEdge("王五", "赵六", 30); g1.Print(); } } 
