#pragma once

#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include "graph_algorithm.h"
#include "min_priority_queue.hpp"
#include "disjoint_set.h"

/// <summary>
/// 深度优先遍历
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="vertex">遍历起点</param>
template<typename TVertex, typename TWeight>
inline void Dfs(const graph::Graph<TVertex, TWeight>& graph, const TVertex& vertex)
{
	// 声明已访问结点集合
	set<TVertex> visited_vertex_set;

	DfsOnVertexRecursive(graph,vertex,visited_vertex_set);
}

/// <summary>
/// 深度优先遍历（递归）
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="vertex">遍历起点</param>
/// <param name="visited_vertex_set">已近遍历过的集合</param>
template<typename TVertex, typename TWeight>
void DfsOnVertexRecursive(const graph::Graph<TVertex, TWeight>& graph, const TVertex& vertex, set<TVertex>& visited_vertex_set)
{
	cout << "访问结点：" << vertex << endl;

	// 起点插入已遍历结点集合
	visited_vertex_set.insert(vertex);

	// 遍历起点的邻接点，执行递归
	TVertex neighbor_vertex;
	bool new_neighbor_exists = graph.getFirstNeighborVertex(vertex,neighbor_vertex);

	// 遍历执行递归
	while (new_neighbor_exists)
	{
		// neighbor_vertex未被访问到（不在visited_vertex_set集合中）
		if (visited_vertex_set.find(neighbor_vertex) == visited_vertex_set.end())
			DfsOnVertexRecursive(graph,neighbor_vertex,visited_vertex_set);
	
		TVertex next_neighbor_vertex;
		// 依托之前实现的图结构存储点的相邻点有顺序性，保证每次不会找到之前就已经找到的点
		new_neighbor_exists = graph.getNextNeighborVertex(vertex,neighbor_vertex,next_neighbor_vertex);
		
		// 如果存在新的相邻结点
		if (new_neighbor_exists)
			neighbor_vertex = next_neighbor_vertex;
	}

}

/// <summary>
/// 图广度优先遍历
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="vertex">目标结点</param>
template<typename TVertex, typename TWeight>
void Bfs(const graph::Graph<TVertex, TWeight>& graph, const TVertex& vertex)
{
	cout << "访问结点：" << vertex << endl;

	// 初始化visited_vertex_set（已遍历结点集合）
	set<TVertex> visited_vertex_set;
	visited_vertex_set.insert(vertex);

	// 初始化visited_queue（结点队列）
	queue<TVertex> vertex_queue;
	vertex_queue.push(vertex);

	// 使用队列进行遍历节点
	while (!vertex_queue.empty())
	{
		TVertex front_vertex = vertex_queue.front();
		vertex_queue.pop();

		TVertex neighbor_vertex;
		bool new_neighbor_exists = graph.getFirstNeighborVertex(front_vertex,neighbor_vertex);
		// 该节点存在相邻结点
		while (new_neighbor_exists)
		{
			// 已遍历集合中没有该结点
			if (visited_vertex_set.find(neighbor_vertex) == visited_vertex_set.end())
			{
				cout << "访问结点：" << neighbor_vertex << endl;
				visited_vertex_set.insert(neighbor_vertex);
				vertex_queue.push(neighbor_vertex);
			}

			TVertex next_neighbor_vertex;
			new_neighbor_exists = graph.getNextNeighborVertex(front_vertex,neighbor_vertex,next_neighbor_vertex);
		
			if (new_neighbor_exists)
				neighbor_vertex = next_neighbor_vertex;
		}
	}
}

/// <summary>
/// 拓扑排序
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="starting_vertex">拓扑排序开始结点</param>
/// <param name="topology_sorted_list">拓扑排序序列</param>
/// <returns>函数执行结果</returns>
template<typename TVertex, typename TWeight>
bool topologicalSort(const graph::Graph<TVertex, TWeight>& graph, const TVertex& starting_vertex, vector<TVertex>& topology_sorted_list)
{
	// 已经被访问的点集合
	set<TVertex> visited_vertex_set;

	// 如果是有向图
	if (graph.type() == graph::Graph<TVertex, TWeight>::DIRECTED)
	{	
		int in_degree = graph.getVertexInDegree(starting_vertex);
		// 起点入度不为0
		if (in_degree > 0)
			return false;
	}

	topologicalSortRecursive_(graph,starting_vertex,visited_vertex_set,topology_sorted_list);

	return true;
}

// 递归的拓扑排序
template<typename TVertex, typename TWeight>
void topologicalSortRecursive_(const graph::Graph<TVertex, TWeight>& graph, TVertex starting_vertex, set<TVertex>& visited_vertex_set, vector<TVertex>& topology_sorted_list)
{
	// 起点插入到已遍历的结点集合
	visited_vertex_set.insert(starting_vertex);
	// 拓扑排序序列
	topology_sorted_list.push_back(starting_vertex);

	// 遍历起点的邻接点，执行递归
	TVertex neighbor_vertex;
	bool new_neighbor_exists = graph.getFirstNeighborVertex(starting_vertex,neighbor_vertex);

	// 遍历执行递归
	while (new_neighbor_exists)
	{
		if (visited_vertex_set.find(neighbor_vertex) == visited_vertex_set.end())	// 该点没被访问过
		{
			topologicalSortRecursive_(graph,neighbor_vertex,visited_vertex_set,topology_sorted_list);
		}

		TVertex next_neighbor_vertex;
		new_neighbor_exists = graph.getNextNeighborVertex(starting_vertex,neighbor_vertex,next_neighbor_vertex);

		if (new_neighbor_exists)
			neighbor_vertex = next_neighbor_vertex;
	}
}


/// <summary>
/// 求图的连通分量（在一个非连通的图中，每个连通的子图称为一个连通分量）
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <returns>图中连通图的个数</returns>
template<typename TVertex, typename TWeight>
int components(const graph::Graph<TVertex, TWeight>& graph)
{
	// 边界条件处理
	if (graph.vertexCount() == 0)
		return 0;

	// 声明visited_vertex_set（已访问结点集合）
	set<TVertex> visited_vertex_set;
	// 若该图不为空，则一定存在一个连通图
	int count = 1;

	for (int i = 0; i < graph.vertexCount(); i++)
	{
		TVertex vertex;
		bool res = graph.getVertexByIndex(i,vertex);
		if (!res)
			continue;

		// 该点已经被访问过
		if (visited_vertex_set.find(vertex) != visited_vertex_set.end())
			continue;

		cout << "连通分量" << count << "：" << endl;

		DfsOnVertexRecursive(graph,vertex,visited_vertex_set);

		count++;
		cout << endl;
	}

	// 退出函数
	return count;
}

/// <summary>
/// prim算法求最小生成树（根据已有点集，选点，连成边）
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="min_span_tree">得到的最小生成树</param>
/// <returns>是否正常退出</returns>
template<typename TVertex, typename TWeight>
bool prim(const graph::Graph<TVertex, TWeight>& graph, MinimunSpanTree<TVertex, TWeight>& min_span_tree)
{
	// 设置起点
	TVertex starting_vertex;
	// “0号点”为起点
	bool res = graph.getVertexByIndex(0, starting_vertex);
	if (!res)
		return false;

	// 初始化最小生成树结点集合和边的最小优先队列
	set<TVertex> mst_vertex_set;
	mst_vertex_set.insert(starting_vertex);

	MinPriorityQueue<graph::Edge<TVertex, TWeight>> min_priority_queue;

	// 贪心
	// 当存在点还没被访问时，持续进入循环
	while (mst_vertex_set.size() < graph.vertexCount())
	{
		if (min_priority_queue.size() != 0)
		{
			graph::Edge<TVertex, TWeight> cur_min_edge;
			// 取出权值最小的边
			min_priority_queue.deQueue(cur_min_edge);

			min_span_tree.insert(cur_min_edge);
			mst_vertex_set.insert(cur_min_edge.ending_vertex);
		}

		// 此循环的目的是把与目前最小生成树的点集有边相连的点纳入考虑范围，就是把对应的边加入到小根堆
		for (typename set<TVertex>::iterator iter = mst_vertex_set.begin(); iter != mst_vertex_set.end(); iter++)
		{
			TVertex cur_mst_vertex = *iter;

			TVertex cur_neighbot_vertex;
			bool new_neighbor_exists = graph.getFirstNeighborVertex(cur_mst_vertex, cur_neighbot_vertex);

			// iter指向的点存在相邻结点
			while (new_neighbor_exists)
			{
				// 相邻的结点没在最小生成树点集，iter指向的点与其相邻点连接的边入最小优先队列
				if (mst_vertex_set.find(cur_neighbot_vertex) == mst_vertex_set.end())
				{
					TWeight cur_weight;
					graph.getWeight(cur_mst_vertex, cur_neighbot_vertex, cur_weight);

					graph::Edge<TVertex, TWeight> cur_edge(cur_mst_vertex, cur_neighbot_vertex, cur_weight);

					min_priority_queue.enQueue(cur_edge);
				}

				TVertex next_neighbor_vertex;
				new_neighbor_exists = graph.getNextNeighborVertex(cur_mst_vertex, cur_neighbot_vertex, next_neighbor_vertex);

				if (new_neighbor_exists)
					cur_neighbot_vertex = next_neighbor_vertex;
			}
		}

		return true;
	}
}

/// <summary>
/// kruskal算法求最小生成树（直接选边，注意不能出现环，使用到了数据结构：并查集）
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="min_span_tree">得到的最小生成树</param>
template<typename TVertex, typename TWeight>
void kruskal(const graph::Graph<TVertex, TWeight>& graph, MinimunSpanTree<TVertex, TWeight>& min_span_tree)
{
	// 初始化min_priority_queue（最小优先队列）和disjoint_set（并查集）
	MinPriorityQueue<graph::Edge<TVertex, TWeight>> min_priority_queue;
	DisjointSet disjoint_set(graph.vertexCount());

	// 将所有边入队到最小优先队列
	for (int i = 0; i < graph.edgeCount(); i++)
	{
		TVertex cur_starting_vertex = graph.getEdge(i).starting_vertex;
		TVertex cur_ending_vertex = graph.getEdge(i).ending_vertex;
		TWeight weight;
		bool res = graph.getWeight(cur_starting_vertex,cur_ending_vertex,weight);
		// 找到对应边
		if (res)
		{
			graph::Edge<TVertex, TWeight> mst_edge(cur_starting_vertex,cur_ending_vertex,weight);
			min_priority_queue.enQueue(mst_edge);
		}
	}

	// 贪心，每次选择合适的“最短”边
	// n个点，最小生成树有n-1条边
	for (int i = 0; i < graph.vertexCount() - 1; )
	{
		graph::Edge<TVertex, TWeight> cur_edge;
		// 取出权值最小的边
		min_priority_queue.deQueue(cur_edge);

		int cur_starting_vertex_index = graph.getVertexIndex(cur_edge.starting_vertex);
		int cur_ending_vertex_index = graph.getVertexIndex(cur_edge.ending_vertex);
	
		// 当前边的起点所在并查集的根结点索引
		int cur_starting_vertex_root_index = disjoint_set.findRecursive(cur_starting_vertex_index);
		// 当前边的终点所在并查集的根结点索引
		int cur_ending_vertex_root_index = disjoint_set.findRecursive(cur_ending_vertex_index);
		
		// 这条“最小边”的两点不在同一个并查集
		if (cur_starting_vertex_index != cur_ending_vertex_index)
		{
			disjoint_set._union(cur_starting_vertex_index,cur_ending_vertex_index);
			// “最小边”加入最小生成树
			min_span_tree.insert(cur_edge);
			i++; // 找到一条边
		}
	}
}

/// <summary>
/// 迪杰斯特拉算法求最短路径（求单源最短路径：从某一个确定点到其他点的最短路径）（优先队列）（局限性：要求图中边的权值不能出现负数）(可以推出完整的最短路径上的各点)
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="starting_vertex">开始结点</param>
/// <param name="distance">起点到其他点的距离，distance[index]代表起点到index结点的距离</param>
/// <param name="predecessor">最短路径终点的前驱节点，predecessor[index]代表index结点的最短路径的前驱结点</param>
template<typename TVertex, typename TWeight>
void dijkstra(const graph::Graph<TVertex, TWeight>& graph, const TVertex& starting_vertex, TWeight distance[], int predecessor[])
{
	// 初始化
	
	set<TVertex> confirmed_vertex_set;

	// distance数组（起点到各点的最短路径长度）初始化
	int starting_vertex_index = graph.getVertexIndex(starting_vertex);
	for (int i = 0; i < graph.vertexCount(); i++)
	{
		// 初始化起点到其他点的距离为"＋∞"
		distance[i] = graph.maxWeight();
	}

	// 初始化起点到起点的距离为0
	distance[starting_vertex_index] = 0;

	// 最短路径的最小优先队列初始化
	MinPriorityQueue<graph::Path<TVertex, TWeight>> min_priority_queue;
	// 起点到起点的边及权值
	graph::Path<TVertex, TWeight> cur_path(starting_vertex,starting_vertex,0);
	min_priority_queue.enQueue(cur_path);
	
	// predecessor数组（最短路径终点的前驱节点索引）初始化
	predecessor[starting_vertex_index] = -1; // starting_vertex没有前驱结点

	// 贪心策略（算法关键部分）
	while (min_priority_queue.size() != 0)
	{
		// 每次取出最短路径
		graph::Path<TVertex, TWeight> cur_min_path;
		min_priority_queue.deQueue(cur_min_path);

		int cur_min_path_ending_vertex_index = graph.getVertexIndex(cur_min_path.ending_vertex);
		// 将点加入已经确定最短路径的点集合
		confirmed_vertex_set.insert(cur_min_path.ending_vertex);

		for (int i = 0; i < graph.vertexCount(); i++)
		{
			TVertex cur_vertex;
			graph.getVertexByIndex(i,cur_vertex);

			// 该点已经确定最短路径
			if (confirmed_vertex_set.find(cur_vertex) != confirmed_vertex_set.end())
				continue;

			TWeight weight;
			// 每次for循环找与当前最短路径终点有边相连的其他点，并试图更新最短路径--->松弛操作
			bool get_weight_done = graph.getWeight(cur_min_path.ending_vertex,cur_vertex,weight);
			if (!get_weight_done)
				continue;

			// 松弛操作（放松操作：对于一条从 顶点u指向 顶点v的边 u-->v来说，如果满足  d[u]+w(u,v)<d[v],就更新 d[v],使得 d[v]=d[u]+w(u,v)；这就是对 "边uv"的一次放松操作；）
			if ( distance[cur_min_path_ending_vertex_index] + weight < distance[i])
			{
				// 更新距离
				distance[i] = distance[cur_min_path_ending_vertex_index] + weight;
				predecessor[i] = cur_min_path_ending_vertex_index;

				// 更新最短路径
				graph::Path<TVertex, TWeight> new_min_distance_path(starting_vertex,cur_vertex,distance[i]);
				min_priority_queue.enQueue(new_min_distance_path);
			}
		}
	}
}

/// <summary>
/// bellmanFord算法求最短路径（求单源最短路径：从某一个确定点到其他点的最短路径）（优先队列）（解决了dijkstra的局限性：图中边的权值可以出现负数）（解决的方法是：如果最后一次遍历仍然有更新操作，则存在负环，没有最短路径，算法结束return false）(可以推出完整的最短路径上的各点)
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="starting_vertex">开始结点</param>
/// <param name="distance">起点到其他点的距离，distance[index]代表起点到index结点的距离</param>
/// <param name="predecessor">最短路径终点的前驱节点，predecessor[index]代表index结点的最短路径的前驱结点</param>
/// <returns>函数是否正常退出：true代表正常退出；false代表图中存在"负环"，不存在各点到源点的最短路径</returns>
template<typename TVertex, typename TWeight>
bool bellmanFord(const graph::Graph<TVertex, TWeight>& graph, const TVertex& starting_vertex, TWeight distance[], int predecessor[])
{
	// 1初始化
	int starting_vertex_index = graph.getVertexIndex(starting_vertex);
	for (int i = 0; i < graph.vertexCount(); i++)
	{
		// 初始化距离数组为"＋∞"
		distance[i] = graph.maxWeight();
	}
	// 源点（开始结点）到源点的距离为0
	distance[starting_vertex_index] = starting_vertex_index;
	// 源点没有最短路径的前驱结点
	predecessor[starting_vertex_index] = -1;

	// 2动态规划（算法关键部分）
	for (int vertex_index = 0; vertex_index < graph.vertexCount() - 1; vertex_index++)
	{// n-1次顺序遍历每条边
		for (int edge_index = 0; edge_index < graph.edgeCount(); edge_index++)
		{// 每轮边遍历的目的是更新各个点的最短路径
			TVertex cur_starting_vertex = graph.getEdge(edge_index).starting_vertex;
			TVertex cur_ending_vertex = graph.getEdge(edge_index).ending_vertex;

			int cur_starting_vertex_index = graph.getVertexIndex(cur_starting_vertex);
			int cur_ending_vertex_index = graph.getVertexIndex(cur_ending_vertex);

			TWeight cur_edge_weight;
			bool res = graph.getWeight(cur_starting_vertex,cur_ending_vertex,cur_edge_weight);
			if (!res)
				continue;

			// 松弛操作
			if (distance[cur_starting_vertex_index] + cur_edge_weight < distance[cur_ending_vertex_index])
			{
				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;
	//		再次遍历每条边，试图更新各点的最短路径，若此次确有点到源点的最短路径被更新，则表明存在"负环"；否则，函数正常退出,表明找到各点到源点的最短路径
	for (int i = 0; i < graph.edgeCount(); i++)
	{
		TVertex cur_starting_vertex = graph.getEdge(edge_index).starting_vertex;
		TVertex cur_ending_vertex = graph.getEdge(edge_index).ending_vertex;

		int cur_starting_vertex_index = graph.getVertexIndex(cur_starting_vertex);
		int cur_ending_vertex_index = graph.getVertexIndex(cur_ending_vertex);

		TWeight cur_edge_weight;
		bool get_weight_done = graph.getWeight(cur_starting_vertex, cur_ending_vertex, cur_edge_weight);
		if (!get_weight_done)
			continue;

		// 此次仍然更新了最短路径
		if (distance[cur_starting_vertex_index] + cur_edge_weight < distance[cur_ending_vertex_index])
		{
			negative_weight_cycle_exists = true;
			break;
		}

	}

	// 4退出函数
	return !negative_weight_cycle_exists;
}

/// <summary>
/// 弗洛伊德算法求最短路径，求多源(任意两个点)的最短路径（此处没有加入pass数组，无法推出完整的最短路径上的各点）
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="distance">起点到其他点的距离，distance[index]代表起点到index结点的距离</param>
/// <param name="predecessor">最短路径终点的前驱节点，predecessor[index]代表index结点的最短路径的前驱结点</param>
template<typename TVertex, typename TWeight>
void floyd(const graph::Graph<TVertex, TWeight>& graph, vector<vector<TWeight>>& distance, vector<vector<int>>& predecessor)
{
	// 1初始化
	// 第一轮（以“-1”点作为中间点）使用图的信息填充distance和predecessor数组
	// distance和predecessor是二维数组
	for (int start_vertex_index = 0; start_vertex_index < graph.vertexCount(); start_vertex_index++)
	{
		for (int end_vertex_index = 0; end_vertex_index < graph.vertexCount(); end_vertex_index++)
		{
			if (start_vertex_index == end_vertex_index)
			{
				// 自己到自己最短路径长度为0，前驱结点为该点本身
				distance[start_vertex_index][end_vertex_index] = TWeight();
				predecessor[start_vertex_index][end_vertex_index] = (int)start;
			}
			else
			{
				TWeight weight;
				bool res = graph.getWeightByVertexIndex(start_vertex_index, end_vertex_index, weight);
				if (res)	// start_vertex到end_vertex有边相连
				{
					distance[start_vertex_index][end_vertex_index] = weight;
					predecessor[start_vertex_index][end_vertex_index] = (int)start;
				}
				else	// start_vertex到end_vertex没有边相连，距离为“+∞”，前驱结点为-1
				{
					distance[start_vertex_index][end_vertex_index] = graph.maxWeight();
					predecessor[start_vertex_index][end_vertex_index] = -1;
				}
			}
		}
	}

	// 2动态规划
	//		n个点，依次以其中某一个点为中间点求最短路径，需要重复执行n次
	for (int intermediate = 0; intermediate < graph.vertexCount(); intermediate++)
	{
		for (int start_vertex_index = 0; start_vertex_index < graph.vertexCount(); start_vertex_index++)
		{
			for (int end_vertex_index = 0; end_vertex_index < graph.vertexCount(); end_vertex_index++)
			{
				// 松弛操作
				if (distance[start_vertex_index][intermediate] + distance[intermediate][end_vertex_index] < distance[start_vertex_index][end_vertex_index])
				{
					distance[start_vertex_index][end_vertex_index] = distance[start_vertex_index][intermediate] + distance[intermediate][end_vertex_index];
					predecessor[start_vertex_index][end_vertex_index] = predecessor[intermediate][end_vertex_index];
				}
			}
		}
	}
}

/// <summary>
/// 打印单源最短路径（Dijkstra、Bellmanford算法等）
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="starting_vertex">开始结点</param>
/// <param name="distance">起点到其他点的距离，distance[index]代表起点到index结点的距离</param>
/// <param name="predecessor">最短路径终点的前驱节点，predecessor[index]代表index结点的最短路径的前驱结点</param>
template<typename TVertex, typename TWeight>
void printSingleSourceShortestPath(const graph::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()];

	for (int ending_vertex_index = 0; ending_vertex_index < graph.vertexCount(); ending_vertex_index++)
	{
		// 源点和终点是一个点
		if (ending_vertex_index == starting_vertex_index)
			continue;

		int cur_predecessor_index = (int)ending_vertex_index;
		int i = 0;

		// 根据由求单源最短路径算法得到的predecessor数组从终点往回找路径
		while (cur_predecessor_index != starting_vertex_index)
		{
			inverted_predecessors[i] = cur_predecessor_index;
			cur_predecessor_index = predecessor[cur_predecessor_index];
			i++;
		}

		// ▲打印最短路径
		TVertex ending_vertex;
		graph.getVertexByIndex(ending_vertex_index,ending_vertex);

		cout << "起始点（" << starting_vertex << "）到结点（" << ending_vertex << "）的最短路径为：";
		cout << starting_vertex << " ";

		// 使用invert_predecessors数组打印出路径，对invert_predecessors数组从后向前，依次打印
		while (i > 0)
		{
			i--;
			TVertex cur_vertex;
			graph.getVertexByIndex(inverted_predecessors[i],cur_vertex);
			cout << cur_vertex << " ";
		}

		cout << "，";
		cout << "最短路径长度为：" << distance[ending_vertex_index] << endl;
	}

	// 释放堆区内存
	delete[] inverted_predecessors;
}

/// <summary>
/// 打印多源最短路径（弗洛伊德算法等）
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="distance">起点到其他点的距离，distance[index]代表起点到index结点的距离</param>
/// <param name="predecessor">最短路径终点的前驱节点，predecessor[index]代表index结点的最短路径的前驱结点</param>
template<typename TVertex, typename TWeight>
void printMultipleSourceShortestPath(const graph::Graph<TVertex, TWeight>& graph, const vector<vector<TWeight>>& distance, const vector<vector<int>>& predecessor)
{
	for (int i = 0; i < graph.vertexCount(); i++)
	{
		TVertex cur_starting_vertex;
		graph.getVertexByIndex(i,cur_starting_vertex);

		cout << "--- 从起始点（" << cur_starting_vertex << "）到其他各顶点的最短路径 ---" << endl;

		for (int j = 0; j < graph.vertexCount(); j++)
		{
			if (i == j)
				continue;

			TVertex ending_vertex;
			graph.getVertexByIndex(j,ending_vertex);

			cout << "起始点（" << cur_starting_vertex << "）到结点（" << ending_vertex << "）的最短路径为：";

			bool res = printSingleSourceShortestPathInMultipleSourceShortestPath(graph,predecessor,i,j);
			
			if (res)
				cout << "，最短路径长度为：" << distance[i][j] << endl;
		}
		cout << endl;
	}
}

/// <summary>
/// 打印单源最短路径(在多源最短路径中)(递归)
/// </summary>
/// <typeparam name="TVertex">结点类型模板参数</typeparam>
/// <typeparam name="TWeight">边权值类型模板参数</typeparam>
/// <param name="graph">给定图</param>
/// <param name="predecessor">最短路径前驱结点二维容器，predecessor[i][j]代表i结点到j结点最短路径中j结点前面的那一个结点</param>
/// <param name="starting_vertex_index">开始结点索引</param>
/// <param name="ending_vertex_index">结束结点索引</param>
/// <returns>是否找到了最短路径</returns>
template<typename TVertex, typename TWeight>
bool printSingleSourceShortestPathInMultipleSourceShortestPath(const graph::Graph<TVertex, TWeight>& graph, vector<vector<int>> predecessor, int starting_vertex_index, int ending_vertex_index)
{
	// 找出图中索引对应的结点
	TVertex starting_vertex;
	graph.getVertexByIndex(starting_vertex_index,starting_vertex);

	TVertex ending_vertex;
	graph.getVertexByIndex(ending_vertex_index,ending_vertex);

	// 合法性校验
	if (predecessor[starting_vertex_index][ending_vertex_index] == -1)
	{
		cout << starting_vertex << "到" << ending_vertex << "没有路径" << endl;
		return false;
	}

	// 递归执行
	if (starting_vertex_index != ending_vertex_index)
	{
		bool res = printSingleSourceShortestPathInMultipleSourceShortestPath(graph,predecessor,starting_vertex_index,predecessor[starting_vertex_index][ending_vertex_index]);
	
		if (!res)
			return false;
	}

	// 打印结点
	cout << ending_vertex << " ";

	// 退出函数
	return true;
}

/// <summary>
/// 求起点到个结点的关键路径（关键路径：项目中时间最长的活动顺序，决定着可能的项目最短工期。关键路径上的活动（edge）时间余量为0，是不能拖延的活动）。
/// 🔺先求点（ve、vl）：根据点（事件）的拓扑排序序列求点（事件）最早发生时间（ve，大）；根据点（事件）的逆拓扑排序序列求点（事件）最晚发生时间（vl，小）。
/// 🔺再求边（e、l）：边（活动）最早发生时间（e） = 边的起点（事件）最早发生时间（ve）；边（活动）最晚发生时间（l） = 边的终点（事件）最晚发生时间（vl） - 边（活动）的权值。
/// 🔺最后求时间余量：边最晚（l） - 边最早（e），若为0，则该边（活动）就是关键路径上的一边（关键活动上的一个活动），注意，关键路径可能不唯一。
/// </summary>
/// <typeparam name="TVertex">点的值</typeparam>
/// <typeparam name="TWeight">边的权值</typeparam>
/// <param name="graph">给定图</param>
/// <param name="starting_vertex">开始结点</param>
/// <returns>关键路径</returns>
template<typename TVertex, typename TWeight>
vector<TWeight> getCriticalPath(const graph::Graph<TVertex, TWeight>& graph, const TVertex& starting_vertex)
{
	// 初始化
	vector<TWeight> critical_paths;
	set<int> visited_vertex_index_set;
	queue<int> vertex_index_queue;

	int starting_vertex_index = graph.getVertexIndex(starting_vertex);
	visited_vertex_index_set.insert(starting_vertex_index);
	vertex_index_queue.push(starting_vertex_index);

	for (int i = 0; i < graph.vertexCount(); i++)
	{
		critical_paths.push_back(TWeight());
	}

	// BFS
	while (!vertex_index_queue.empty())
	{
		int cur_start_index = vertex_index_queue.front();
		vertex_index_queue.pop();

		for (int cur_end_index = 0; cur_end_index < int(graph.vertexCount()); cur_end_index++)
		{
			TWeight cur_weight;
			bool res = graph.getWeightByVertexIndex(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())
					vertex_index_queue.push(cur_end_index);

				visited_vertex_index_set.insert(cur_end_index);
			}
		}
	}
	// 退出函数
	return critical_paths;
}