/*!* @file graph_algorithm.cpp* @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)* @brief 图算法.cpp文件* @version 0.2.1* @date 2021年02月04日*/#include <iostream>#include <set>#include <queue>#include <vector>#include "graph_algorithm.h"#include "min_priority_queue.h"#include "disjoint_set.h"/*!* @brief **图深度优先遍历*** @tparam TVertex 结点类型模版参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param vertex 遍历起点* @note* 图深度优先遍历* ------------* ------------** ------------* 声明已访问结点集合visited_vertex_set\n\n* 对vertex(遍历起点)调用DfsOnVertexRecursive\n*** ------------*/template<typename TVertex, typename TWeight>void Dfs(const Graph<TVertex, TWeight>& graph, const TVertex& vertex) {set<TVertex> visited_vertex_set; // 声明已访问结点集合visited_vertex_setDfsOnVertexRecursive(graph, vertex, visited_vertex_set); // 对vertex(遍历起点)调用DfsOnVertexRecursive}/*!* @brief **图结点深度优先遍历(递归)*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param vertex 遍历起点* @param visited_vertex_set 已访问结点集合* @note* 图结点深度优先遍历(递归)* --------------------* --------------------** 利用函数的调用关系来模拟栈** --------------------* + **1 初始化visited_vertex_set(已访问结点集合)**\n\n* vertex插入到visited_vertex_set\n\n* + **2 遍历vertex(起点)的邻接点, 执行递归**\n\n* <span style="color:#E76600;font-weight:bold">( 2.1 初始化neighbor_vertex<span style="color:#283593;font-weight:bold">(新邻接点)</span>和new_neighbor_exists<span style="color:#283593;font-weight:bold">(是否存在新邻接点)</span> )</span>\n* 声明neighbor_vertex\n* 调用GetFirstNeighborVertex, 初始化neighbor_vertex和new_neighbor_exists\n\n* <span style="color:#E76600;font-weight:bold">( 2.2 遍历执行递归 )</span>\n* **while loop** 存在新邻接点 :\n\n*   **if** 新邻接点不在visit_vertex_set中 :\n*    对新邻接点调用DfsOnVertexRecursive<span style="color:#008040;font-weight:bold">(递归)</span>\n\n*   获取下一新邻接点, 并将执行结果<span style="color:#283593;font-weight:bold">(是否存在下一新邻接点)</span>赋给new_neighbor_exists\n*   **if** 下一新邻接点存在 :\n*    更新neighbor_vertex\n\n*** --------------------*/template<typename TVertex, typename TWeight>void DfsOnVertexRecursive(const Graph<TVertex, TWeight>& graph, const TVertex& vertex, set<TVertex>& visited_vertex_set) {cout << "访问结点: " << vertex << endl;// ---------- 1 起点插入已遍历结点集合 ----------visited_vertex_set.insert(vertex); // vertex插入到visited_vertex_set// ---------- 2 遍历起点的邻接点, 执行递归 ----------// ( 2.1 初始化neighbor_vertex(新邻接点)和new_neighbor_exists(是否存在新邻接点) )TVertex neighbor_vertex; // 声明neighbor_vertexbool new_neighbor_exists = graph.GetFirstNeighborVertex(vertex, neighbor_vertex); // 调用GetFirstNeighborVertex, 初始化neighbor_vertex和new_neighbor_exists// ( 2.2 遍历执行递归 )while (new_neighbor_exists) { // while loop 存在新邻接点if (visited_vertex_set.find(neighbor_vertex) == visited_vertex_set.end()) { // if 新邻接点不在visit_vertex_set(已访问结点集合)中DfsOnVertexRecursive(graph, neighbor_vertex, visited_vertex_set); // 对新邻接点调用DfsOnVertexRecursive(递归)}TVertex next_neighbor_vertex; // 声明next_neighbor_vertex(下一新邻结点)new_neighbor_exists = graph.GetNextNeighborVertex(vertex, neighbor_vertex, next_neighbor_vertex); // 获取下一新邻接点, 并将执行结果(是否存在下一新邻接点)赋给new_neighbor_existsif (new_neighbor_exists) { // if 下一新邻接点存在neighbor_vertex = next_neighbor_vertex; // 更新neighbor_vertex}}}/*!* @brief **拓扑排序*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param starting_vertex 起点* @param topology_sorted_list 拓扑排序列表* @return 执行结果* @note* 拓扑排序* ------* ------** DFS的方式** ------* 声明visited_vertex_set(已访问结点集合)\n\n* **if** 有向图 :\n*   获取起点入度\n*   **if** 入度 > 0 :\n*    返回false\n\n* 对起点调用TopologicalSortRecursive_\n\n* 返回true\n*** ------*/template<typename TVertex, typename TWeight>bool TopologicalSort(const Graph<TVertex, TWeight>& graph,const TVertex& starting_vertex,vector<TVertex>& topology_sorted_list){set<TVertex> visited_vertex_set; // 声明visited_vertex_set(已访问结点集合)if (graph.Type() == Graph<TVertex, TWeight>::DIRECTED) { // if 有向图int in_degree = graph.GetVertexInDegree(starting_vertex); // 获取起点入度if (in_degree > 0) { // if 入度 > 0return false; // 返回false}}TopologicalSortRecursive_(graph, starting_vertex, visited_vertex_set, topology_sorted_list); // 对起点调用TopologicalSortRecursive_return true; // 返回true}/*!* @brief **拓扑排序(递归)*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param starting_vertex 起点* @param visited_vertex_set 已访问结点集合* @param topology_sorted_list 拓扑排序列表* @note* 拓扑排序(递归)* ------------* ------------** DFS的方式** ------------* + **1 起点插入已遍历结点集合**\n\n* 将starting_vertex插入到visited_vertex_set\n* 将starting_vertex插入到topology_sorted_list\n\n* + **2 遍历起点的邻接点, 执行递归**\n\n* ( 2.1 初始化neighbor_vertex(新邻接点)和new_neighbor_exists(是否存在新邻接点) )\n* 声明neighbor_vertex(新邻结点)\n* 调用GetFirstNeighborVertex,初始化neighbor_vertex和new_neighbor_exists(是否存在新邻结点)\n\n* ( 2.2 遍历执行递归 )\n* **while loop** 存在新邻接点 :\n*   **if** 新邻接点不在visit_vertex_set(已访问结点集合)中 :\n*    对新邻接点调用DfsOnVertexRecursive(递归)\n\n*   声明next_neighbor_vertex(下一邻接点)\n*   获取next_neighbor_vertex, 并将执行结果(是否存在下一新邻接点)赋给new_neighbor_exists\n\n*   **if** 下一新邻接点存在 :\n*    更新neighbor_vertex\n*** ------------*/template<typename TVertex, typename TWeight>void TopologicalSortRecursive_(const Graph<TVertex, TWeight>& graph,TVertex starting_vertex,set<TVertex>& visited_vertex_set,vector<TVertex>& topology_sorted_list){// ---------- 1 起点插入已遍历结点集合 ----------visited_vertex_set.insert(starting_vertex); // 将starting_vertex插入到visited_vertex_settopology_sorted_list.push_back(starting_vertex); // 将starting_vertex插入到topology_sorted_list// ---------- 2 遍历起点的邻接点, 执行递归 ----------// 2.1 初始化neighbor_vertex(新邻接点)和new_neighbor_exists(是否存在新邻接点)TVertex neighbor_vertex; // 声明neighbor_vertex(新邻结点)bool new_neighbor_exists = graph.GetFirstNeighborVertex(starting_vertex, neighbor_vertex); // 调用GetFirstNeighborVertex,初始化neighbor_vertex和new_neighbor_exists// 2.2 遍历执行递归while (new_neighbor_exists) { // while loop 存在新邻接点if (visited_vertex_set.find(neighbor_vertex) == visited_vertex_set.end()) { // if 新邻接点不在visit_vertex_set(已访问结点集合)中TopologicalSortRecursive_(graph, neighbor_vertex, visited_vertex_set, topology_sorted_list); // 对新邻接点调用DfsOnVertexRecursive(递归)}TVertex next_neighbor_vertex; // 声明next_neighbor_vertex(下一邻结点)new_neighbor_exists = graph.GetNextNeighborVertex(starting_vertex, // 获取next_neighbor_vertex, 并将执行结果(是否存在下一新邻接点)赋给new_neighbor_existsneighbor_vertex,next_neighbor_vertex);if (new_neighbor_exists) { // if 下一新邻接点存在neighbor_vertex = next_neighbor_vertex; // 更新neighbor_vertex}}}/*!* @brief **图广度优先遍历*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param vertex 遍历起点* @note* 图广度优先遍历* ------------* ------------** ------------* + **1 初始化visited_vertex_set(已访问结点集合)**\n\n*   声明visited_vertex_set\n*   插入vertex(起点)\n\n* + **2 初始化visited_queue(结点队列)**\n\n*   声明vertex_queue\n*   起点入队\n\n* + **3 使用队列进行遍历**\n\n*   **while loop** 队列不为空 :\n*    取front_vertex(队头)\n*    队头出队\n\n*    获取neighbor_vertex(新邻接点)和new_neighbor_exists(是否存在新邻接点)\n\n*    **while loop** 存在neighbor_vertex :\n\n*     **if** neighbor_vertex未被访问 :\n*      访问neighbor_vertex\n*      neighbor_vertex插入visited_vertex_set\n\n*      neighbor_vertex入队\n\n*     获取下一邻接点\n*     **if** 下一邻接点存在 :\n*      用下一邻接点更新neighbor_vertex\n*** ------------*/template<typename TVertex, typename TWeight>void Bfs(const Graph<TVertex, TWeight>& graph, const TVertex& vertex) {cout<<"访问结点: "<<vertex<<endl;// ---------- 1 初始化visited_vertex_set(已遍历结点集合) ----------set<TVertex> visited_vertex_set; // 声明visited_vertex_setvisited_vertex_set.insert(vertex); // 插入vertex(起点)// ---------- 2 初始化visited_queue(结点队列) ----------queue<TVertex> vertex_queue; // 声明vertex_queuevertex_queue.push(vertex); // 起点入队// ---------- 3 使用队列进行遍历结点 ----------while (!vertex_queue.empty()) { // while loop 队列不为空TVertex front_vertex = vertex_queue.front(); // 取front_vertex(队头)vertex_queue.pop(); // 队头出队TVertex neighbor_vertex;bool new_neighbor_exists = graph.GetFirstNeighborVertex(front_vertex, neighbor_vertex); // 获取neighbor_vertex(新邻接点)和new_neighbor_exists(是否存在新邻接点)while (new_neighbor_exists) { // while loop 存在新邻接点if (visited_vertex_set.find(neighbor_vertex) == visited_vertex_set.end()) { // if 该新邻接点未被访问cout<<"访问结点: "<<neighbor_vertex<<endl; // 访问新邻接点visited_vertex_set.insert(neighbor_vertex); // 该结点插入visited_vertex_set(已访问结点集合)vertex_queue.push(neighbor_vertex); // 该结点入队}TVertex next_neighbor_vertex;new_neighbor_exists = graph.GetNextNeighborVertex(front_vertex, // 获取下一新邻接点, 并将执行结果(是否存在下一新邻接点)赋给new_neighbor_existsneighbor_vertex,next_neighbor_vertex);if (new_neighbor_exists) { // if 下一新邻接点存在neighbor_vertex = next_neighbor_vertex; // 更新neighbor_vertex}}}}/*!* @brief **图的连通分量*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @return 连通分量个数* @note* 图的连通分量* ----------* ----------** <span style="color:#DF5A00">* 打印连通分量与算法耦合太重, 有兴趣的朋友自行解耦:-)* </span>** ----------* + **1 边界条件处理**\n\n* **if** 结点数为0 :\n*   返回0\n\n* + **2 遍历结点, 使用DFS划分联通分量**\n\n* 声明visited_vertex_set(已访问结点集合)\n* 初始化连通分量数量为1\n\n* **for loop** 遍历结点索引 :\n*   声明vertex(当前结点)\n*   获取i(当前索引)对应的结点vertex\n\n*   **if** 在visited_vertex_set中(则已经在某连通分量中) :\n*    continue(不再处理)\n\n*   使用DfsOnVertexRecursive对vertex进行遍历\n\n*   连通分量数量+1\n\n* + **退出函数**\n\n* 返回连通分量数量\n*** ----------*/template<typename TVertex, typename TWeight>int Components(const Graph<TVertex, TWeight>& graph) {// ---------- 1 边界条件处理 ----------if (graph.VertexCount() == 0) { // if 结点数为0return 0; // 返回0}// 2 ---------- 声明visited_vertex_set(已访问结点集合) ----------set<TVertex> visited_vertex_set; // 声明visited_vertex_set(已访问结点集合)int count = 1; // 初始连通分量数量为1for (unsigned int i = 0; i < graph.VertexCount(); i++) { // for loop 遍历结点索引TVertex vertex; // 声明vertex(当前结点)bool res = graph.GetVertexByIndex(i, vertex); // 获取i(当前索引)对应的结点vertexif (!res) {continue;}if (visited_vertex_set.find(vertex) != visited_vertex_set.end()) { // if 在visited_vertex_set中(则已经在某连通分量中)continue; // continue(不再处理)}cout << "连通分量" << count << " :" << endl;DfsOnVertexRecursive(graph, vertex, visited_vertex_set); // 使用DfsOnVertexRecursive对vertex进行遍历count++; // 连通分量数量+1cout<<endl;}// ---------- 3 退出函数 ----------return count; // 返回连通分量数量}/*!* @brief **Kruskal最小生成树算法*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param min_span_tree 最小生成树保存变量* @note* Kruskal最小生成树算法* -------------------* -------------------** <span style="color:#DF5A00">* 图 { Vertices(结点集合), { Edges(边集合) } }\n* \n* 最小生成树的初始状态: 只有n个顶点, 没有边, MST = { Vertices, { } }\n* \n* while MST未完成:\n*    在Edges中选择权值最小的边\n*    if 此边的两个结点, 分别落在不同的连通分量:\n*      将此边加入到MST\n*      Edges舍去这条边\n* </span>** -------------------* + **1 初始化min_priority_queue(最小优先队列)和disjoint_set(并查集)**\n\n* 声明min_priority_queue<span style="color:#283593;font-weight:bold">(最小优先队列)</span>\n* 初始化disjoint_set<span style="color:#283593;font-weight:bold">(并查集)</span>, size为图结点数\n\n* + **2 将所有边入队到最小优先队列**\n\n* **for loop** 遍历边索引 :\n*   获取cur_starting_vertex<span style="color:#283593;font-weight:bold">(当前边起点)</span>\n*   获取cur_ending_vertex<span style="color:#283593;font-weight:bold">(当前边终点)</span>\n\n*   声明weight<span style="color:#283593;font-weight:bold">(当前边权重)</span>\n*   获取weight\n*   **if** weight存在<span style="color:#008040;font-weight:bold">(即边存在)</span> :\n*    声明并初始化mst_edge<span style="color:#283593;font-weight:bold">(最小生成树边)</span>\n*    入队到min_priority_queue\n\n* + **3 贪心**\n\n* **for loop** 循环(图结点数 - 1)次 :\n*   声明cur_edge<span style="color:#283593;font-weight:bold">(当前边)</span>\n*   min_priority_queue队头出队, 赋给cur_edge\n\n*   取cur_starting_vertex_index<span style="color:#283593;font-weight:bold">(当前边的起点索引)</span>\n*   取cur_ending_vertex_index<span style="color:#283593;font-weight:bold">(当前边终点索引)</span>\n\n*   取cur_starting_vertex_root_index<span style="color:#283593;font-weight:bold">(当前边的起点所在并查集的根结点索引)</span>\n*   取cur_ending_vertex_root_index<span style="color:#283593;font-weight:bold">(当前边的终点所在并查集的根结点索引)</span>\n\n*   **if** 当前边起点和当前边终点, 不在一个并查集 :\n*    将cur_edge的起点所在的并查集, 与cur_edge终点所在的并查集合并\n*    cur_edge插入到min_span_tree<span style="color:#008040;font-weight:bold">(最小生成树增加1条边)</span>\n\n*    循环计数加1\n*** -------------------*/template<typename TVertex, typename TWeight>void Kruskal(const Graph<TVertex, TWeight>& graph, MinimumSpanTree<TVertex, TWeight>& min_span_tree) {// ---------- 1 初始化min_priority_queue(最小优先队列)和disjoint_set(并查集) ----------MinPriorityQueue<Edge<TVertex, TWeight> > min_priority_queue; // 声明min_priority_queue(最小优先队列)DisjointSet disjoint_set(graph.VertexCount()); // 初始化disjoint_set(并查集), size为图结点数// ---------- 2 将所有边入队到最小优先队列 ----------for (unsigned int i = 0; i < graph.EdgeCount(); i++) { // for loop 遍历边索引TVertex cur_starting_vertex = graph.GetEdge(i).starting_vertex; // 获取cur_starting_vertex(当前边起点)TVertex cur_ending_vertex = graph.GetEdge(i).ending_vertex; // 获取cur_ending_vertex(当前边终点)TWeight weight; // 声明weight(当前边权重)bool res = graph.GetWeight(cur_starting_vertex, cur_ending_vertex, weight); // 获取weightif (res) { // if weight存在(即当前边存在)Edge<TVertex, TWeight> mst_edge(cur_starting_vertex, cur_ending_vertex, weight); // 声明并初始化mst_edge(最小生成树边)min_priority_queue.Enqueue(mst_edge); // 入队到min_priority_queue}}// ---------- 3 贪心 ----------for (unsigned int i = 0; i < graph.VertexCount() - 1;) { // for loop 循环(图结点数 - 1)次Edge<TVertex, TWeight> cur_edge; // 声明cur_edge(当前边)min_priority_queue.Dequeue(cur_edge); // min_priority_queue队头出队, 赋给cur_edgeint cur_starting_vertex_index = graph.GetVertexIndex(cur_edge.starting_vertex); // 取cur_starting_vertex_index(当前边的起点索引)int cur_ending_vertex_index = graph.GetVertexIndex(cur_edge.ending_vertex); // 取cur_ending_vertex_index(当前边终点索引)int cur_starting_vertex_root_index = disjoint_set.FindRecursive(cur_ending_vertex_index); // 取cur_starting_vertex_root_index(当前边的起点所在并查集的根结点索引)int cur_ending_vertex_root_index = disjoint_set.FindRecursive(cur_starting_vertex_index); // 取cur_ending_vertex_root_index(当前边的终点所在并查集的根结点索引)if (cur_starting_vertex_root_index != cur_ending_vertex_root_index) { // if 当前边起点和当前边终点, 不在一个并查集disjoint_set.Union(cur_starting_vertex_root_index, cur_ending_vertex_root_index); // 将cur_edge的起点所在的并查集, 与cur_edge终点所在的并查集合并min_span_tree.Insert(cur_edge); // cur_edge插入到min_span_tree(最小生成树增加1条边)i++; // 循环计数加1}}}/*!* @brief **Prim最小生成树算法*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param min_span_tree 最小生成树* @return 执行结果* @note* Prim最小生成树算法* ----------------* ----------------** 此算法针对无向图\n\n* <span style="color:#FB1927">* 图 { Vertices(结点集合), { Edges(边集合) } }\n* min_span_tree: 最小生成树\n* mst_vertex_set: min_span_tree的结点集合\n\n* 算法从mst_vertex_set = { starting_vertex }开始(只包含起始结点)\n* 循环:\n*    在所有u ∈ mst_vertex_set, v ∈ (Vertices - mst_vertex_set)的边(u, v) ∈ E中\n* </span>* ```* mst_vertex_set Vertices - mst_vertex_set* ------ ------* / \ / \* | u ---|------|-- v |* \ / \ /* ------- ------* ```* <span style="color:#FB1927">*    找一条权值最小的边(starting_vertex, ending_vertex), 权值weight\n*      加入min_span_tree\n*      结点u加入mst_vertex_set\n*    直到mst_vertex_set = Vertices为止\n\n* 此时min_span_tree为最小生成树, 有vertex_count - 1条边\n* </span>** ----------------* + **1 设置起点**\n\n* 声明starting_vertex<span style="color:#283593;font-weight:bold">(起点)</span>\n* 获取索引0结点, 作为起点\n* **if** 获取失败 :\n*   返回false\n\n* + **2 初始化最小生成树结点集合和边的最小优先队列**\n\n* 声明mst_vertex_set<span style="color:#283593;font-weight:bold">(最小生成树结点集合)</span>\n* starting_vertex插入集合\n\n* 声明min_priority_queue<span style="color:#283593;font-weight:bold">(边的最小优先队列)</span>\n\n* + **3 贪心**\n\n* **while loop** 最小生成树结点集合的结点数 < 图结点数<span style="color:#008040;font-weight:bold">(即最小生成树未完成)</span> :\n\n*   <span style="color:#E76600;font-weight:bold">( 3.1 最小优先队列队头出队, 进入最小生成树 )</span>\n*   **if** min_priority_queue不为空 :\n*    声明cur_min_edge<span style="color:#283593;font-weight:bold">(当前最小边)</span>\n*    队头出队, 赋值给cur_min_edge\n\n*    cur_min_edge插入min_span_tree<span style="color:#283593;font-weight:bold">(最小生成树)</span>\n*    cur_min_edge的终点, 插入mst_vertex_set\n\n*   <span style="color:#E76600;font-weight:bold">( 3.2 最小优先队列队头出队, 进入最小生成树 )</span>\n*   **for loop** 遍历mst_vertex_set :\n*    取cur_mst_vertex<span style="color:#283593;font-weight:bold">(当前最小生成树结点)</span>\n\n*    声明cur_neighbor_vertex<span style="color:#283593;font-weight:bold">(当前邻接结点)</span>\n*    取cur_mst_vertex的首个邻接结点, 赋给cur_neighbor_vertex, 执行结果赋值给new_neighbor_exists<span style="color:#283593;font-weight:bold">(存在新的邻接结点)</span>\n\n*    **while loop** 存在新的邻接结点 :\n*     **if** cur_neighbor_vertex不在最小生成树结点集合中 :\n*      声明cur_weight<span style="color:#283593;font-weight:bold">(当前边权重)</span>\n*      获取 边(cur_mst_vertex ---> cur_neighbor_vertex) 的权重, 赋给cur_weight\n\n*      使用 边(cur_mst_vertex ---> cur_neighbor_vertex) 生成cur_edge\n*      cur_edge入队到min_priority_queue\n\n*     获取next_neighbor_vertex<span style="color:#283593;font-weight:bold">(下一邻接结点)</span>, 并将执行结果赋给new_neighbor_exists\n\n*     **if** 下一邻接结点存在 :\n*      下一邻接结点赋给cur_neighbor_vertex\n*** ----------------*/template<typename TVertex, typename TWeight>bool Prim(const Graph<TVertex, TWeight>& graph, MinimumSpanTree<TVertex, TWeight>& min_span_tree) {// ---------- 1 设置起点 ----------TVertex starting_vertex; // 声明starting_vertex(起点)bool res = graph.GetVertexByIndex(0, starting_vertex); // 获取索引0结点, 作为起点if (!res) { // if 获取失败return false; // 返回false}// ---------- 2 初始化最小生成树结点集合和边的最小优先队列 ----------set<TVertex> mst_vertex_set; // 声明mst_vertex_set(最小生成树结点集合)mst_vertex_set.insert(starting_vertex); // starting_vertex插入集合MinPriorityQueue<Edge<TVertex, TWeight> > min_priority_queue; // 声明min_priority_queue(边的最小优先队列)// ---------- 3 贪心 ----------while (mst_vertex_set.size() < graph.VertexCount()) { // while loop 最小生成树结点集合的结点数 < 图结点数(最小生成树未完成)if (min_priority_queue.Size() != 0) { // if min_priority_queue不为空Edge<TVertex, TWeight> cur_min_edge; // 声明cur_min_edge(当前最小边)min_priority_queue.Dequeue(cur_min_edge); // 队头出队, 赋值给cur_min_edgemin_span_tree.Insert(cur_min_edge); // cur_min_edge插入min_span_tree(最小生成树)mst_vertex_set.insert(cur_min_edge.ending_vertex); // cur_min_edge的终点, 插入mst_vertex_set}for (typename set<TVertex>::iterator iter = mst_vertex_set.begin(); iter != mst_vertex_set.end(); iter++) { // for loop 遍历mst_vertex_setTVertex cur_mst_vertex = *iter; // 取cur_mst_vertex(当前最小生成树结点)TVertex cur_neighbor_vertex; // 声明cur_neighbor_vertex(当前邻接结点)bool new_neighbor_exists = graph.GetFirstNeighborVertex(cur_mst_vertex, cur_neighbor_vertex); // 取cur_mst_vertex的首个邻接结点, 赋给cur_neighbor_vertex, 执行结果赋值给new_neighbor_exists(存在新的邻接结点)while (new_neighbor_exists) { // while loop 存在新的邻接结点if (mst_vertex_set.find(cur_neighbor_vertex) == mst_vertex_set.end()) { // if cur_neighbor_vertex(当前新的邻接结点)不在最小生成树结点集合中TWeight cur_weight; // 声明cur_weight(当前边权重)graph.GetWeight(cur_mst_vertex, cur_neighbor_vertex, cur_weight); // 获取 边(cur_mst_vertex ---> cur_neighbor_vertex) 的权重, 赋给cur_weightEdge<TVertex, TWeight> cur_edge(cur_mst_vertex, cur_neighbor_vertex, cur_weight); // 使用 边(cur_mst_vertex --- cur_neighbor_vertex) 生成cur_edgemin_priority_queue.Enqueue(cur_edge); // 将其入队到min_priority_queue(最小优先队列)}TVertex next_neighbor_vertex;new_neighbor_exists = graph.GetNextNeighborVertex(cur_mst_vertex, // 获取next_neighbor_vertex(下一邻接结点), 并将执行结果赋给new_neighbor_existscur_neighbor_vertex,next_neighbor_vertex);if (new_neighbor_exists) { // if 下一邻接结点存在cur_neighbor_vertex = next_neighbor_vertex; // 下一邻接结点赋给cur_neighbor_vertex}}}}return true;}/*!* @brief **Dijkstra迪杰斯特拉最短路径*** @tparam TVertex 结点类型模板类型* @tparam TWeight 边权值类型模板类型* @param graph 图* @param starting_vertex 起点* @param distance 最短路径数组, distance[i]表示: 起始结点到索引i结点的最短路径* @param predecessor 前一结点数组, predecessor[i]表示: 最短路径中, 索引i结点的前一结点的索引* @note* Dijkstra迪杰斯特拉最短路径* ------------------------* ------------------------** <span style="color:#E76600">* Dijkstra算法伪代码\n* \n* vertex_set: 保存所有已知实际(起始点 --> 该结点)最短路径值的结点的集合\n* min_priority_queue: 结点的一个优先队列,以结点的最短路径估计(起始点 --> 该节点的路径值), 进行排序\n* \n* 迪杰斯特拉算法:\n* \n*   --- 初始化 ---\n* \n*   // 初始化起点到每个(以外的)结点的distance, 到自身的距离为0, 到其他结点为无穷大\n*   INITIALIZE-SINGLE-SOURCE(graph(图), starting_vertex(起点))\n* \n*   // vertex_set初始化为空\n*   vertex_set(结点集合) <-- 空\n* \n*   // 起点进入优先队列\n*   priority_queue(优先队列) <-- 路径(起始点, 起始点, 路径长度)\n* \n*   --- 贪心 ---\n* \n*   while (min_priority_queue中有元素) :\n*    do u <-- EXTRACT_MIN(priority_queue) // 选取u为priority_queue中, 最短路径估计最小(起始点到该节点的路径最短)的结点\n* \n*    vertex_set <-- vertex_set and u // u加入集合vertex_set\n*    for u的每个邻接结点v:\n*     松弛(u, v, 边集合) // 松弛成功的结点, 会被加入到vertex_set, u进入priority_queue* </span>** ------------------------* + **1 初始化**\n\n* <span style="color:#FF9900;font-weight:bold">( 1.1 distance数组(起点到各点的最短路径长度)初始化 )</span>\n* 获取starting_vertex_index<span style="color:#283593;font-weight:bold">(起点索引)</span>\n* **for loop** 遍历结点 :\n*   路径(起点 ---> 当前结点)的最短路径, 长度设为上限值<span style="color:#008040;font-weight:bold">(不存在最短路径)</span>\n\n* 路径(起点 ---> 起点)的最短路径, 长度设为0\n\n* <span style="color:#FF9900;font-weight:bold">( 1.2 min_priority_queue(最短路径的最小优先队列)初始化 )</span>\n* 路径(起点 ---> 起点)入队\n\n* <span style="color:#FF9900;font-weight:bold">( 1.3 predecessor数组(最短路径终点的前驱结点索引)初始化 )</span>\n* 路径(起点 ---> 起点)的最短路径, 起点的前驱结点索引为-1<span style="color:#008040;font-weight:bold">(即起点不存在前驱结点)</span>\n\n* + **2 贪心**    <span style="color:#d40000">两层对结点的循环, 故时间复杂度: O(V^2)</span>\n\n* **while loop** 最短路径的最小优先队列不为空 :\n\n*   min_priority_queue队头出队, 赋给cur_min_path<span style="color:#283593;font-weight:bold">(从起点开始到各个结点, 当前最短的路径)</span>\n*   获取cur_min_path的终点索引, 赋给cur_min_path_ending_vertex_index\n\n*   **for loop** 遍历结点 :\n*    声明cur_vertex<span style="color:#283593;font-weight:bold">(当前结点)</span>\n*    获取cur_vertex\n*    声明weight(边(cur_min_path的终点 ---> 当前结点)的权值)\n*    获取 边(cur_min_path.ending_vertex ---> cur_vertex) <span style="color:#283593;font-weight:bold">(当前最短的路径的终点 ---> 当前遍历结点)</span>\n\n*    **if** 边(cur_min_path.ending_vertex ---> cur_vertex)不存在 :\n*     continue(不做处理)\n\n*    **if** 路径(起点 ---> 当前最短路径的终点) + 边(当前最短路径的终点, 当前遍历结点)权值 < 路径(起点 ---> 当前遍历结点) :\n*     路径(起点 ---> 当前遍历结点) = 路径(起点 ---> 当前最短路径的终点) + 边(当前最短路径的终点, 当前遍历结点)权值\n*     路径(起点 ---> 当前遍历结点)中 , 当前遍历结点的前一结点的索引, 设为cur_min_path_ending_vertex_index\n\n*     生成路径new_min_distance_path<span style="color:#283593;font-weight:bold">(起点 ---> 当前遍历结点)</span>\n*     将new_min_distance_path插入min_priority_queue<span style="color:#283593;font-weight:bold">(路径的最小优先队列)</span>\n*** ------------------------*/template<typename TVertex, typename TWeight>void Dijkstra(const Graph<TVertex, TWeight>& graph,const TVertex& starting_vertex,TWeight distance[],int predecessor[]){// ---------- 1 初始化 ----------// ( 1.1 distance数组(起点到各点的最短路径长度)初始化 )int starting_vertex_index = graph.GetVertexIndex(starting_vertex); // 获取starting_vertex_index(起点索引)for (unsigned int i = 0; i < graph.VertexCount(); i++) { // for loop 遍历结点distance[i] = graph.MaxWeight(); // 路径(起点 ---> 当前结点)的最短路径, 长度设为上限值(不存在最短路径)}distance[starting_vertex_index] = 0; // 路径(起点 ---> 起点)的最短路径, 长度设为0// ( 1.2 min_priority_queue(最短路径的最小优先队列)初始化 )MinPriorityQueue<Path<TVertex, TWeight> > min_priority_queue;Path<TVertex, TWeight> cur_path(starting_vertex, starting_vertex, 0);min_priority_queue.Enqueue(cur_path); // 路径(起点 ---> 起点)入队// ( 1.3 predecessor数组(最短路径终点的前驱结点索引)初始化 )predecessor[starting_vertex_index] = -1; // 路径(起点 ---> 起点)的最短路径, 起点的前驱结点索引为-1(即起点不存在前驱结点)// ---------- 2 贪心 ----------while (min_priority_queue.Size() != 0) { // while loop 最短路径的最小优先队列不为空Path<TVertex, TWeight> cur_min_path;min_priority_queue.Dequeue(cur_min_path); // min_priority_queue队头出队, 赋给cur_min_path(从起点开始到各个结点, 当前最短的路径)int cur_min_path_ending_vertex_index = graph.GetVertexIndex(cur_min_path.ending_vertex); // 获取cur_min_path的终点索引, 赋给cur_min_path_ending_vertex_indexfor (unsigned int i = 0; i < graph.VertexCount(); i++) { // for loop 遍历结点TVertex cur_vertex; // 声明cur_vertex(当前结点)graph.GetVertexByIndex(i, cur_vertex); // 获取cur_vertexTWeight weight; // 声明weight(边(cur_min_path的终点 ---> 当前结点)的权值)bool get_weight_done = graph.GetWeight(cur_min_path.ending_vertex, cur_vertex, weight); // 获取 边(cur_min_path.ending_vertex ---> cur_vertex) (即: 当前最短的路径的终点 ---> 当前遍历结点)if (!get_weight_done) { // if 边(cur_min_path.ending_vertex ---> cur_vertex)不存在continue; // continue(不做处理)}// --- 松弛操作 ---// 如果// 路径 (starting_vertex --> cur_min_path_ending_vertex) 的weight// +// 边 (cur_min_path_ending_vertex --> cur_vertex) 的weight// <// 路径 (starting_vertex ----------------------------------> cur_vertex) 的weight// 则// 更新distance[i]和predecessor[i]// 生成new_min_distance_path, 进入最小优先队列if (distance[cur_min_path_ending_vertex_index] + weight < distance[i]) { // if 路径(起点 ---> 当前最短路径的终点) + 边(当前最短路径的终点, 当前遍历结点)权值 < 路径(起点 ---> 当前遍历结点)distance[i] = distance[cur_min_path_ending_vertex_index] + weight; // 路径(起点 ---> 当前遍历结点) = 路径(起点 ---> 当前最短路径的终点) + 边(当前最短路径的终点, 当前遍历结点)权值predecessor[i] = cur_min_path_ending_vertex_index; // 路径(起点 ---> 当前遍历结点)中, 当前遍历结点的前一结点的索引, 设为cur_min_path_ending_vertex_indexPath<TVertex, TWeight> new_min_distance_path(starting_vertex, cur_vertex, distance[i]); // 生成路径new_min_distance_path(起点 ---> 当前遍历结点)min_priority_queue.Enqueue(new_min_distance_path); // 将new_min_distance_path插入min_priority_queue(路径的最小优先队列)}}}}/*!* @brief **Bellman-Ford贝尔曼福特最短路径*** @tparam TVertex 图结点模板类型* @tparam TWeight 图边权值模板类型* @param graph 图的引用* @param starting_vertex 起始结点* @param distance 最短路径数组, distance[i]表示: 起始结点到索引i结点的最短路径* @param predecessor 前一结点数组, predecessor[i]表示: 最短路径中, 索引i结点的前一结点* @return 是否有负环* @note* Bellman-Ford贝尔曼福特最短路径* ---------------------------* ---------------------------** <span style="color:#FB1927">* BellmanFord算法:\n* \n* --- 初始化 ---\n* \n*    for 图中的每个结点v:\n*      如果(starting_vertex, v)没有边:\n*        distance[v] <-- MAX(不存在路径)\n*      否则:\n*        如果 v 是starting_vertex(起始点):\n*          distance[v] = 0\n*          predecessor[v] <-- -1(没有前一结点)\n*        否则:\n*          distance[v] = 边(starting_vertex, v)的长度(权值)\n*          predecessor[v] <-- starting_vertex_index(结点starting_vertex的索引) // v的前一结点是starting_vertex* \n* \n* --- 动态规划 ---\n* \n*    for循环(图结点总数 - 1)次:\n*      for 图的每一条边edge (u, v):\n*        // 松弛\n*      如果 distance[u] + 边(u, v)权重 < distance[v]:\n*        distance[v] <-- distance[u] + 边(u, v)权重\n*        predecessor[v] <-- u\n* \n* \n* --- 检查是否有负权重的回路 ---\n* \n*    for 每一条边edge (u, v):\n*      如果 distance[u] + 边(u, v)权重 < distance[v]:\n*        error "图包含负回路"\n* </span>** ---------------------------* + **1 初始化**\n\n* 初始化starting_vertex_index<span style="color:#283593;font-weight:bold">(起点索引)</span>\n* **while loop** 遍历结点索引 :\n*   路径(起点 ---> 索引i结点)的最短路径, 权值(长度)初始化为MaxWeight()<span style="color:#008040;font-weight:bold">(即初始化为不存在最短路径)</span>\n\n* 路径(起点 ---> 起点)的最短路径, 权值(长度)初始化为0\n* 路径(起点 ---> 起点)的最短路径, 起点的前一结点索引设为-1<span style="color:#008040;font-weight:bold">(不存在)</span>\n\n* + **2 动态规划**    <span style="color:#d40000">1层对结点的循环, 1层对边的循环, 故时间复杂度: O(V*E)</span>\n\n* **while loop** 循环(结点数 - 1)次<span style="color:#008040;font-weight:bold">(最小生成树边的数量)</span> :\n*   **while loop** 循环每条边 :\n\n*    取cur_starting_vertex<span style="color:#283593;font-weight:bold">(当前边起点)</span>\n*    取cur_ending_vertex<span style="color:#283593;font-weight:bold">(当前边终点)\n\n*    取cur_starting_vertex_index<span style="color:#283593;font-weight:bold">(当前边起点索引)</span>\n*    取cur_ending_vertex_index<span style="color:#283593;font-weight:bold">(当前边终点索引)</span>\n\n*    声明cur_edge_weight<span style="color:#283593;font-weight:bold">(当前边权值)</span>\n*    取cur_edge_weight\n*    **if** 获取失败<span style="color:#008040;font-weight:bold">(即边(cur_starting_vertex ---> cur_ending_vertex)不存在)</span> :\n*     continue\n\n*    <span style="color:#008040;font-weight:bold">(松弛)</span>\n*    **if** (起点 ---> 当前边起点)的最短路径 + 当前边权值 < (起点 ---> 当前边终点)的最短路径 :\n*     (起点 ---> 当前边终点)的最短路径 = (起点 ---> 当前边起点)的最短路径 + 当前边权值\n*     在(起点 ---> 当前边终点)的最短路径中, 当前边终点的前一结点, 被赋值为当前边起点\n\n* + **3 检查是否有负权重的回路**\n\n* 初始化negative_weight_cycle_exists(存在负环)为false<span style="color:#008040;font-weight:bold">(初始化为没有负权环)</span>\n\n* **for loop** 遍历每条边 :\n\n*   取cur_starting_vertex<span style="color:#283593;font-weight:bold">(当前边起点)</span>\n*   取cur_ending_vertex<span style="color:#283593;font-weight:bold">(当前边终点)</span>\n\n*   取cur_starting_vertex_index<span style="color:#283593;font-weight:bold">(当前边起点索引)</span>\n*   取cur_ending_vertex_index<span style="color:#283593;font-weight:bold">(当前边终点索引)</span>\n\n*   声明cur_weight<span style="color:#283593;font-weight:bold">(当前边权值)</span>\n*   取cur_weight\n*   **if** 获取失败<span style="color:#008040;font-weight:bold">(即边(cur_starting_vertex ---> cur_ending_vertex)不存在)</span> :\n*    continue\n\n*   **if** (起点 ---> 当前边起点)的最短路径 + 当前边权值 < (起点 ---> 当前边终点)的最短路径 :\n*    negative_weight_cycle_exists设为true\n*    跳出循环<span style="color:#008040;font-weight:bold">(发现负权回路)</span>\n\n* + **4 退出函数**\n\n* 返回negative_weight_cycle_exists\n*** ---------------------------*/template<typename TVertex, typename TWeight>bool BellmanFord(const Graph<TVertex, TWeight>& graph,const TVertex& starting_vertex,TWeight distance[],int predecessor[]){// ---------- 1 初始化 ----------int starting_vertex_index = graph.GetVertexIndex(starting_vertex); // 初始化starting_vertex_index(起点索引)for (unsigned int i = 0; i < graph.VertexCount(); i++) { // while loop 遍历结点索引distance[i] = graph.MaxWeight(); // 路径(起点 ---> 索引i结点)的最短路径, 权值(长度)初始化为MaxWeight()(即初始化为不存在最短路径)}distance[starting_vertex_index] = starting_vertex_index; // (起点 ---> 起点)的最短路径, 权值(长度)初始化为0predecessor[starting_vertex_index] = -1; // (起点 ---> 起点)的最短路径, 起点的前一结点索引设为-1(不存在)// ---------- 2 动态规划 ----------for (unsigned int vertex_index = 0; vertex_index < graph.VertexCount() - 1; vertex_index++) { // while loop 循环(结点数 - 1)次(最小生成树边的数量)for (unsigned int edge_index = 0; edge_index < graph.EdgeCount(); edge_index++) { // while loop 循环每条边TVertex cur_starting_vertex = graph.GetEdge(edge_index).starting_vertex; // 取cur_starting_vertex(当前边起点)TVertex cur_ending_vertex = graph.GetEdge(edge_index).ending_vertex; // 取cur_ending_vertex(当前边终点)int cur_starting_vertex_index = graph.GetVertexIndex(cur_starting_vertex); // 取cur_starting_vertex_index(当前边起点索引)int cur_ending_vertex_index = graph.GetVertexIndex(cur_ending_vertex); // 取cur_ending_vertex_index(当前边终点索引)TWeight cur_edge_weight; // 声明cur_edge_weight(当前边权重)bool res = graph.GetWeight(cur_starting_vertex, cur_ending_vertex, cur_edge_weight); // 获取cur_edge_weightif (!res) { // if 获取失败(即边(cur_starting_vertex ---> cur_ending_vertex)不存在)continue;}// --- 松弛 ---// 如果// 边 (starting_vertex --> cur_starting_vertex) 的weight// +// 边 (cur_starting_vertex --> cur_ending_vertex) 的weight// <// 边 (starting_vertex ---------------------------> cur_ending_vertex) 的weight// 则// 更新distance[cur_ending_vertex_index]和predecessor[cur_ending_vertex_index]if (distance[cur_starting_vertex_index] + cur_edge_weight < distance[cur_ending_vertex_index]) { // if (起点 ---> 当前边起点)的最短路径 + 当前边权值 < (起点 ---> 当前边终点)的最短路径distance[cur_ending_vertex_index] = distance[cur_starting_vertex_index] + cur_edge_weight; // (起点 ---> 当前边终点)的最短路径 = (起点 ---> 当前边起点)的最短路径 + 当前边权值predecessor[cur_ending_vertex_index] = cur_starting_vertex_index; // (起点 ---> 当前边终点)的最短路径, 当前边终点的前一结点, 被赋值为当前边起点}}}// ---------- 3 检查是否有负权重的回路 ----------bool negative_weight_cycle_exists = false; // 初始化negative_weight_cycle_exists为false(初始化为没有负权环)for (unsigned int i = 0; i < graph.EdgeCount(); i++) { // for loop 遍历每条边TVertex cur_starting_vertex = graph.GetEdge(i).starting_vertex; // 取cur_starting_vertex(当前边起点)TVertex cur_ending_vertex = graph.GetEdge(i).ending_vertex; // 取cur_ending_vertex(当前边终点)int cur_starting_vertex_index = graph.GetVertexIndex(cur_starting_vertex); // 取cur_starting_vertex_index(当前边起点索引)int cur_ending_vertex_index = graph.GetVertexIndex(cur_ending_vertex); // 取cur_ending_vertex_index(当前边终点索引)TWeight cur_weight; // 声明cur_weight(当前边权值)bool get_weight_done = graph.GetWeight(cur_starting_vertex, cur_ending_vertex, cur_weight); // 取cur_weightif (!get_weight_done) { // if 获取失败(即边(cur_starting_vertex ---> cur_ending_vertex)不存在)continue;}if (distance[cur_starting_vertex_index] + cur_weight < distance[cur_ending_vertex_index]) { // if (起点 ---> 当前边起点)的最短路径 + 当前边权值 < (起点 ---> 当前边终点)的最短路径negative_weight_cycle_exists = true; // negative_weight_cycle_exists设为truebreak; // 跳出循环(发现负权回路)}}// ---------- 4 退出函数 ----------return negative_weight_cycle_exists; // 返回negative_weight_cycle_exists}/*!* @brief **Floyd-Warshall弗洛伊德最短路径算法*** @tparam TVertex 图结点类型模板参数* @tparam TWeight 图边权值类型模板参数* @param graph 图* @param distance 最短路径数组* @param predecessor 前一结点数组* @note* Floyd-Warshall弗洛伊德最短路径算法* --------------------------------* --------------------------------** <span style="color:#DF5A00">* distance[i][j]表示: 索引i结点到索引j结点的最短路径\n* predecessor[i][j]表示: 索引i结点到索引j结点的最短路径中, j的前一结点\n* <span style="color:#DF5A00">** <span style="color:#65000b">* Floyd:\n*   distance[][] is a distance matrix for n vertices.\n*   distance[i][j] is the distance to move directly from i to j.\n*   if no direct link from i to j\n*    then initialize distance[i][j] = INFINITY\n*   the distance from a node to itself is 0.(Initialize distance[i][i] = 0 for all i)\n* \n*   predecessor[][] is a predecessor matrix. it enables you to reconstruct the shortest paths.\n*   predecessor[i][j] should be initialized to i.\n* \n* 算法执行结果:\n*   distance[i][j] contains the total cost along the shortest path from i to j.\n*   predecessor[i][j] contains the predecessor of j on the shortest path from i to j.\n* </span>** --------------------------------** - **1 使用图的信息填充distance和predecessor数组**\n\n* **for loop** 遍历start<span style="color:#283593;font-weight:bold">(起点)</span> :\n*   **for loop** 遍历end<span style="color:#283593;font-weight:bold">(终点)</span> :\n*    **if** start等于end :\n*     路径(start ---> end)长度初始化\n*     路径(start ---> end), start的前一结点为start\n*    **else** (start不等于end):\n*     获取边(start ---> end)的权值<span style="color:#283593;font-weight:bold">(长度)</span>\n*     **if** 存在边 :\n*      路径(start ---> end)的长度为边权值\n*      路径(start ---> end), end的前一结点为start\n*     **else** (不存在边) :\n*      路径(start ---> end)的长度为边权值上限\n*      路径(start ---> end), end的前一结点不存在(predecessor[start][end]设为-1)\n\n* - **2 动态规划**\n\n* **for loop** 遍历intermediate<span style="color:#283593;font-weight:bold">(中间点)</span> :\n*   **for loop** 遍历起点 :\n*    **for loop** 遍历终点 :\n*     (松弛)\n*     **if** 路径(start ---> intermediate) + 路径(intermediate ---> end) < 路径(start ---> end) :\n*      路径(start ---> end) <= 路径(start ---> intermediate) + 路径(intermediate ---> end)\n*      路径(start ---> end)终点的前一结点, 修改为路径(intermediate ---> end)终点的前一结点\n*** --------------------------------*/template<typename TVertex, typename TWeight>void Floyd(const Graph<TVertex, TWeight>& graph, vector<vector<TWeight> >& distance, vector<vector<int> >& predecessor) {// ---------- 1 使用图的信息填充distance和predecessor数组 ----------for (unsigned int start = 0; start < graph.VertexCount(); start++) { // for loop 遍历start(起点)for (unsigned int end = 0; end < graph.VertexCount(); end++) { // for loop 遍历end(终点)if (start == end) { // if start等于enddistance[start][end] = TWeight(); // 路径(start ---> start)长度初始化predecessor[start][end] = (int)start; // 路径(start ---> end), start的前一结点为start} else { // else (start不等于end)TWeight weight;bool res = graph.GetWeightByVertexIndex(start, end, weight); // 获取边(start ---> end)的权值(长度)if (res) { // if 存在边distance[start][end] = weight; // 路径(start ---> end)的长度为边权值predecessor[start][end] = (int)start; // 路径(start ---> end), end的前一结点为start} else { // else (不存在边)distance[start][end] = graph.MaxWeight(); // 路径(start ---> end)的长度为边权值上限predecessor[start][end] = -1; // 路径(start ---> end), end的前一结点不存在(predecessor[start][end]设为-1)}}}}// ---------- 2 动态规划 ----------for (unsigned int intermediate = 0; intermediate < graph.VertexCount(); intermediate++) { // for loop 遍历intermediate(中间点)for (unsigned int start = 0; start < graph.VertexCount(); start++) { // for loop 遍历起点for (unsigned int end = 0; end < graph.VertexCount(); end++) { // for loop 遍历终点// --- 松弛操作 ---// 如果// 边 (start --> intermediate) 的weight// +// 边 (intermediate --> end) 的weight// <// 边 (start --------------------> end) 的weight// 则// 更新distance[start][end] 和 predecessor[start][end]// (松弛)if (distance[start][intermediate] + distance[intermediate][end] < distance[start][end]) { // if 路径(start ---> intermediate) + 路径(intermediate ---> end) < 路径(start ---> end)distance[start][end] = distance[start][intermediate] + distance[intermediate][end]; // 路径(start ---> end) <= 路径(start ---> intermediate) + 路径(intermediate ---> end)predecessor[start][end] = predecessor[intermediate][end]; // 路径(start ---> end)终点的前一结点, 修改为路径(intermediate ---> end)终点的前一结点}}}}}/*!* @brief **打印单源最短路径(SSSP)*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param starting_vertex 起点* @param distance 最短路径数组, distance[i]表示: 起始结点到索引i结点的最短路径* @param predecessor 前一结点数组, predecessor[i]表示: 最短路径中, 索引i结点的前一结点* @note* 打印单源最短路径(SSSP)* --------------------* --------------------** distance[i]表示: 起始结点到索引i结点的最短路径\n* predecessor[i]表示: 最短路径中, 索引i结点的前一结点\n** --------------------* 打印一段文本\n\n* 获取起点索引\n* 声明inverted_predecessors<span style="color:#283593;font-weight:bold">(反向前驱数组)</span>, 并分配内存\n\n* **for loop** 遍历结点索引(当前索引作为路径终点索引) :\n\n*   **if** 起点索引 == 终点索引 :\n*    continue\n\n*   初始化cur_predecessor_index<span style="color:#283593;font-weight:bold">(最短路径当前结点的前驱结点索引)</span>为ending_vertex_index(终点索引)\n*   初始化i<span style="color:#283593;font-weight:bold">(inverted_predecessors的数组索引)</span>为0\n\n*   **while loop** 当前结点的前驱结点 不等于 起点 :\n*    inverted_predecessors[i]被赋值为当前结点的前驱结点\n*    cur_predecessor_index更新为predecessor[cur_predecessor_index](向前驱方向进行)\n*    i++(填充inverted_predecessors的下一个位置的内容)\n\n*   获取当前终点的索引\n*   打印一段文本\n\n*   (使用inverted_predecessors数组打印出路径, 对inverted_predecessor数组从后向前, 依次打印)\n*   **while loop** i > 0 :\n*    i--\n*    获取inverted_predecessors[i]对应的结点, 赋给cur_vertex\n*    打印cur_vertex\n\n*   打印一段文本\n\n* 释放inverted_predecessors\n*** --------------------*/template<typename TVertex, typename TWeight>void PrintSingleSourceShortestPath(const Graph<TVertex, TWeight>& graph,const TVertex& starting_vertex,TWeight distance[],const int predecessor[]){cout << "### 从起始点(" << starting_vertex << ")到其他各顶点的最短路径 ###" << endl; // 打印一段文本int starting_vertex_index = graph.GetVertexIndex(starting_vertex); // 获取起点索引int* inverted_predecessors = new int[graph.VertexCount()]; // 声明inverted_predecessors(反向前驱数组), 并分配内存for (unsigned int ending_vertex_index = 0; // for loop 遍历结点索引(当前索引作为路径终点索引)ending_vertex_index < graph.VertexCount();ending_vertex_index++){if (ending_vertex_index == starting_vertex_index) { // if 起点索引 == 终点索引continue; // continue}int cur_predecessor_index = (int)ending_vertex_index; // 初始化cur_predecessor_index(最短路径当前结点的前驱结点索引)为ending_vertex_index(终点索引)int i = 0; // 初始化i(inverted_predecessors的数组索引)为0while (cur_predecessor_index != starting_vertex_index) { // while loop 当前结点的前驱结点 不等于 起点inverted_predecessors[i] = cur_predecessor_index; // inverted_predecessors[i]被赋值为当前结点的前驱结点cur_predecessor_index = predecessor[cur_predecessor_index]; // cur_predecessor_index更新为predecessor[cur_predecessor_index](向前驱方向进行)i++; // i++(填充inverted_predecessors的下一个位置的内容)}TVertex ending_vertex;graph.GetVertexByIndex(ending_vertex_index, ending_vertex); // 获取当前终点的索引cout << "起始点(" << starting_vertex << ")到结点(" << ending_vertex << ")的最短路径为:"; // 打印一段文本cout << starting_vertex << " ";// (使用inverted_predecessors数组打印出路径, 对inverted_predecessor数组从后向前, 依次打印)while (i > 0) { // while loop i > 0i--; // i减1TVertex cur_vertex;graph.GetVertexByIndex(inverted_predecessors[i], cur_vertex); // 获取inverted_predecessors[i]对应的结点, 赋给cur_vertexcout << cur_vertex << " "; // 打印cur_vertex}cout << ", ";cout << "最短路径长度为:" << distance[ending_vertex_index] << endl; // 打印一段文本}delete[] inverted_predecessors; // 释放inverted_predecessors}/*!* @brief **打印单源最短路径(在多源最短路径中)(递归)*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param predecessor 前一结点数组* @param starting_vertex_index 起点索引* @param ending_vertex_index 终点索引* @note* 打印单源最短路径(在多源最短路径中)(递归)* -----------------------------------* -----------------------------------** <span style="color:#893834">* **Sssp**: Single source shortest path, 单源最短路径\n* **Mssp**: Multiple source shortest path, 单源最短路径\n* **predecessor[i][j]**: 路径(索引i结点 ----> 索引j结点)的最短路径中, 索引j结点的前一结点\n* </span>** -----------------------------------* + **1 合法性校验**\n\n* **if** predecessor[starting_vertex_index][ending_vertex_index]为-1, 即起点到结点不存在最短路径 :\n*   打印"没有路径"\n*   返回false\n\n* + **2 递归执行**\n\n* **if** 起点索引 不等于 终点索引 :\n*   对最短路径中的starting_vertex_index<span style="color:#283593;font-weight:bold">(起点索引)</span>和* predecessor[starting_vertex_index][ending_vertex_index]<span style="color:#283593;font-weight:bold">(终点的前一结点索引)</span>, 调用PrintSsspInMsspRecursive\n\n*   **if** 执行结果失败 :\n*    返回false\n\n* + **3 打印结点**\n\n* 声明ending_vertex<span style="color:#283593;font-weight:bold">(终点)</span>\n* 获取ending_vertex\n* 打印终点\n\n* + **4 退出函数**\n\n* 返回true\n*** -----------------------------------*/template<typename TVertex, typename TWeight>bool PrintSsspInMsspRecursive(const Graph<TVertex, TWeight>& graph,vector<vector<int> > predecessor,int starting_vertex_index,int ending_vertex_index){// ---------- 1 合法性校验 ----------if (predecessor[starting_vertex_index][ending_vertex_index] == -1) { // if 终点的前一结点索引为-1, 即起点到结点不存在最短路径cout << "没有路径" << endl; // 打印"没有路径"return false; // 返回false}// ---------- 2 递归执行 ----------if (starting_vertex_index != ending_vertex_index) { // if 起点索引 不等于 终点索引bool res = PrintSsspInMsspRecursive(graph, // 对最短路径中的起点索引和终点的前一结点索引, 调用PrintSsspInMsspRecursivepredecessor,starting_vertex_index,predecessor[starting_vertex_index][ending_vertex_index]);if (!res) { // if 执行结果失败return false; // 返回false}}// ---------- 3 打印结点 ----------TVertex ending_vertex; // 声明ending_vertex(终点)graph.GetVertexByIndex(ending_vertex_index, ending_vertex); // 获取ending_vertexcout << ending_vertex << " "; // 打印ending_vertex// ---------- 4 退出函数 ----------return true; // 返回true}/*!* @brief **打印多源最短路径(弗洛伊德Floyd等MSSP)*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param distance 最短路径数组, distance[i][j]表示: 索引i结点到索引j结点的最短路径* @param predecessor 前一结点数组, predecessor[i][j]表示: 索引i结点到索引j结点最短路径中, j的前一结点* @note* 打印多源最短路径(弗洛伊德Floyd等MSSP)* ---------------------------------* ---------------------------------** 按照不同起始点, 分类打印** ---------------------------------* **for loop** 遍历结点索引i :\n*   获取i对应的结点, 作为当前路径起点\n*   打印一段文字\n*   **for loop** 遍历结点索引j :\n*    **if** i等于j(代表起点与终点重合) :\n*     continue\n*    获取j对应的结点, 作为当前路径终点\n*    打印一段文字\n*    对i<span style="color:#283593;font-weight:bold">(当前路径起点索引)</span>和j<span style="color:#283593;font-weight:bold">(当前路径终点索引)</span>调用PrintSsspInMsspRecursive\n*    **if** 存在最短路径 :\n*     打印最短路径长度\n*** ---------------------------------*/template<typename TVertex, typename TWeight>void PrintMultipleSourceShortestPath(const Graph<TVertex, TWeight>& graph,const vector<vector<TWeight> >& distance,const vector<vector<int> >& predecessor){for (unsigned int i = 0; i < graph.VertexCount(); i++) { // for loop 遍历结点索引iTVertex cur_starting_vertex;graph.GetVertexByIndex(i, cur_starting_vertex); // 获取i对应的结点, 作为当前路径起点cout << "--- 从起始点(" << cur_starting_vertex << ")到其他各顶点的最短路径 ---" << endl; // 打印一段文字for (unsigned int j = 0; j < graph.VertexCount(); j++) { // for loop 遍历结点索引jif (i == j) { // if i等于j(代表起点与终点重合)continue;}TVertex ending_vertex;graph.GetVertexByIndex(j, ending_vertex); // 获取j对应的结点, 作为当前路径终点cout << "起始点(" << cur_starting_vertex << ")到结点(" << ending_vertex << ")的最短路径为: "; // 打印一段文字bool res = PrintSsspInMsspRecursive(graph, predecessor, i, j); // 对i(当前路径起点索引)和j(当前路径终点索引)调用PrintSsspInMsspRecursiveif (res) { // if 存在最短路径cout << ", 最短路径长度为: " << distance[i][j] << endl; // 打印最短路径长度}}cout<<endl;}}/*!* @brief **关键路径*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @param graph 图* @param starting_vertex 起点* @return 起点索引到各结点索引的关键路径数组* @note* 关键路径* -------* -------* <p>* + **1 初始化**\n\n* 声明critical_paths<span style="color:#283593;font-weight:bold">(起点索引到各结点索引的关键路径数组)</span>\n* 声明visited_vertex_index_set<span style="color:#283593;font-weight:bold">(已访问结点索引的集合)</span>\n* 声明vertex_index_queue<span style="color:#283593;font-weight:bold">(结点索引队列)</span>\n\n* 初始化starting_vertex_index<span style="color:#283593;font-weight:bold">(起点的结点索引)</span>\n\n* 将starting_vertex_index插入visited_vertex_index_set\n* 将starting_vertex_index插入vertex_index_queue\n\n* **for loop** 遍历图的结点索引 :\n*   critical_paths各元素值初始化\n\n* + **2 BFS**\n\n* **while loop** vertex_index_queue不为空 :\n*   获取队头, 作为cur_start_index<span style="color:#283593;font-weight:bold">(当前起点)</span>\n*   队头出队\n\n*   **for loop** 遍历图结点索引, 作为cur_end_index<span style="color:#283593;font-weight:bold">(当前终点)</span> :\n*    声明cur_weight<span style="color:#283593;font-weight:bold">(当前边权重)</span>\n*    获取边(cur_start_index ---> cur_end_index)的权重, 赋给cur_weight\n*    **if** 存在边 && 参数起点到当前边起点的关键路径距离 + 当前边权重<span style="color:#283593;font-weight:bold">(边长)</span> > 参数起点到当前边终点的关键路径距离 :\n*     当前边终点入队\n\n*    cur_end_index插入到visited_vertex_index_set\n\n* + **3 退出函数**\n\n* 返回critical_paths\n* </p>* <hr>*/template<typename TVertex, typename TWeight>vector<TWeight> GetCriticalPath(const Graph<TVertex, TWeight>& graph, const TVertex& starting_vertex) {// ---------- 1 初始化 ----------vector<TWeight> critical_paths; // 声明critical_paths(起点索引到各结点索引的关键路径数组)set<int> visited_vertex_index_set; // 声明visited_vertex_index_set(已访问结点索引的集合)queue<int> vertex_index_queue; // 声明vertex_index_queue(结点索引队列)int starting_vertex_index = graph.GetVertexIndex(starting_vertex); // 初始化starting_vertex_index(起点的结点索引)visited_vertex_index_set.insert(starting_vertex_index); // 将starting_vertex_index插入visited_vertex_index_setvertex_index_queue.push(starting_vertex_index); // 将starting_vertex_index插入vertex_index_queuefor (unsigned int i = 0; i < graph.VertexCount(); i++) { // for loop 遍历图的结点索引 :critical_paths.push_back(TWeight()); // critical_paths各元素值初始化}// ---------- 2 BFS ----------while (!vertex_index_queue.empty()) { // while loop vertex_index_queue不为空 :int cur_start_index = vertex_index_queue.front(); // 获取队头, 作为cur_start_index(当前起点)vertex_index_queue.pop(); // 队头出队for (int cur_end_index = 0; cur_end_index < int(graph.VertexCount()); cur_end_index++) { // for loop 遍历图结点索引, 作为cur_end_index(当前终点)TWeight cur_weight; // 声明cur_weight(当前边权重)bool res = graph.GetWeightByVertexIndex(cur_start_index, cur_end_index, cur_weight); // 获取边(cur_start_index ---> cur_end_index)的权重, 赋给cur_weightif (res && critical_paths[cur_start_index] + cur_weight > critical_paths[cur_end_index]) {critical_paths[cur_end_index] = critical_paths[cur_start_index] + cur_weight;if (visited_vertex_index_set.find(cur_end_index) == visited_vertex_index_set.end()) { // if 存在边 && 参数起点到当前边起点的关键路径距离 + 当前边权重(边长) > 参数起点到当前边终点的关键路径距离vertex_index_queue.push(cur_end_index); // 当前边终点入队}visited_vertex_index_set.insert(cur_end_index); // cur_end_index插入到visited_vertex_index_set}}}// ---------- 3 退出函数 ----------return critical_paths; // 返回critical_paths}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。
1. 开源生态
2. 协作、人、软件
3. 评估模型