【高阶数据结构】图 -- 详解（上）https://developer.aliyun.com/article/1515768?spm=a2c6h.13148508.setting.28.11104f0e63xoTy
四、最小生成树
最小生成树：构成生成树的所有边加起来的权值是最小的（最小成本让这 n 个点相连）。
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。
若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n-1 条边。因此构造最小生成树的准则有三条：
- 只能使用图中权值最小的边来构造最小生成树。
- 只能使用恰好 n-1 条边来连接图中的 n 个顶点。
- 选用的 n-1 条边不能构成回路。
构造最小生成树的方法： Kruskal 算法和 Prim 算法。这两个算法都采用了逐步求解的 贪心 策略。
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是
整体最优的的选择，而是某种意义上的 局部最优解 。贪心算法不是对所有的问题都能得到整体最优解。
1、Kruskal 算法
任给一个有 n 个顶点的连通网络 N={V, E}，首先构造一个由这 n 个顶点组成、不含任何边的图 G={V, NULL}，其中每个顶点自成一个连通分量，其次不断从 E 中取出权值最小的一条边（若有多条任取其一），若该边的两个顶点来自不同的连通分量，则将此边加入到 G 中。如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。
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) { 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(); } 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(); }
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 < _vertexs.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; } } } }
2、Prim 算法
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); } 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 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> 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; } }
五、最短路径
最短路径问题：从在带权有向图 G 中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。
1、单源最短路径 —— 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 算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径。
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); pPath.resize(n, -1); dist[srci] = 0; pPath[srci] = srci; // 已经确定最短路径的顶点集合 vector<bool> S(n, false); 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 (_matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) { dist[v] = dist[u] + _matrix[u][v]; pPath[v] = u; } } } } 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); }
void TestGraphDijkstra() { 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); }
图中带有负权路径时，上面的贪心策略就失效了，从测试结果可以看到 s->t->y 之间的最短路径没更新出来：
修改代码如下：
2、单源最短路径 —— Bellman-Ford 算法
Dijkstra 算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而 Bellman—ford 算法 可以解决负权图的单源最短路径问题。
它的优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显的缺点，它的时间复杂度 O(N*E)（N 是点数，E 是边数）普遍是要高于 Dijkstra 算法 O(N²) 的。像这里如果我们使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是 O(N^3)，这里也可以看出来 Bellman-Ford 就是一种暴力求解更新。
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 TestGraphBellmanFord1() { 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; if (g.BellmanFord('s', dist, parentPath)) g.PrintShortPath('s', dist, parentPath); else cout << "存在负权回路" << endl; } void TestGraphBellmanFord2() { 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('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; }
3、多源最短路径 —— 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 算法本质是三维动态规划，D[i][j][k] 表示从点 i 到点 j 只经过 0 到 k 个点最短路径，然后建立起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得到所以点的最短路。
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] = W(); } } } // abcdef a {} f || b {} c // 最短路径的更新：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 << vvParentPath[i][j] << " "; printf("%3d", vvpPath[i][j]); } cout << endl; } 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; } }
