代码拉取完成，页面将自动刷新
同步操作将从 cyberdash/数据结构（C++模板实现） 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
/*!
* @file test.cpp
* @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
* @brief 图测试.cpp文件
* @version 0.2.1
* @date 2021-10-9
*/
#include "test.h"
#include "min_priority_queue.h"
#include "graph_algorithm.h"
#include "graph_algorithm.cpp"
using namespace std;
/*!
* @brief **测试-图-基础函数**
* @note
* 测试-图-基础函数
* --------------
* --------------
*
* --------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试基础函数**\n\n
* 构造adjacency_list_directed_graph(邻接表有向图)\n
* 依次删除1个城市, 然后打印图\n\n
* 构造adjacency_list_undirected_graph(邻接表无向图)\n
* 依次删除1个城市, 然后打印图\n\n
* 构造matrix_directed_graph(矩阵有向图)\n
* 依次删除1个城市, 然后打印图\n\n
* 构造matrix_undirected_graph(矩阵无向图)\n
* 依次删除1个城市, 然后打印图\n\n
*
*
* --------------
*/
void TestBaseFunctions() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph BaseFunctions |"<<endl;
cout<<"| 测试-图-基础函数 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
unsigned int edge_count = 9;
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" }; // 初始化起点数组
vector<string> ending_vertices{ "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" }; // 初始化终点数组
vector<double> weights{ 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 }; // 初始化边权值数组
vector<Edge<string, double> > edges; // 声明边vector
// 构造边vector
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// ---------- 2 测试基础函数 ----------
// 构造adjacency_list_directed_graph(邻接表有向图)
AdjacencyListGraph<string, double> adjacency_list_directed_graph(Graph<string, double>::DIRECTED, 10, 1000, edges, vertices);
// 依次删除1个城市, 然后打印图
cout << "---------- 1 邻接表有向图删除结点 ----------" << endl << endl;
adjacency_list_directed_graph.RemoveVertex("北京");
adjacency_list_directed_graph.RemoveVertex("上海");
adjacency_list_directed_graph.RemoveVertex("深圳");
cout << adjacency_list_directed_graph << endl << endl;
// 构造adjacency_list_undirected_graph(邻接表无向图)
AdjacencyListGraph<string, double> adjacency_list_undirected_graph(Graph<string, double>::UNDIRECTED, 10, 1000, edges, vertices);
// 依次删除1个城市, 然后打印图
cout << "---------- 2 邻接表无向图删除结点 ----------" << endl << endl;
adjacency_list_undirected_graph.RemoveVertex("北京");
adjacency_list_undirected_graph.RemoveVertex("上海");
adjacency_list_undirected_graph.RemoveVertex("深圳");
cout << adjacency_list_undirected_graph << endl << endl;
// 构造matrix_directed_graph(矩阵有向图)
MatrixGraph<string, double> matrix_directed_graph(Graph<string, double>::DIRECTED, 10, 1000, edges, vertices);
// 依次删除1个城市, 然后打印图
cout << "---------- 3 矩阵有向图删除结点 ----------" << endl << endl;
matrix_directed_graph.RemoveVertex("北京");
matrix_directed_graph.RemoveVertex("上海");
matrix_directed_graph.RemoveVertex("深圳");
cout << matrix_directed_graph << endl << endl;
// 构造matrix_undirected_graph(矩阵无向图)
MatrixGraph<string, double> matrix_undirected_graph(Graph<string, double>::UNDIRECTED, 10, 1000, edges, vertices);
// 依次删除1个城市, 然后打印图
cout << "---------- 4 矩阵无向图删除结点 ----------" << endl << endl;
matrix_undirected_graph.RemoveVertex("北京");
matrix_undirected_graph.RemoveVertex("上海");
matrix_undirected_graph.RemoveVertex("深圳");
cout << matrix_undirected_graph << endl << endl;
cout << "-------------------------------------------------------------" << endl;
}
/*!
* @brief **测试-矩阵图-打印矩阵**
* @note
* 测试-矩阵图-打印矩阵
* -----------------
* -----------------
*
* -----------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* 构造无向矩阵图\n\n
* + **2 打印矩阵**\n\n
*
*
* -----------------
*/
void TestMatrixGraphPrintMatrix() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test MatrixGraph PrintMatrix |"<<endl;
cout<<"| 测试-矩阵图-打印矩阵 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
unsigned int edge_count = 9;
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices{ "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights{ 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 }; // 边权重数组
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// 构造无向矩阵图
MatrixGraph<string, double> matrix_graph(10, 1000, edges, vertices);
// ---------- 2 打印矩阵 ----------
cout << "打印矩阵:" << endl << endl;
matrix_graph.PrintMatrix();
cout<<"-------------------------------------------------------------"<<endl;
}
/*!
* @brief **测试-图-深度优先遍历(递归)**
* @note
* 测试-图-深度优先遍历(递归)
* -----------------------
* -----------------------
*
* -----------------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表图深度优先遍历**\n\n
* 构造adjacency_list_graph(邻接表无向图)\n
* 以"北京"为起点进行深度优先遍历\n\n
* + **3 测试矩阵图深度优先遍历**\n\n
* 构造matrix_graph(矩阵无向图)\n
* 以"北京"为起点进行深度优先遍历\n
*
*
* -----------------------
*/
void TestDfsRecursive() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph Dfs |"<<endl;
cout<<"| 测试-图-深度优先遍历(递归) |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
unsigned int edge_count = 9;
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices{ "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights{ 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 };
// 初始化边信息
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// ---------- 2 测试邻接表图深度优先遍历 ----------
cout<<"---------- 邻接表图 ----------"<<endl;
AdjacencyListGraph<string, double> adjacency_list_graph(10, 1000, edges, vertices); // 构造adjacency_list_graph(邻接表无向图)
Dfs(adjacency_list_graph, vertices[0]); // "北京"为起点进行深度优先遍历
// ---------- 3 测试矩阵图深度优先遍历 ----------
cout<<endl<<"---------- 矩阵图 ----------"<<endl;
MatrixGraph<string, double> matrix_graph(10, 1000, edges, vertices); // 构造matrix_graph(矩阵无向图)
Dfs(matrix_graph, vertices[0]); // 以"北京"为起点进行深度优先遍历
cout<<"-------------------------------------------------------------"<<endl;
}
/*!
* @brief **测试-图-广度优先遍历**
* @note
* 测试-图-广度优先遍历
* -----------------
* -----------------
*
* -----------------
*
*
* -----------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表图广度优先遍历**\n\n
* 构造adjacency_list_undirected_graph(邻接表无向图)\n
* 以"北京"为起点进行bfs遍历\n\n
* + **3 测试矩阵图广度优先遍历**\n\n
* 构造matrix_undirected_graph(矩阵无向图)\n
* 以"北京"为起点进行bfs遍历\n
*/
void TestBFS() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph Bfs |"<<endl;
cout<<"| 测试-图-广度优先遍历 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
unsigned int edge_count = 9;
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices{ "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights{ 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 };
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// ---------- 2 测试邻接表图广度优先遍历 ----------
cout<<"---------- 邻接表图 ----------"<<endl;
AdjacencyListGraph<string, double> adjacency_list_undirected_graph(10, 1000, edges, vertices); // 构造adjacency_list_undirected_graph(邻接表无向图)
Bfs(adjacency_list_undirected_graph, vertices[0]); // 以"北京"为起点进行bfs遍历
// ---------- 3 测试矩阵图广度优先遍历 ----------
cout<<endl<<"---------- 矩阵图 ----------"<<endl;
MatrixGraph<string, double> matrix_undirected_graph(10, 1000, edges, vertices); // 构造matrix_undirected_graph(矩阵无向图)
Bfs(matrix_undirected_graph, vertices[0]); // 以"北京"为起点进行bfs遍历
cout<<"-------------------------------------------------------------"<<endl;
}
/*!
* @brief **测试-图-连通分量**
* @note
* 测试-图-连通分量
* --------------
* --------------
*
* --------------
*
*
* --------------
* + **1 构造邻接表图**\n\n
* 声明adjacency_list_graph(邻接表图)\n
* 插入结点0, 1, 2, 3\n
* 插入边(0 , 1)和边(2, 3)\n\n
* + **2 构造矩阵图**\n\n
* 声明matrix_graph(矩阵图)\n
* 插入结点0, 1, 2, 3\n
* 插入边(0 , 1)和边(2, 3)\n\n
* + **3 邻接表图求连通分量**\n\n
* 调用Components\n\n
* + **4 矩阵图求连通分量**\n\n
* 调用Components\n\n
*
*
* --------------
*/
void TestComponents() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph Components |"<<endl;
cout<<"| 测试-图-连通分量 |"<<endl;
cout<<"| 节点: |"<<endl;
cout<<"| 0, 1, 2, 3 |"<<endl;
cout<<"| 边: |"<<endl;
cout<<"| 0-1权值: 0.8 |"<<endl;
cout<<"| 2-3权值: 7.3 |"<<endl<<endl;
// ---------- 1 构造邻接表图 ----------
// 声明adjacency_list_graph(邻接表图)
AdjacencyListGraph<int, double> adjacency_list_graph(10, 10000);
// 插入结点0, 1, 2, 3
adjacency_list_graph.InsertVertex(0);
adjacency_list_graph.InsertVertex(1);
adjacency_list_graph.InsertVertex(2);
adjacency_list_graph.InsertVertex(3);
// 插入边(0 , 1)和边(2, 3)
adjacency_list_graph.InsertEdge(0, 1, 0.8);
adjacency_list_graph.InsertEdge(2, 3, 7.3);
// ---------- 2 构造矩阵图 ----------
// 声明matrix_graph(矩阵图)
MatrixGraph<int, double> matrix_graph(10, 10000);
// 插入结点0, 1, 2, 3
matrix_graph.InsertVertex(0);
matrix_graph.InsertVertex(1);
matrix_graph.InsertVertex(2);
matrix_graph.InsertVertex(3);
// 插入边(0 , 1)和边(2, 3)
matrix_graph.InsertEdge(0, 1, 0.8);
matrix_graph.InsertEdge(2, 3, 7.3);
// ---------- 3 邻接表图求连通分量 ----------
cout<<"---------- 邻接表图 ----------"<<endl;
Components(adjacency_list_graph); // 调用Components
// ---------- 4 矩阵图求连通分量 ----------
cout<<"---------- 矩阵图 ----------"<<endl;
Components(matrix_graph); // 调用Components
cout<<"-------------------------------------------------------------"<<endl;
}
/*!
* @brief **测试-图-最小生成树Kruskal**
* @note
* 测试-图-最小生成树Kruskal
* ----------------------
* ----------------------
*
* ----------------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表图Kruskal**\n\n
* 构造adjacency_list_undirected_graph(邻接表无向图)\n
* 初始化adj_min_span_tree(邻接表图的最小生成树)\n\n
* 调用Kruskal求最小生成树\n
* 打印最小生成树\n\n
* + **3 测试矩阵图Kruskal**\n\n
* 构造matrix_undirected_graph(矩阵无向图)\n
* 初始化matrix_min_span_tree(矩阵图的最小生成树)\n\n
* 调用Kruskal求最小生成树\n
* 打印最小生成树\n\n
*
*
* -------------------
*/
void TestKruskal() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph Kruskal |"<<endl;
cout<<"| 测试-图-最小生成树Kruskal |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
unsigned int edge_count = 9;
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices{ "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights{ 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 };
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// ---------- 2 测试邻接表图Kruskal ----------
cout<<"---------- 邻接表图 ----------"<<endl;
AdjacencyListGraph<string, double> adjacency_list_graph(10, 1000, edges, vertices); // 构造adjacency_list_undirected_graph(邻接表无向图)
MinimumSpanTree<string, double> adj_min_span_tree(100); // 初始化adj_min_span_tree(邻接表图的最小生成树)
Kruskal(adjacency_list_graph, adj_min_span_tree); // 调用Kruskal求最小生成树
adj_min_span_tree.Print(); // 打印最小生成树
// ---------- 3 测试矩阵图Kruskal ----------
cout<<endl<<"---------- 矩阵图 ----------"<<endl;
MatrixGraph<string, double> matrix_graph(10, 1000, edges, vertices); // 构造matrix_undirected_graph(矩阵无向图)
MinimumSpanTree<string, double> matrix_min_span_tree(100); // 初始化matrix_min_span_tree(邻接表图的最小生成树)
Kruskal(matrix_graph, matrix_min_span_tree); // 调用Kruskal求最小生成树
matrix_min_span_tree.Print(); // 打印最小生成树
cout << "-------------------------------------------------------------" << endl;
}
/*!
* @brief **测试-图-最小生成树Prim**
* @note
* 测试-图-最小生成树Prim
* -------------------
* -------------------
*
* -------------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表图Prim**\n\n
* 构造adjacency_list_undirected_graph(邻接表无向图)\n
* 初始化adj_min_span_tree(邻接表图的最小生成树)\n\n
* 调用Prim求最小生成树\n
* 打印最小生成树\n\n
* + **3 测试矩阵图Prim**\n\n
* 构造matrix_undirected_graph(矩阵无向图)\n
* 初始化matrix_min_span_tree(矩阵图的最小生成树)\n\n
* 调用Prim求最小生成树\n
* 打印最小生成树\n\n
*
*
* -------------------
*/
void TestPrim() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph Prim |"<<endl;
cout<<"| 测试-图-最小生成树Prim |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
unsigned int edge_count = 9;
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices{ "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights{ 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 };
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// ---------- 2 测试邻接表图Prim ----------
cout<<"---------- 邻接表图 ----------"<<endl;
AdjacencyListGraph<string, double> adjacency_list_undirected_graph(10, 1000, edges, vertices); // 构造adjacency_list_undirected_graph(邻接表无向图)
MinimumSpanTree<string, double> adj_min_span_tree(100); // 初始化adj_min_span_tree(邻接表图的最小生成树)
Prim(adjacency_list_undirected_graph, adj_min_span_tree); // 调用Prim求最小生成树
adj_min_span_tree.Print(); // 打印最小生成树
// ---------- 3 测试矩阵图Prim ----------
cout<<endl<<"---------- 矩阵图 ----------"<<endl;
MatrixGraph<string, double> matrix_undirected_graph(10, 1000, edges, vertices); // 构造matrix_undirected_graph(矩阵无向图)
MinimumSpanTree<string, double> matrix_min_span_tree(100); // 初始化matrix_min_span_tree(邻接表图的最小生成树)
Prim(matrix_undirected_graph, matrix_min_span_tree); // 调用Prim求最小生成树
matrix_min_span_tree.Print(); // 打印最小生成树
cout<<endl<<"-------------------------------------------------------------"<<endl<<endl;
}
/*!
* @brief **测试-图-最短路径Dijkstra**
* @note
* 测试-图-最短路径Dijkstra
* ----------------------
* ----------------------
*
* ----------------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表图Dijkstra**\n\n
* 构造adjacency_list_undirected_graph(邻接表无向图)\n
* 声明adjacency_list_graph_min_distances(邻接表图最短路径数组)\n
* 声明adjacency_list_graph_predecessors(最短路径前驱结点数组)\n\n
* 调用Dijkstra函数, 求"北京"到其他各点的最短路径\n
* 调用PrintSingleSourceShortestPath打印"北京"到各城市的最短路径\n\n
* + **3 测试矩阵图Dijkstra**\n\n
* 构造matrix_undirected_graph(矩阵无向图)\n
* 声明matrix_graph_min_distances(邻接表图最短路径数组)\n
* 声明matrix_graph_predecessors(最短路径前驱结点数组)\n\n
* 调用Dijkstra函数, 求"北京"到其他各点的最短路径\n
* 调用PrintSingleSourceShortestPath打印"北京"到各城市的最短路径\n\n
*
*
* ----------------------
*/
void TestDijkstra() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Dijkstra |"<<endl;
cout<<"| 测试-图-最短路径Dijkstra |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
unsigned int edge_count = 9;
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices{ "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights{ 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 };
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// ---------- 2 测试邻接表图Dijkstra ----------
cout << "---------- 邻接表图 ----------" << endl;
AdjacencyListGraph<string, double> adjacency_list_undirected_graph(10, 1000, edges, vertices); // 构造adjacency_list_undirected_graph(邻接表无向图)
double adjacency_list_graph_min_distances[10]; // 声明adjacency_list_graph_min_distances(邻接表图最短路径数组)
int adjacency_list_graph_predecessors[10]; // 声明adjacency_list_graph_predecessors(最短路径前驱结点数组)
// 调用Dijkstra函数, 求"北京"到其他各点的最短路径
Dijkstra(adjacency_list_undirected_graph, vertices[0], adjacency_list_graph_min_distances, adjacency_list_graph_predecessors);
// 调用PrintSingleSourceShortestPath打印"北京"到各城市的最短路径
PrintSingleSourceShortestPath(adjacency_list_undirected_graph, vertices[0], adjacency_list_graph_min_distances, adjacency_list_graph_predecessors);
// ---------- 3 测试矩阵图Dijkstra ----------
cout << endl << endl << "---------- 矩阵图 ----------" << endl;
MatrixGraph<string, double> matrix_undirected_graph(1, 10, 1000, edges, vertices); // 构造matrix_undirected_graph(矩阵无向图)
double matrix_graph_min_distances[10]; // 声明matrix_graph_min_distances(邻接表图最短路径数组)
int matrix_graph_predecessors[10]; // 声明matrix_graph_predecessors(最短路径前驱结点数组)
// 调用Dijkstra函数, 求"北京"到其他各点的最短路径
Dijkstra(matrix_undirected_graph, vertices[0], matrix_graph_min_distances, matrix_graph_predecessors);
// 调用PrintSingleSourceShortestPath打印"北京"到各城市的最短路径
PrintSingleSourceShortestPath(matrix_undirected_graph, vertices[0], matrix_graph_min_distances, matrix_graph_predecessors);
cout<<"-------------------------------------------------------------"<<endl<<endl;
}
/*!
* @brief **测试-图-最短路径BellmanFord**
* @note
* 测试-图-最短路径BellmanFord
* ------------------------
* ------------------------
*
* ------------------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表图BellmanFord**\n\n
* 构造adjacency_list_undirected_graph(邻接表无向图)\n
* 声明adjacency_list_graph_min_distances(邻接表图最短路径数组)\n
* 声明adjacency_list_graph_predecessors(最短路径前驱结点数组)\n\n
* 调用BellmanFord函数, 求"北京"到其他各点的最短路径\n
* 调用PrintSingleSourceShortestPath打印"北京"到各城市的最短路径\n\n
* + **3 测试矩阵图BellmanFord**\n\n
* 构造matrix_undirected_graph(矩阵无向图)\n
* 声明matrix_graph_min_distances(邻接表图最短路径数组)\n
* 声明matrix_graph_predecessors(最短路径前驱结点数组)\n\n
* 调用BellmanFord函数, 求"北京"到其他各点的最短路径\n
* 调用PrintSingleSourceShortestPath打印"北京"到各城市的最短路径\n\n
*
*
* ------------------------
*/
void TestBellmanFord() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph BellmanFord |"<<endl;
cout<<"| 测试-图-最短路径BellmanFord |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
unsigned int edge_count = 9;
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices{ "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights{ 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 }; // 边权重数组
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// ---------- 2 测试邻接表图BellmanFord ----------
cout << "---------- 邻接表图 ----------" << endl;
AdjacencyListGraph<string, double> adjacency_list_graph(10, 1000, edges, vertices); // 构造adjacency_list_undirected_graph(邻接表无向图)
double adjacency_list_graph_min_distances[10]; // 声明adjacency_list_graph_min_distances(邻接表图最短路径数组)
int adjacency_list_graph_predecessors[10]; // 声明adjacency_list_graph_predecessors(最短路径前驱结点数组)
// 调用BellmanFord函数, 求"北京"到其他各点的最短路径
BellmanFord(adjacency_list_graph, vertices[0], adjacency_list_graph_min_distances, adjacency_list_graph_predecessors);
// 调用PrintSingleSourceShortestPath打印"北京"到各城市的最短路径
PrintSingleSourceShortestPath(adjacency_list_graph, vertices[0], adjacency_list_graph_min_distances, adjacency_list_graph_predecessors);
// ---------- 3 测试矩阵图BellmanFord ----------
cout << endl << endl << "---------- 矩阵图 ----------" << endl;
MatrixGraph<string, double> matrix_graph(10, 1000, edges, vertices); // 构造matrix_undirected_graph(矩阵无向图)
double matrix_graph_min_dists[10]; // 声明matrix_graph_min_distances(邻接表图最短路径数组)
int matrix_graph_predecessors[10]; // 声明matrix_graph_predecessors(最短路径前驱结点数组)
// 调用BellmanFord函数, 求"北京"到其他各点的最短路径
BellmanFord(matrix_graph, vertices[0], matrix_graph_min_dists, matrix_graph_predecessors);
// 调用PrintSingleSourceShortestPath打印"北京"到各城市的最短路径
PrintSingleSourceShortestPath(matrix_graph, vertices[0], matrix_graph_min_dists, matrix_graph_predecessors);
cout<<"-------------------------------------------------------------"<<endl<<endl;
}
/*!
* @brief **测试-图-最短路径Floyd**
* @note
* 测试-图-最短路径Floyd
* ------------------
* ------------------
*
* ------------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表有向图Floyd**\n\n
* 构造adjacency_list_directed_graph(邻接表有向图)\n\n
* 初始化adj_list_min_distances(邻接表最短路径二维向量)\n
* 初始化adj_list_predecessors(最短路径前驱结点二维向量)\n\n
* 调用Floyd执行弗洛伊德算法\n
* 打印多源最短路径\n\n
* + **3 测试矩阵有向图Floyd**\n\n
* 构造matrix_directed_graph(矩阵有向图)\n\n
* 初始化matrix_min_distances(矩阵最短路径二维向量)\n
* 初始化matrix_predecessors(最短路径前驱结点二维向量)\n\n
* 调用Floyd执行弗洛伊德算法\n
* 打印多源最短路径\n\n
*
*
* ------------------
*/
void TestFloyd() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Floyd-Warshall |"<<endl;
cout<<"| 测试-图-最短路径Floyd |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
unsigned int edge_count = 9;
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices { "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights { 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 };
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
// ---------- 2 测试邻接表有向图Floyd ----------
cout << "---------- 邻接表图 ----------" << endl;
// 构造adjacency_list_directed_graph(邻接表有向图)
AdjacencyListGraph<string, double> adjacency_list_directed_graph(Graph<string, double>::DIRECTED, 10, 1000, edges, vertices);
// 初始化adj_list_min_distances(邻接表最短路径二维向量)
vector<vector<double> > adj_list_min_distances(adjacency_list_directed_graph.VertexCount(),
vector<double>(adjacency_list_directed_graph.VertexCount()));
// 初始化adj_list_predecessors(最短路径前驱结点二维向量)
vector<vector<int> > adj_list_predecessors(adjacency_list_directed_graph.VertexCount(),
vector<int>(adjacency_list_directed_graph.VertexCount()));
// 调用Floyd执行弗洛伊德算法
Floyd(adjacency_list_directed_graph, adj_list_min_distances, adj_list_predecessors);
// 打印多源最短路径
PrintMultipleSourceShortestPath(adjacency_list_directed_graph,
adj_list_min_distances,
adj_list_predecessors);
// ---------- 3 测试矩阵有向图Floyd ----------
cout << endl << endl << "---------- 矩阵图 ----------" << endl;
// 构造matrix_directed_graph(矩阵有向图)
MatrixGraph<string, double> matrix_directed_graph(Graph<string, double>::DIRECTED, 10, 1000, edges, vertices); // 构造矩阵图
// 初始化matrix_min_distances(矩阵最短路径二维向量)
vector<vector<double> > matrix_min_distances(matrix_directed_graph.VertexCount(),
vector<double>(matrix_directed_graph.VertexCount()));
// 初始化matrix_predecessors(最短路径前驱结点二维向量)
vector<vector<int> > matrix_predecessors(matrix_directed_graph.VertexCount(),
vector<int>(matrix_directed_graph.VertexCount()));
// 调用Floyd执行弗洛伊德算法
Floyd(matrix_directed_graph, matrix_min_distances, matrix_predecessors);
// 打印多源最短路径
PrintMultipleSourceShortestPath(matrix_directed_graph,
matrix_min_distances,
matrix_predecessors);
cout << "-------------------------------------------------------------" << endl << endl;
}
/*!
* @brief **测试-图-拓扑排序**
* @note
* 测试-图-拓扑排序
* --------------
* --------------
*
* --------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表有向图拓扑排序**\n\n
* 初始化adj_list_directed_graph(邻接表有向图)\n
* 打印拓扑排序结果\n\n
* + **3 测试矩阵无向图拓扑排序**\n\n
* 初始化matrix_undirected_graph(矩阵无向图)\n
* 打印拓扑排序结果\n
*
*
* --------------
*/
void TestTopologicalSort() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph TopologySort |"<<endl;
cout<<"| 测试-图-拓扑排序 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
unsigned int edge_count = 9;
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices { "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights { 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 };
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
vector<string> topology_sorted_list;
// ---------- 2 测试邻接表有向图拓扑排序 ----------
cout << "---------- 邻接表图 ----------" << endl;
// 初始化adj_list_directed_graph(邻接表有向图)
AdjacencyListGraph<string, double> adj_list_directed_graph(Graph<string, double>::DIRECTED, 10, 1000, edges, vertices);
bool res = TopologicalSort(adj_list_directed_graph, vertices[0], topology_sorted_list);
if (!res) {
cout<<"拓扑排序失败"<<endl;
return;
}
// 打印拓扑排序结果
for (auto iter = topology_sorted_list.begin(); iter != topology_sorted_list.end(); iter++) {
cout<<*iter<<' ';
}
cout<<endl;
topology_sorted_list.clear(); // 清空topology_sorted_list
// ---------- 3 测试矩阵无向图拓扑排序 ----------
cout << endl << endl << "---------- 矩阵图 ----------" << endl;
// 初始化matrix_undirected_graph(矩阵无向图)
MatrixGraph<string, double> matrix_undirected_graph(Graph<string, double>::UNDIRECTED, 10, 1000, edges, vertices);
res = TopologicalSort(matrix_undirected_graph, vertices[0], topology_sorted_list);
if (!res) {
cout<<"拓扑排序失败"<<endl;
}
// 打印拓扑排序结果
for (auto iter = topology_sorted_list.begin(); iter != topology_sorted_list.end(); iter++) {
cout<<*iter<<' ';
}
cout<<endl;
cout << "-------------------------------------------------------------" << endl << endl;
}
/*!
* @brief **测试-图-关键路径**
* @note
* 测试-图-关键路径
* --------------
* --------------
*
* --------------
* + **1 初始化图的基本信息**\n\n
* 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)\n
* 初始化边信息\n\n
* + **2 测试邻接表有向图关键路径**\n\n
* 初始化adj_list_directed_graph(邻接表有向图)\n
* 调用GetCriticalPath, 求"北京"到各城市的关键路径\n
* 打印各关键路径\n\n
* + **3 测试矩阵有向图关键路径**\n\n
* 初始化matrix_directed_graph(矩阵有向图)\n
* 调用GetCriticalPath, 求"北京"到各城市的关键路径\n
* 打印各关键路径\n
*
*
* --------------
*/
void TestCriticalPaths() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test Graph CriticalPaths |"<<endl;
cout<<"| 测试-图-关键路径 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 北京 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 0.1 0.12 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 上海---0.01---广州 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 0.13 0.14 0.05 0.17 |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| / \\ / \\ |"<<endl;
cout<<"| 杭州--0.09-- 深圳 --0.11--成都 |"<<endl;
cout<<endl;
// ---------- 1 初始化图的基本信息 ----------
// 初始化结点信息(北京, 上海, 广州, 深圳, 杭州, 成都 6座城市)
vector<string> vertices{ "北京", "上海", "广州", "深圳", "杭州", "成都" };
// 初始化边信息
unsigned int edge_count = 9;
vector<string> starting_vertices{ "北京", "北京", "上海", "上海", "上海", "广州", "广州", "深圳", "深圳" };
vector<string> ending_vertices { "上海", "广州", "广州", "深圳", "杭州", "深圳", "成都", "杭州", "成都" };
vector<double> weights { 0.1, 0.12, 0.01, 0.14, 0.13, 0.05, 0.17, 0.09, 0.11 };
vector<Edge<string, double> > edges;
for (unsigned int i = 0; i < edge_count; i++) {
Edge<string, double> edge(starting_vertices[i], ending_vertices[i], weights[i]);
edges.push_back(edge);
}
string starting_vertex = vertices[0];
// ---------- 2 测试邻接表有向图关键路径 ----------
cout << "---------- 邻接表图 ----------" << endl;
// 初始化adj_list_directed_graph(邻接表有向图)
AdjacencyListGraph<string, double> adj_list_directed_graph(Graph<string, double>::DIRECTED, 10, 1000, edges, vertices);
// 调用GetCriticalPath, 求"北京"到各城市的关键路径
vector<double> critical_paths = GetCriticalPath(adj_list_directed_graph, starting_vertex);
// 打印各关键路径
for (unsigned int i = 0; i < critical_paths.size(); i++) {
cout<<"北京 ---> "<<vertices[i]<<" 关键路径长度: "<<critical_paths[i]<<endl;
}
// ---------- 3 测试矩阵有向图关键路径 ----------
cout << endl << endl << "---------- 矩阵图 ----------" << endl;
// 初始化matrix_directed_graph(矩阵有向图)
MatrixGraph<string, double> matrix_directed_graph(Graph<string, double>::DIRECTED, 10, 1000, edges, vertices);
// 调用GetCriticalPath, 求"北京"到各城市的关键路径
critical_paths = GetCriticalPath(matrix_directed_graph, starting_vertex);
// 打印各关键路径
for (unsigned int i = 0; i < critical_paths.size(); i++) {
cout<<"北京 ---> "<<vertices[i]<<" 关键路径长度: "<<critical_paths[i]<<endl;
}
cout << "-------------------------------------------------------------" << endl << endl;
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手