同步操作将从 cyberdash/数据结构(C++模板实现) 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
/*!* @file graph.h* @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)* @brief 图抽象模板类与边模板类* @version 0.2.1* @date 2021年01月23日*/#ifndef CYBER_DASH_GRAPH_H#define CYBER_DASH_GRAPH_H#include <vector>using namespace std;/*!* @brief **边模板类*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数* @note* 边模板类* -------* -------** <span style="color:#DF5A00">* 注:\n* 此模板类只表示存在边, 并不表达边的方向\n* 边的方向在邻接表图中, 由邻接表表示, 在邻接矩阵图中, 由邻接矩阵表示\n* </span>** -------**/template<typename TVertex, typename TWeight>class Edge {public:/*!* @brief **默认构造函数*** @note* 默认构造函数* ----------* ----------** ----------*/Edge(): starting_vertex(TVertex()), ending_vertex(TVertex()), weight(TWeight()) {}/*!* @brief **构造函数(边权值/起点/终点)*** @param weight 边权值* @param starting_vertex 起点* @param ending_vertex 终点* @note* 构造函数(边权值/起点/终点)* -----------------------* -----------------------** -----------------------*/Edge(const TVertex& starting_vertex, const TVertex& ending_vertex, const TWeight& weight):weight(weight), starting_vertex(starting_vertex), ending_vertex(ending_vertex) {}/*!* @brief **重载<=*** @param edge 边* @return 执行结果* @note* 重载<=* -----* -----** -----*/bool operator<=(const Edge<TVertex, TWeight>& edge) { return weight <= edge.weight; }/*!* @brief **重载>=*** @param edge 边* @return 执行结果* @note* 重载>=* -----* -----** -----*/bool operator>=(const Edge<TVertex, TWeight>& edge) { return weight >= edge.weight; }/*!* @brief **重载>*** @param edge 边* @return 执行结果* @note* 重载>* ----* ----** ----*/bool operator>(const Edge<TVertex, TWeight>& edge) { return weight > edge.weight; }/*!* @brief **重载<*** @param edge 最小生成树边* @return 执行结果* @note* 重载<* ----* ----** <span style="color:#DF5A00">* doxygen处理less-than符号(<)不是很友好, 所以注释中使用"\<"来表达<* </span>** ----*/bool operator<(const Edge<TVertex, TWeight>& edge) { return weight < edge.weight; }TVertex starting_vertex; //!< **起点**TVertex ending_vertex; //!< **终点**TWeight weight; //!< **边权重**};/*!* @brief **路径模板类*** @tparam TVertex 结点类型模板参数* @tparam TWeight 边权值类型模板参数*/template<typename TVertex, typename TWeight>class Path: public Edge<TVertex, TWeight> {public:/*!* @brief **默认构造函数***/Path(): starting_vertex(TVertex()), ending_vertex(TVertex()), weight(TWeight()) {};/*!* @brief **构造函数*** @param starting_vertex 起点* @param ending_vertex 终点* @param weight 边权值*/Path(TVertex starting_vertex, TVertex ending_vertex, TWeight weight):starting_vertex(starting_vertex), ending_vertex(ending_vertex), weight(weight) {}TWeight weight; //!< **路径权值**TVertex starting_vertex; //!< **起点**TVertex ending_vertex; //!< **终点**};/*!* @brief **图抽象模板类*** @tparam TVertex 节点类型模板参数* @tparam TWeight 边权值类型模板参数* @note* 图抽象模板类* ----------* ----------** ----------*/template<typename TVertex, typename TWeight>class Graph {public:/*!* @brief **获取图类型*** @return 图类型* @note* 1: 有向, 2: 无向*/int Type() const { return this->type_; }/*!* @brief **获取结点数量*** @return 结点数量* @note* 获取结点数量* ----------* ----------** ----------*/unsigned int VertexCount() const { return this->vertex_count_; }/*!* @brief **获取边数量*** @return 边数量* @note* 获取边数量* ---------* ---------** ---------*/unsigned int EdgeCount() const { return this->edge_count_; }/*!* @brief **获取边权值上限*** @return 边权值上限*/virtual TWeight MaxWeight() const { return this->max_weight_; }/*!* @brief **获取边vector*** @return 边vector*/virtual const vector<Edge<TVertex, TWeight> >& Edges() const { return this->edges_; }/*!* @brief **获取结点vector*** @return 结点vector*/virtual const vector<TVertex>& Vertices() const { return this->vertices_; }/*!* @brief **获取边(by边索引)*** @param index 边索引* @return 边* @note* 获取边(by边索引)* --------------* --------------** todo: 应该改为返回bool类型** --------------*/virtual const Edge<TVertex, TWeight>& GetEdge(int index) const { return this->edges_[index]; }/*!* @brief **获取结点(by结点索引)(纯虚函数)*** @param vertex 结点保存变量* @param vertex_index 结点索引* @return 执行结果* @note* 获取结点(by结点索引)(纯虚函数)* ---------------* ---------------** ---------------*/virtual bool GetVertexByIndex(int vertex_index, TVertex& vertex) const = 0;/*!* @brief **获取边权值(by结点)(纯虚函数)*** @param weight 边权值保存变量* @param starting_vertex 起点* @param ending_vertex 终点* @return 执行结果* @note* 获取边权值(by结点)(纯虚函数)* -----------------* -----------------** -----------------*/virtual bool GetWeight(const TVertex& starting_vertex, const TVertex& ending_vertex, TWeight& weight) const = 0;/*!* @brief **获取边权值(by结点索引)*** @param weight 边权值保存变量* @param starting_vertex_index 起点索引* @param ending_vertex_index 终点索引* @return 执行结果* @note* 获取边权值(by结点索引)* ---------------------* ---------------------** ---------------------*/virtual bool GetWeightByVertexIndex(int starting_vertex_index, int ending_vertex_index, TWeight& weight) const = 0;/*!* @brief **获取结点的第一个相邻结点*** @param first_neighbor 第一个相邻结点保存变量* @param vertex 当前结点* @return 执行结果* @note* 获取结点的第一个相邻结点* --------------------* --------------------** --------------------*/virtual bool GetFirstNeighborVertex(const TVertex& vertex, TVertex& first_neighbor) const = 0;/*!* @brief **获取结点的下一个相邻结点*** @param next_neighbor 下一个相邻结点保存变量* @param vertex 当前结点* @param neighbor_vertex 相邻节点* @return 执行结果* @note* 获取结点的下一个相邻结点* --------------------* --------------------** --------------------*/virtual bool GetNextNeighborVertex(const TVertex& vertex,const TVertex& neighbor_vertex,TVertex& next_neighbor) const = 0;/**!* @brief **获取结点的度*** @param vertex 结点* @return 度* @note* 获取结点的度* ----------* ----------** ----------* **if** 有向图 :\n*   返回-1(有向图应获取出度入度)\n\n* 获取vertex_index(结点索引)\n\n* 返回this->degrees_[vertex_index]\n*** ----------*/int GetVertexDegree(TVertex vertex) {if (this->type_ == DIRECTED) { // if 有向图return -1; // 返回-1(有向图应获取出度入度)}int vertex_index = GetVertexIndex(vertex); // 获取vertex_index(结点索引)return this->degrees_[vertex_index]; // 返回this->degrees_[vertex_index]}/**!* @brief **获取结点的入度*** @param vertex 结点* @return 入度* @note* 获取结点的入度* ------------* ------------** ------------* **if** 无向图 :\n*   返回-1(无向图应获取度)\n\n* 获取vertex_index(结点索引)\n\n* 返回this->in_degrees_[vertex_index]\n*** ----------*/int GetVertexInDegree(const TVertex& vertex) const {if (this->type_ == UNDIRECTED) { // if 无向图return -1; // 返回-1(无向图应获取度)}int vertex_index = GetVertexIndex(vertex); // 获取vertex_index(结点索引)return this->in_degrees_[vertex_index]; // 返回this->in_degrees_[vertex_index]}/**!* @brief **获取结点的出度*** @param vertex 结点* @return 出度* @note* 获取结点的出度* ------------* ------------** ------------* **if** 无向图 :\n*   返回-1(无向图应获取度)\n\n* 获取vertex_index(结点索引)\n\n* 返回this->out_degrees_[vertex_index]\n*** ----------*/int GetVertexOutDegree(TVertex vertex) {if (this->type_ == UNDIRECTED) { // if 无向图return -1; // 返回-1(无向图应获取度)}int vertex_index = GetVertexIndex(vertex); // 获取vertex_index(结点索引)return this->out_degrees_[vertex_index]; // 返回this->out_degrees_[vertex_index]}/*!* @brief **插入结点*** @param vertex 结点* @return 执行结果* @note* 插入结点* -------* -------** -------*/virtual bool InsertVertex(const TVertex& vertex) = 0;/*!* @brief **插入边*** @param starting_vertex 起点* @param ending_vertex 终点* @param weight 边权值* @return 执行结果* @note* 插入边* -----* -----** -----*/virtual bool InsertEdge(const TVertex& starting_vertex, const TVertex& ending_vertex, const TWeight& weight) = 0;/*!* @brief **删除结点*** @param vertex 结点* @return 执行结果* @note* 删除结点* -------* -------** -------*/virtual bool RemoveVertex(const TVertex& vertex) = 0;/*!* @brief **删除边*** @param starting_vertex 起点* @param ending_vertex 终点* @return 执行结果* @note* 删除边* -----* -----** -----*/virtual bool RemoveEdge(const TVertex& starting_vertex, const TVertex& ending_vertex) = 0;/*!* @brief **获取结点索引*** @param vertex 结点* @return 结点索引* @note* 获取结点索引* --------------* --------------** --------------*/virtual int GetVertexIndex(const TVertex& vertex) const = 0;static const int DIRECTED = 1; //!< **有向**static const int UNDIRECTED = 2; //!< **无向**protected:int max_vertex_count_; //!< **图结点数量上限**TWeight max_weight_; //!< **边权值上限**int edge_count_; //!< **边数量**int vertex_count_; //!< **结点数量**int type_; //!< **类型(1:有向, 2:无向)**vector<TVertex> vertices_; //!< **结点vector**vector<Edge<TVertex, TWeight> > edges_; //!< **边vector**vector<int> degrees_; //!< **度vector(无向图使用)**vector<int> in_degrees_; //!< **入度vector(有向图使用)**vector<int> out_degrees_; //!< **出度vector(有向图使用)**};#endif //CYBER_DASH_GRAPH_H
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。