代码拉取完成，页面将自动刷新
同步操作将从 cyberdash/数据结构（C++模板实现） 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
/*!
* @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_set
DfsOnVertexRecursive(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_vertex
bool 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_exists
if (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 入度 > 0
return 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_set
topology_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_exists
neighbor_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_set
visited_vertex_set.insert(vertex); // 插入vertex(起点)
// ---------- 2 初始化visited_queue(结点队列) ----------
queue<TVertex> vertex_queue; // 声明vertex_queue
vertex_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_exists
neighbor_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 结点数为0
return 0; // 返回0
}
// 2 ---------- 声明visited_vertex_set(已访问结点集合) ----------
set<TVertex> visited_vertex_set; // 声明visited_vertex_set(已访问结点集合)
int count = 1; // 初始连通分量数量为1
for (unsigned int i = 0; i < graph.VertexCount(); i++) { // for loop 遍历结点索引
TVertex vertex; // 声明vertex(当前结点)
bool res = graph.GetVertexByIndex(i, vertex); // 获取i(当前索引)对应的结点vertex
if (!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++; // 连通分量数量+1
cout<<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); // 获取weight
if (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_edge
int 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_edge
min_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_set
TVertex 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_weight
Edge<TVertex, TWeight> cur_edge(cur_mst_vertex, cur_neighbor_vertex, cur_weight); // 使用 边(cur_mst_vertex --- cur_neighbor_vertex) 生成cur_edge
min_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_exists
cur_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_index
for (unsigned int i = 0; i < graph.VertexCount(); i++) { // for loop 遍历结点
TVertex cur_vertex; // 声明cur_vertex(当前结点)
graph.GetVertexByIndex(i, cur_vertex); // 获取cur_vertex
TWeight 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_index
Path<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; // (起点 ---> 起点)的最短路径, 权值(长度)初始化为0
predecessor[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_weight
if (!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_weight
if (!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设为true
break; // 跳出循环(发现负权回路)
}
}
// ---------- 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等于end
distance[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的数组索引)为0
while (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 > 0
i--; // i减1
TVertex cur_vertex;
graph.GetVertexByIndex(inverted_predecessors[i], cur_vertex); // 获取inverted_predecessors[i]对应的结点, 赋给cur_vertex
cout << 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, // 对最短路径中的起点索引和终点的前一结点索引, 调用PrintSsspInMsspRecursive
predecessor,
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_vertex
cout << 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 遍历结点索引i
TVertex 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 遍历结点索引j
if (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(当前路径终点索引)调用PrintSsspInMsspRecursive
if (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_set
vertex_index_queue.push(starting_vertex_index); // 将starting_vertex_index插入vertex_index_queue
for (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_weight
if (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
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手