1 Star 0 Fork 0

郑玉强/dataStructure

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
graph.hpp 4.96 KB
一键复制 编辑 原始数据 按行查看 历史
#pragma once
#include <vector>
using namespace std;
namespace graph
{
// 边模板类
template <class TVertex, class TWeight>
class Edge
{
public:
TVertex starting_vertex; // 起点
TVertex ending_vertex; // 终点
TWeight weight; // 边权重
Edge() :starting_vertex(TVertex()), ending_vertex(TVertex()), weight(TWeight()) {}
Edge(const TVertex& starting_vertex, const TVertex& ending_vertex, const TWeight& weight)
:weight(weight), starting_vertex(starting_vertex), ending_vertex(ending_vertex) {}
// 边的比较是边权值之间的比较
// 重载<=
bool operator<=(const Edge<TVertex, TWeight>& edge) { return this->weight <= edge.weight; }
// 重载>=
bool operator>=(const Edge<TVertex, TWeight>& edge) { return this->weight >= edge.weight; }
// 重载>
bool operator>(const Edge<TVertex, TWeight>& edge) { return this->weight > edge.weight; }
// 重载<
bool operator<(const Edge<TVertex, TWeight>& edge) { return this->weight < edge.weight; }
// 重载==
bool operator==(const Edge<TVertex, TWeight>& edge) { return (this->starting_vertex == edge.starting_vertex && this->ending_vertex == edge.ending_vertex); }
};
// 路径模板类
template <class TVertex, class TWeight>
class Path :public Edge<TVertex, TWeight>
{
TWeight weight; // 路径权值
TVertex starting_vertex; // 起点
TVertex ending_vertex; // 终点
Path() :starting_vertex(TVertex()), ending_vertex(TVertex()), weight(TWeight()) {}
Path(TVertex starting_vertex, TVertex ending_vertex, TWeight weight)
:starting_vertex(starting_vertex), ending_vertex(ending_vertex), weight(weight) {}
};
template <class TVertex, class TWeight>
class Graph
{
protected:
int max_vertex_count_; // 图节点数量上限
TWeight max_weight_; // 边权值上限
int edge_count_; // 边数量
int vertex_count_; // 结点数量
int type_; // 类型(1:有向,2:无向)
vector<TVertex> vertices_; // 结点vector
vector<int> degrees_; // 度vector(无向图使用)
vector<int> in_degrees_; // 入度vector(有向图使用)
vector<int> out_degrees_; // 出度vector(有向图使用)
vector<Edge<TVertex, TWeight>> edges_; // 边vector
public:
static const int DIRECTED = 1; // 有向
static const int UNDIRECTED = 2; // 无向
// 获取图类型
int type() const { return this->type_; }
// 获取结点数量
unsigned int vertexCount() const { return this->vertex_count_; }
// 获取边数量
unsigned int edgeCount() const { return this->edge_count_; }
// 获取边权值上限
// virtual关键字用于声明虚函数,这意味着这个函数可以在派生类中被重写(override)
virtual TWeight maxWeight() const { return this->max_weight_; }
// 获取点权值上限
virtual int maxVertexCount() const { return this->max_vertex_count_; }
// 获取边vector
virtual const vector<Edge<TVertex, TWeight>>& edges() const { return this->edges_; }
// 获取结点vector
virtual const vector<TVertex>& vertices() const { return this->vertices_; }
// 通过索引获取边,因为vector容器重载的“[]”
virtual const Edge<TVertex, TWeight>& getEdge(int index) const { return this->edges_[index]; }
// 通过索引获取结点,纯虚函数
virtual bool getVertexByIndex(int vertex_index, TVertex& vertex) const = 0;
// 通过结点获取边权值,纯虚函数
virtual bool getWeight(const TVertex& starting_vertex, const TVertex& ending_vertex, TWeight& weight) const = 0;
// 通过始末边的索引获取边权值,纯虚函数
virtual bool getWeightByVertexIndex(int starting_vertex_index, int ending_vertex_index, TWeight& weight) const = 0;
// 获取结点的第一个相邻结点,纯虚函数
virtual bool getFirstNeighborVertex(const TVertex& vertex, TVertex& first_neighbor) const = 0;
// 获取结点的下一个相邻结点,纯虚函数
virtual bool getNextNeighborVertex(const TVertex& vertex, const TVertex& neighbor_vertex,TVertex& next_neighbor) const = 0;
// 获取结点的度
int getVertexDegree(TVertex vertex)
{
// 有向图没有度的概念,度被分为出度和入度
if (this->type_ == DIRECTED)
return -1;
int vertex_index = this->getVertexIndex(vertex);
return this->degrees_[vertex_index];
}
// 获取结点的入度
int getVertexInDegree(const TVertex& vertex) const
{
// 无向图没有入度的概念
if (this->type_ == UNDIRECTED)
return -1;
int vertex_index = this->getVertexIndex(vertex);
return this->in_degrees_[vertex_index];
}
// 获取结点的出度
int getVertexOutDegree(const TVertex& vertex) const
{
// 无向图没有入度的概念
if (this->type_ == UNDIRECTED)
return -1;
int vertex_index = this->getVertexIndex(vertex);
return this->out_degrees_[vertex_index];
}
// 插入结点,纯虚函数
virtual bool insertVertex(const TVertex& vertex) = 0;
// 插入边,纯虚函数
virtual bool insertEdge(const TVertex& starting_vertex, const TVertex& ending_vertex, const TWeight& weight) = 0;
// 删除结点,纯虚函数
virtual bool removeVertex(const TVertex& vertex) = 0;
// 删除边,纯虚函数
virtual bool removeEdge(const TVertex& starting_vertex, const TVertex& ending_vertex) = 0;
// 获取结点索引,纯虚函数
virtual int getVertexIndex(const TVertex& vertex) const = 0;
};
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/zheng-yuqiang_lyg_cn/data-structure.git
git@gitee.com:zheng-yuqiang_lyg_cn/data-structure.git
zheng-yuqiang_lyg_cn
data-structure
dataStructure
dev01

搜索帮助