Fetch the repository succeeded.
This action will force synchronization from cyberdash/数据结构（C++模板实现）, which will overwrite any changes that you have made since you forked the repository, and can not be recovered!!!
Synchronous operation will process in the background and will refresh the page when finishing processing. Please be patient.
/*!
* @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 助手