devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++ 图的遍历_c++图的遍历

作者：从前慢现在也慢 | 2024-04-10 13:30:11

赞

踩

c++图的遍历

1. 图的遍历

给定一个图 G 和其中任意一个顶点 v0 ，从 v0 出发，沿着图中各边访问图中的所有顶点，且每个顶 点仅被遍历一次 。 " 遍历 " 即对结点进行某种操作的意思 。 请思考树以前是怎么遍历的，此处可以直接用来遍历图吗？为什么？

1.1 图的广度优先遍历

 

 

问题：如何防止节点被重复遍历 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <queue>
  5. #include <climits>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
  10.  
  11. class Graph
  12. {
  13.  
  14. public:
  15.     typedef Graph<V, W, MAX_W, Direction> Self;
  16.     Graph() = default;
  17.     Graph(const V *vertexs, size_t n)
  18.     {
  19.         // reverse 只是预留了，没有做填充。resize() 是做了填充的，默认是用0 做了填充，
  20.         _vertexs.reserve(n);
  21.         for (size_t i = 0; i < n; i++)
  22.         {
  23.             _vertexs.push_back(vertexs[i]);
  24.             _vIndexMap[_vertexs[i]] = i;
  25.         }
  26.         //将MAX_W 作为一个边部存在 的标示值
  27.         _matrix.resize(n);
  28.         for (auto &e : _matrix)
  29.         {
  30.             e.resize(n, MAX_W);
  31.         }
  32.     }
  33.  
  34.     //输入顶点获取顶点的边的数量
  35.     size_t GetVertexIndex(const V &v)
  36.     {
  37.         auto ret = _vIndexMap.find(v);
  38.         if (ret != _vIndexMap.end())
  39.         {
  40.             return ret->second;
  41.         }
  42.         else
  43.         {
  44.             throw invalid_argument("不存在顶点");
  45.             return -1;
  46.         }
  47.     }
  48.  
  49.     void _AddEdge(size_t srci, size_t dsti, const W &w)
  50.     {
  51.  
  52.         _matrix[srci][dsti] = w;
  53.         if (Direction == false)
  54.         {
  55.             _matrix[dsti][srci] = w;
  56.         }
  57.     }
  58.  
  59.     void AddEdge(const V &src, const V &dst, const W &w)
  60.     {
  61.         size_t srci = GetVertexIndex(src);
  62.         size_t dsti = GetVertexIndex(dst);
  63.         _AddEdge(srci, dsti, w);
  64.     }
  65.  
  66.     void Print()
  67.     {
  68.         // 打印顶点和下标映射关系
  69.         for (size_t i = 0; i < _vertexs.size(); ++i)
  70.         {
  71.             cout << _vertexs[i] << "-" << i << " ";
  72.         }
  73.         cout << endl
  74.              << endl;
  75.         cout << " ";
  76.         for (size_t i = 0; i < _vertexs.size(); ++i)
  77.         {
  78.             cout << i << " ";
  79.         }
  80.         cout << endl;
  81.         // 打印矩阵
  82.         for (size_t i = 0; i < _matrix.size(); ++i)
  83.         {
  84.             cout << i << " ";
  85.             for (size_t j = 0; j < _matrix[i].size(); ++j)
  86.             {
  87.                 if (_matrix[i][j] != MAX_W)
  88.                     cout << _matrix[i][j] << " ";
  89.                 else
  90.                     cout << "#"
  91.                          << " ";
  92.             }
  93.             cout << endl;
  94.         }
  95.         cout << endl
  96.              << endl;
  97.         // 打印所有的边
  98.         for (size_t i = 0; i < _matrix.size(); ++i)
  99.         {
  100.             for (size_t j = 0; j < _matrix[i].size(); ++j)
  101.             {
  102.                 if (i < j && _matrix[i][j] != MAX_W)
  103.                 {
  104.                     cout << _vertexs[i] << "-" << _vertexs[j] << ":" << _matrix[i][j] << endl;
  105.                 }
  106.             }
  107.         }
  108.     }
  109.  
  110.     void Bfs(const V &src)
  111.     {
  112.  
  113.         size_t srcindex = GetVertexIndex(src);
  114.         vector<bool> visited(_matrix.size(), false);
  115.         size_t n = _matrix.size();
  116.         queue<size_t> q;
  117.         q.push(srcindex);
  118.  
  119.         visited[srcindex] = true;
  120.         size_t d = 1;
  121.         size_t dSize = 1;
  122.  
  123.         while (!q.empty())
  124.         {
  125.  
  126.             printf("%s degree%d", src.c_str(), d);
  127.  
  128.             while (dSize--)
  129.             {
  130.                 size_t front = q.front();
  131.                 q.pop();
  132.                 for (size_t i = 0; i < _vertexs.size(); i++)
  133.                 {
  134.                     if (visited[i] == false && _matrix[front][i] != MAX_W)
  135.                     {
  136.                         printf("[%d:%s]", i, _vertexs[i].c_str());
  137.                         visited[i] = true;
  138.                         q.push(i);
  139.                     }
  140.                 }
  141.             }
  142.  
  143.             cout << endl;
  144.             dSize = q.size();
  145.             ++d;
  146.         }
  147.         cout << endl;
  148.     }
  149.  
  150. private:
  151.     //将传入我V 类型（本例是string)和对应的索引编号对应上。
  152.     map<V, size_t> _vIndexMap;
  153.     vector<V> _vertexs;        //顶点集合
  154.     vector<vector<W>> _matrix; //存储边集合的矩阵
  155. };
  156.  
  157. int main()
  158. {
  159.  
  160.     // Graph<char, int, INT_MAX, true> g("01234", 4);
  161.     // g.AddEdge('0', '1', 1);
  162.     // g.AddEdge('0', '3', 4);
  163.     // g.AddEdge('1', '3', 2);
  164.     // g.AddEdge('1', '2', 9);
  165.     // g.AddEdge('2', '3', 8);
  166.     // g.AddEdge('2', '1', 5);
  167.     // g.AddEdge('2', '0', 3);
  168.     // g.AddEdge('3', '2', 6);
  169.     // g.Print();
  170.     // cout << g.GetVertexIndex('2') << endl;
  171.  
  172.     string a[] = {"zhangsan", "lisi", "wangwu", "zhaoliu", "zhouqi"};
  173.     Graph<string, int> g1(a, sizeof(a) / sizeof(string));
  174.     g1.AddEdge("zhangsan", "lisi", 100);
  175.     g1.AddEdge("zhangsan", "wangwu", 200);
  176.     g1.AddEdge("wangwu", "zhaoliu", 30);
  177.     g1.AddEdge("wangwu", "zhouqi", 30);
  178.  
  179.     g1.Bfs("zhangsan");
  180.  
  181.     system("pause");
  182.     return 0;
  183. }

 

1.2 图的深度优先遍历 

  1. void _DFS(int index, vector<bool>& visited)
  2. {
  3.  if(!visited[index])
  4.  {
  5.  cout<<_v[index]<<" ";
  6.  visited[index] = true;
  7.  LinkEdge* pCur = _linkEdges[index];
  8.  while(pCur)
  9.  {
  10.  _DFS(pCur->_dst, visited);
  11.  pCur = pCur->_pNext;
  12.  }
  13.  }
  14. }
  15. void DFS(const V& v)
  16. {
  17.  cout<<"DFS:";
  18.  vector<bool> visited(_v.size(), false);
  19.  _DFS(GetIndexOfV(v), visited);
  20.  for(size_t index = 0; index < _v.size(); ++index)
  21.  _DFS(index, visited);
  22.  cout<<endl;
  23. }
  24. void TestGraphDBFS()
  25. {
  26. string a[] = { "张三", "李四", "王五", "赵六", "周七" };
  27. Graph<string, int> g1(a, sizeof(a)/sizeof(string));
  28. g1.AddEdge("张三", "李四", 100);
  29. g1.AddEdge("张三", "王五", 200);
  30. g1.AddEdge("王五", "赵六", 30);
  31. g1.AddEdge("王五", "周七", 30);
  32. g1.BFS("张三");
  33. g1.DFS("张三");
  34. }

4. 最小生成树

连通图中的每一棵生成树，都是原图的一个极大无环子图，即： 从其中删去任何一条边，生成树
就不在连通；反之，在其中引入任何一条新边，都会形成一条回路 。
若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n-1 条边 。因此构造最小生成树的准则有三
条：
1. 只能使用图中的边来构造最小生成树
2. 只能使用恰好 n-1 条边来连接图中的 n 个顶点
3. 选用的 n-1 条边不能构成回路
构造最小生成树的方法： Kruskal 算法 和 Prim 算法 。这两个算法都采用了 逐步求解的贪心策略 。
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是
整体 最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解

4.1 Kruskal算法

        任给一个有n个顶点的连通网络N={V,E}，首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分量，其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。 

  1. W Kruskal(Self& minTree)
  2. {
  3.      minTree._vertexs = _vertexs;
  4.      minTree._vIndexMap = _vIndexMap;
  5.      minTree._matrix.resize(_vertexs.size());
  6.      for (auto& e : minTree._matrix)
  7.  {
  8.          e.resize(_vertexs.size(), MAX_W);
  9.      }
  10.      priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
  11.      for (size_t i = 0; i < _matrix.size(); ++i)
  12.      {
  13.          for (size_t j = 0; j < _matrix[i].size(); ++j)
  14.          {
  15.              if (i < j && _matrix[i][j] != MAX_W)
  16.              {
  17.                  pq.push(Edge(i, j, _matrix[i][j]));
  18.              }
  19.          }
  20.      }
  21.      W total = W();
  22.      // 贪心算法，从最小的边开始选
  23.      size_t i = 1;
  24.      UnionFindSet ufs(_vertexs.size());
  25.      while (i < _vertexs.size() && !pq.empty())
  26.      {
  27.          Edge min = pq.top();
  28.          pq.pop();
  29.          // 边不在一个集合，说明不会构成环，则添加到最小生成树
  30.          if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti))
  31.          {
  32.              //cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << 
  33. ":" << _matrix[min._srci][min._dsti] << endl;
  34.              minTree._AddEdge(min._srci, min._dsti, min._w);
  35.              total += min._w;
  36.              ufs.Union(min._srci, min._dsti);
  37.              ++i;
  38.          }
  39.      }
  40.      if (i == _vertexs.size())
  41.      {
  42.          return total;
  43.      }
  44.      else
  45.      {
  46.          return W();
  47.      }
  48. }
  49. void TestGraphMinTree()
  50. {
  51.      const char* str = "abcdefghi";
  52.      Graph<char, int> g(str, strlen(str));
  53.      g.AddEdge('a', 'b', 4);
  54.      g.AddEdge('a', 'h', 8);
  55.      //g.AddEdge('a', 'h', 9);
  56.      g.AddEdge('b', 'c', 8);
  57.      g.AddEdge('b', 'h', 11);
  58.  g.AddEdge('c', 'i', 2);
  59.      g.AddEdge('c', 'f', 4);
  60.      g.AddEdge('c', 'd', 7);
  61.      g.AddEdge('d', 'f', 14);
  62.      g.AddEdge('d', 'e', 9);
  63.      g.AddEdge('e', 'f', 10);
  64.      g.AddEdge('f', 'g', 2);
  65.      g.AddEdge('g', 'h', 1);
  66.      g.AddEdge('g', 'i', 6);
  67.      g.AddEdge('h', 'i', 7);
  68.      Graph<char, int> kminTree;
  69.      cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
  70.      kminTree.Print();
  71.      Graph<char, int> pminTree;
  72.      cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
  73.      pminTree.Print();
  74. }

 4.2 Prim算法 

  1. W Prim(Self& minTree, const V& src)
  2. {
  3.  minTree._vertexs = _vertexs;
  4.  minTree._vIndexMap = _vIndexMap;
  5.  minTree._matrix.resize(_vertexs.size());
  6.  for (auto& e : minTree._matrix)
  7.  {
  8.  e.resize(_vertexs.size(), MAX_W);
  9.  }
  10.  size_t srci = GetVertexIndex(src);
  11. set<size_t> inSet;
  12.  inSet.insert(srci);
  13.  priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
  14.  for (size_t i = 0; i < _vertexs.size(); ++i)
  15.  {
  16.  if (_matrix[srci][i] != MAX_W)
  17.  {
  18.  pq.push(Edge(srci, i, _matrix[srci][i]));
  19.  }
  20.  }
  21.  W total = W();
  22.  while (inSet.size() < _vertexs.size() && !pq.empty())
  23.  {
  24.  Edge min = pq.top();
  25.  pq.pop();
  26.  // 防止环的问题
  27.  if (inSet.find(min._srci) == inSet.end() ||
  28. inSet.find(min._dsti) == inSet.end())
  29.  {
  30.  //cout << _vertexs[min._srci] << "-" << 
  31. _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;
  32.  minTree._AddEdge(min._srci, min._dsti, min._w);
  33.  total += min._w;
  34.  // 新入顶点的连接边进入队列
  35.  for (size_t i = 0; i < _vertexs.size(); ++i)
  36.  {
  37.  if (_matrix[min._dsti][i] != MAX_W && inSet.find(i) 
  38. == inSet.end())
  39.  {
  40.  pq.push(Edge(min._dsti, i, _matrix[min._dsti]
  41. [i]));
  42.  }
  43.  }
  44.  inSet.insert(min._dsti);
  45.  }
  46.  }
  47.  if (inSet.size() == _vertexs.size())
  48.  {
  49.  return total;
  50.  }
  51.  else
  52.  {
  53.  return W();
  54.  }
  55. }
  56. void TestGraphMinTree()
  57. {
  58.      const char* str = "abcdefghi";
  59.      Graph<char, int> g(str, strlen(str));
  60.      g.AddEdge('a', 'b', 4);
  61.      g.AddEdge('a', 'h', 8);
  62. //g.AddEdge('a', 'h', 9);
  63.      g.AddEdge('b', 'c', 8);
  64.      g.AddEdge('b', 'h', 11);
  65.      g.AddEdge('c', 'i', 2);
  66.      g.AddEdge('c', 'f', 4);
  67.      g.AddEdge('c', 'd', 7);
  68.      g.AddEdge('d', 'f', 14);
  69.      g.AddEdge('d', 'e', 9);
  70.      g.AddEdge('e', 'f', 10);
  71.      g.AddEdge('f', 'g', 2);
  72.      g.AddEdge('g', 'h', 1);
  73.      g.AddEdge('g', 'i', 6);
  74.      g.AddEdge('h', 'i', 7);
  75.      Graph<char, int> kminTree;
  76.      cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
  77.      kminTree.Print();
  78.      Graph<char, int> pminTree;
  79.      cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
  80.      pminTree.Print();
  81. }

5. 最短路径

最短路径问题：从在带权有向图 G 中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。

5.1单源最短路径--Dijkstra算法

单源最短路径问题：给定一个图 G = ( V ， E ) G=(V ， E)G=(V ， E) ，求源结点 s ∈ V s ∈ Vs ∈ V 到图
中每个结点 v ∈ V v ∈ Vv ∈ 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 算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路
径的最短路径。 
  1. void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath)
  2. {
  3. size_t N = _vertexs.size();
  4. size_t srci = GetVertexIndex(src);
  5. // vector<W> dist,记录srci-其他顶点最短路径权值数组
  6. dist.resize(N, MAX_W);
  7. // vector<int> parentPath 记录srci-其他顶点最短路径父顶点数组
  8. parentPath.resize(N, -1);
  9. // 标记是否找到最短路径的顶点集合S
  10. vector<bool> S;
  11. S.resize(N, false);
  12. // srci的权值给一个最小值，方便贪心第一次找到这个节点
  13. dist[srci] = W(); 
  14. // N个顶点更新N次
  15. for (size_t i = 0; i < N; ++i)
  16.  {
  17.      // 贪心算法：srci到不在S中路径最短的那个顶点u
  18.      W min = MAX_W;
  19.      size_t u = srci;
  20.      for (size_t j = 0; j < N; ++j)
  21.      {
  22.          if (S[j] == false && dist[j] < min)
  23.          {
  24.              min = dist[j];
  25.              u = j;
  26.          }
  27.      }
  28.      S[u] = true;
  29.      // 松弛算法：更新一遍u连接的所有边，看是否能更新出更短连接路径
  30.      for (size_t k = 0; k < N; ++k)
  31.      {
  32. // 如果srci->u + u->k 比 srci->k更短 则进行更新
  33.          if (S[k] == false && _matrix[u][k] != MAX_W
  34.              && dist[u] + _matrix[u][k] < dist[k])
  35.          {
  36.              dist[k] = dist[u] + _matrix[u][k];
  37.              parentPath[k] = u;
  38.          }
  39.      }
  40.  }
  41. }
  42. // 打印最短路径的逻辑算法
  43. void PrinrtShotPath(const V& src, const vector<W>& dist, const vector<int>&
  44. parentPath)
  45. {
  46.  size_t N = _vertexs.size();
  47.  size_t srci = GetVertexIndex(src);
  48.  for (size_t i = 0; i < N; ++i)
  49.  {
  50.  if (i == srci)
  51.  continue;
  52.  
  53.  vector<int> path;
  54.  int parenti = i;
  55.  while (parenti != srci)
  56.  {
  57.  path.push_back(parenti);
  58.  parenti = parentPath[parenti];
  59.  }
  60.  path.push_back(srci);
  61.  reverse(path.begin(), path.end());
  62.  for (auto pos : path)
  63.  {
  64.  cout << _vertexs[pos] << "->";
  65.  }
  66.  cout << dist[i] << endl;
  67.  }
  68. }
  69. void TestGraphDijkstra()
  70. {
  71. const char* str = "syztx";
  72. Graph<char, int, INT_MAX, true> g(str, strlen(str));
  73. g.AddEdge('s', 't', 10);
  74. g.AddEdge('s', 'y', 5);
  75. g.AddEdge('y', 't', 3);
  76. g.AddEdge('y', 'x', 9);
  77. g.AddEdge('y', 'z', 2);
  78. g.AddEdge('z', 's', 7);
  79. g.AddEdge('z', 'x', 6);
  80. g.AddEdge('t', 'y', 2);
  81. g.AddEdge('t', 'x', 1);
  82. g.AddEdge('x', 'z', 4);
  83. vector<int> dist;
  84. vector<int> parentPath;
  85. g.Dijkstra('s', dist, parentPath);
  86. g.PrinrtShotPath('s', dist, parentPath);
  87. // 图中带有负权路径时，贪心策略则失效了。
  88. // 测试结果可以看到s->t->y之间的最短路径没更新出来
  89. /*const char* str = "sytx";
  90.  Graph<char, int, INT_MAX, true> g(str, strlen(str));
  91.  g.AddEdge('s', 't', 10);
  92.  g.AddEdge('s', 'y', 5);
  93.  g.AddEdge('t', 'y', -7);
  94.  g.AddEdge('y', 'x', 3);
  95.  vector<int> dist;
  96.  vector<int> parentPath;
  97.  g.Dijkstra('s', dist, parentPath);
  98.  g.PrinrtShotPath('s', dist, parentPath);*/
  99. }

 5.2 单源最短路径--Bellman-Ford算法

Dijkstra 算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法
就不能帮助我们解决问题了，而 bellman—ford 算法可以解决负权图的单源最短路径问题 。它的
优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显
的缺点，它的时间复杂度 O(N*E) (N 是点数， E 是边数 ) 普遍是要高于 Dijkstra 算法 O(N²) 的。像这里
如果我们使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是 O(N^3) ，这里也可以看出
来 Bellman-Ford 就是一种暴力求解更新。 

  1. bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)
  2. {
  3.  size_t N = _vertexs.size();
  4.  size_t srci = GetVertexIndex(src);
  5.  // vector<W> dist,记录srci-其他顶点最短路径权值数组
  6.  dist.resize(N, MAX_W);
  7. // vector<int> parentPath 记录srci-其他顶点最短路径父顶点数组
  8.  parentPath.resize(N, -1);
  9.  // 先更新srci->srci为最小值
  10.  dist[srci] = W();
  11.  for (size_t k = 0; k < N - 1; ++k)
  12.  {
  13.  bool exchange = false;
  14.  for (size_t i = 0; i < N; ++i)
  15.  {
  16.  for (size_t j = 0; j < N; ++j)
  17.  {
  18.  // srci->i + i->j < srci->j 则更新路径及权值
  19.  if (_matrix[i][j] != MAX_W
  20.  && dist[i] + _matrix[i][j] < dist[j])
  21.  {
  22.  dist[j] = dist[i] + _matrix[i][j];
  23.  parentPath[j] = i;
  24.  exchange = true;
  25.  }
  26.  }
  27.  }
  28.  if (exchange == false)
  29.  break;
  30.  }
  31.  for (size_t i = 0; i < N; ++i)
  32.  {
  33.  for (size_t j = 0; j < N; ++j)
  34.  {
  35.  // 检查有没有负权回路
  36.  if (_matrix[i][j] != MAX_W
  37.  && dist[i] + _matrix[i][j] < dist[j])
  38.  {
  39.  return false;
  40.  }
  41.  }
  42.  }
  43.  return true;
  44. }
  45. void TestGraphBellmanFord()
  46. {
  47.  const char* str = "syztx";
  48.  Graph<char, int, INT_MAX, true> g(str, strlen(str));
  49.  g.AddEdge('s', 't', 6);
  50.  g.AddEdge('s', 'y', 7);
  51.  g.AddEdge('y', 'z', 9);
  52.  g.AddEdge('y', 'x', -3);
  53.  g.AddEdge('z', 's', 2);
  54.  g.AddEdge('z', 'x', 7);
  55.  g.AddEdge('t', 'x', 5);
  56.  g.AddEdge('t', 'y', 8);
  57.  g.AddEdge('t', 'z', -4);
  58. g.AddEdge('x', 't', -2);
  59.  vector<int> dist;
  60.  vector<int> parentPath;
  61.  if (g.BellmanFord('s', dist, parentPath))
  62.  {
  63.  g.PrinrtShotPath('s', dist, parentPath);
  64.  }
  65.  else
  66.  {
  67.  cout << "存在负权回路" << endl;
  68.  }
  69.  // 微调图结构，带有负权回路的测试
  70.  //const char* str = "syztx";
  71.  //Graph<char, int, INT_MAX, true> g(str, strlen(str));
  72.  //g.AddEdge('s', 't', 6);
  73.  //g.AddEdge('s', 'y', 7);
  74.  //g.AddEdge('y', 'x', -3);
  75.  //g.AddEdge('y', 'z', 9);
  76.  //g.AddEdge('y', 'x', -3);
  77.  //g.AddEdge('y', 's', 1); // 新增
  78.  //g.AddEdge('z', 's', 2);
  79.  //g.AddEdge('z', 'x', 7);
  80.  //g.AddEdge('t', 'x', 5);
  81.  //g.AddEdge('t', 'y', -8); // 更改
  82.  //g.AddEdge('t', 'z', -4);
  83.  //g.AddEdge('x', 't', -2);
  84.  //vector<int> dist;
  85.  //vector<int> parentPath;
  86.  //if (g.BellmanFord('s', dist, parentPath))
  87.  //{
  88.  // g.PrinrtShotPath('s', dist, parentPath);
  89.  //}
  90.  //else
  91.  //{
  92.  // cout << "存在负权回路" << endl;
  93.  //}
  94. }

5.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 个点最短路径，然后建立
起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得
到所以点的最短路。 

  1. void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>&
  2. vvParentPath)
  3. {
  4.  size_t N = _vertexs.size();
  5.  vvDist.resize(N);
  6.  vvParentPath.resize(N);
  7. // 初始化权值和路径矩阵
  8.  for (size_t i = 0; i < N; ++i)
  9.  {
  10.  vvDist[i].resize(N, MAX_W);
  11.  vvParentPath[i].resize(N, -1);
  12.  }
  13.  // 将直接相连的路径初始化
  14.  for (size_t i = 0; i < N; ++i)
  15.  {
  16.  for (size_t j = 0; j < N; ++j)
  17.  {
  18.  if (_matrix[i][j] != MAX_W)
  19.  { 
  20.  vvDist[i][j] = _matrix[i][j];
  21.  vvParentPath[i][j] = i;
  22.  }
  23.  else
  24.  {
  25.  vvParentPath[i][j] = -1;
  26.  }
  27.  if (i == j)
  28.  {
  29.  vvDist[i][j] = 0;
  30.  vvParentPath[i][j] = -1;
  31.  }
  32.  }
  33.  }
  34.  // 依次用顶点k作为中转点更新最短路径
  35.  for (size_t k = 0; k < N; ++k)
  36.  {
  37.  for (size_t i = 0; i < N; ++i)
  38.  {
  39.  for (size_t j = 0; j < N; ++j)
  40.  {
  41.  // i->k + k->j 比 i->j前面更新的距离更短，则更新
  42.  if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
  43.  && vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
  44.  {
  45.  vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
  46.  vvParentPath[i][j] = vvParentPath[k][j];
  47.  }
  48.  }
  49.  }
  50.  // 打印权值和路径矩阵观察数据
  51.  //for (size_t i = 0; i < N; ++i)
  52.  //{
  53.  // for (size_t j = 0; j < N; ++j)
  54.  // {
  55.  // if (vvDist[i][j] == MAX_W)
  56.  // {
  57.  // //cout << "*" << " ";
  58.  // printf("%3c", '*');
  59.  // }
  60.  // else
  61. // {
  62.  // //cout << vvDist[i][j] << " ";
  63.  // printf("%3d", vvDist[i][j]);
  64.  // }
  65.  // }
  66.  // cout << endl;
  67.  //}
  68.  //cout << endl;
  69.  //for (size_t i = 0; i < N; ++i)
  70.  //{
  71.  // for (size_t j = 0; j < N; ++j)
  72.  // {
  73.  // //cout << vvParentPath[i][j] << " ";
  74.  // printf("%3d", vvParentPath[i][j]);
  75.  // }
  76.  // cout << endl;
  77.  //}
  78.  //cout << "=================================" << endl;
  79.  }
  80. }
  81. void TestFloydWarShall()
  82. {
  83.  const char* str = "12345";
  84.  Graph<char, int, INT_MAX, true> g(str, strlen(str));
  85.  g.AddEdge('1', '2', 3);
  86.  g.AddEdge('1', '3', 8);
  87.  g.AddEdge('1', '5', -4);
  88.  g.AddEdge('2', '4', 1);
  89.  g.AddEdge('2', '5', 7);
  90.  g.AddEdge('3', '2', 4);
  91.  g.AddEdge('4', '1', 2);
  92.  g.AddEdge('4', '3', -5);
  93.  g.AddEdge('5', '4', 6);
  94.  vector<vector<int>> vvDist;
  95.  vector<vector<int>> vvParentPath;
  96.  g.FloydWarShall(vvDist, vvParentPath);
  97.  // 打印任意两点之间的最短路径
  98.  for (size_t i = 0; i < strlen(str); ++i)
  99.  {
  100.  g.PrinrtShotPath(str[i], vvDist[i], vvParentPath[i]);
  101.  cout << endl;
  102.  }
  103. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/398953
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号