本文的主要内容为:图的C++代码实现 (邻接矩阵法),主要为各个类的声明
边类
1 // Author: SihanLin
2 // FileName: Edge.h
3
4 // 图的边类
5 class CEdge{
6 public:
7 int from; // 起点
8 int to; // 终点
9 int weight; // 权值
10
11 explicit CEdge(int from = -1, int to = -1, int weight = 0){ // 构造函数
12 this->from = from;
13 this->to = to;
14 this->weight = weight;
15 }
16
17 virtual ~CEdge(){ // 析构函数
18
19 }
20 };
图的抽象基类
1 // Author: SihanLin
2 // FileName: Graph.h
3
4 // 图的抽象基类
5 class CGraph{
6 protected:
7 static const int UNVISITED; // 顶点不可访问 0
8 static const int VISITED; // 顶点可访问 1
9 public:
10 int numVertex; // 顶点个数
11 int numEdge; // 边的个数
12 int* mark; // 用于标记顶点是否已经被访问
13 int* inDegree; // 用于记录顶点的入度
14
15 explicit CGraph(int numVertex = 1); // 构造函数
16 virtual ~CGraph(); // 析构函数
17
18 int GetVerticesNum();
19 int GetEdgesNum();
20 int GetFromVertex(CEdge oneEdge); // 获取边的起点
21 int GetToVertex(CEdge oneEdge); // 获取边的终点
22 int GetWeight(CEdge oneEdge); // 获取边的权值
23 bool IsEdge(CEdge oneEdge); // 判断是否是边
24 void ResetMark(); // 重新设置顶点是否被访问的记录
25
26 // 纯虚函数
27 virtual CEdge FirstEdge(int oneVertex) = 0; // 获取顶点的第一条边
28 virtual CEdge NextEdge(CEdge preEdge) = 0; // 获取上一条边的下一条边
29 virtual void SetEdge(int from, int to, int weight) = 0; // 设置边
30 virtual void delEdge(int from, int to) = 0; // 删除边
31 };
图的邻接矩阵实现类
1 // Author: SihanLin
2 // FileName: GraphAdjacentMatrix.h
3
4
5 #include "Graph.h"
6
7 // 图的邻接矩阵实现类
8 class CGraphM : public CGraph{
9 private:
10 int** matrix; // 指向二维邻接矩阵的指针
11 public:
12 explicit CGraphM(int numVertex = 1);
13 ~CGraphM();
14
15 CEdge FirstEdge(int oneVertex); // 找到顶点的第一条边
16 CEdge NextEdge(CEdge preEdge); // 找到一条边的下一条边
17 void SetEdge(int from, int to, int weight); // 设置边
18 void delEdge(int from, int to); // 删除边
19
20 void InitGraphM(int* pWArray2D); // 初始化图
21
22 void DFS(int oneVertex); // 深度优先搜索
23 void BFS(int oneVertex); // 广度优先搜索
24 void Visit(int oneVertex); // 访问顶点
25
26 void Travel(int startVertex = 0, int travelType = 0); // 周游接口合并
27 };
具体的功能实现放在下期文章,读者可先自行思考。
原文链接: https://www.cnblogs.com/SihanLin/p/14104003.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/205818
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!