图的代码实现(邻接矩阵)
不知上期各位读者思考得怎么样了，这期的文章是接上一期的。
本文的主要内容为：图的C++代码实现 (邻接矩阵法)，主要为各个类的具体实现
图的抽象基类
1 // FilenName: Graph.cpp
2
3 #include "Graph.h"
4
5 const int CGraph::UNVISITED = 0;
6 const int CGraph::VISITED = 1;
7
8 CGraph::CGraph(int numVertex) {
9 this->numVertex = numVertex;
10 this->numEdge = 0;
11 this->mark = new int[this->numVertex];
12 this->inDegree = new int[this->numVertex];
13
14 for(int i = 0; i < this->numVertex; i++){
15 this->mark[i] = CGraph::UNVISITED;
16 this->inDegree[i] = 0;
17 }
18 }
19
20 CGraph::~CGraph() {
21 delete[] this->mark;
22 delete[] this->inDegree;
23 }
24
25 int CGraph::GetVerticesNum() {
26 return this->numVertex;
27 }
28
29 int CGraph::GetEdgesNum() {
30 return this->numEdge;
31 }
32
33 int CGraph::GetFromVertex(CEdge oneEdge) {
34 return oneEdge.from;
35 }
36
37 int CGraph::GetToVertex(CEdge oneEdge) {
38 return oneEdge.to;
39 }
40
41 int CGraph::GetWeight(CEdge oneEdge) {
42 return oneEdge.weight;
43 }
44
45 bool CGraph::IsEdge(CEdge oneEdge) {
46 return (oneEdge.from >= 0 && oneEdge.to >=0 && oneEdge.weight >= 0);
47 }
48
49 void CGraph::ResetMark() {
50 for(int i = 0; i < this->numVertex; i++){
51 this->mark[i] = CGraph::UNVISITED;
52 }
53 }
图的邻接矩阵实现类
1 // FileName: GraphAdjacentMatrix.cpp
2
3 #include "GraphAdjacentMatrix.h"
4 #include <queue>
5 using namespace std;
6
7 /**********************************************
8 * 函数功能：构造函数，动态分配邻接矩阵二维数组，
9 * 调用者无需释放，析构函数会自动释放
10 * @param:
11 * numVertex: 图的顶点数目
12 * @return:
13 * 无
14 *********************************************/
15 CGraphM::CGraphM(int numVertex) : CGraph(numVertex) {
16 this->matrix = (int**) new int*[this->numVertex];
17 for(int i = 0; i < numVertex; i++){
18 this->matrix[i] = new int[this->numVertex];
19 }
20
21 for(int i = 0; i < numVertex; i++){
22 for(int j = 0; j < numVertex; j++){
23 this->matrix[i][j] = 0;
24 }
25 }
26 }
27
28
29 /************************************************
30 * 函数功能：析构函数，释放动态分配的邻接矩阵二维数组
31 * @param:
32 * Null
33 * @return:
34 * 无
35 ***********************************************/
36 CGraphM::~CGraphM() {
37 for(int i = 0; i < this->numVertex; i++){
38 delete [] this->matrix[i];
39 }
40 delete [] this->matrix;
41 }
42
43
44 /**********************************************
45 * 函数功能：删除边
46 * @param:
47 * from: 边的起点
48 * to: 边的终点
49 * @return:
50 * void
51 *********************************************/
52 void CGraphM::delEdge(int from, int to) {
53 if(from == to){
54 this->matrix[from][to] = 0;
55 }
56 else{
57 this->matrix[from][to] = -1;
58 }
59 this->inDegree[to]--;
60 this->numEdge--;
61 }
62
63 /**********************************************
64 * 函数功能：设置边
65 * @param:
66 * from: 边的起点
67 * to: 边的终点
68 * weight：边的权值
69 * @return:
70 * void
71 *********************************************/
72 void CGraphM::SetEdge(int from, int to, int weight) {
73 if(from == to){
74 this->matrix[from][to] = 0;
75 }
76 else{
77 this->matrix[from][to] = weight;
78 }
79 this->inDegree[to]++;
80 this->numEdge++;
81 }
82
83 /**********************************************
84 * 函数功能：获取以参数 oneVertex 为起点的第一条边
85 * @param:
86 * oneVertex: 边的起点
87 * @return:
88 * 边类对象
89 *********************************************/
90 CEdge CGraphM::FirstEdge(int oneVertex) {
91 CEdge resultEdge; // 函数返回值
92 resultEdge.from = oneVertex; // 起点
93
94 for(int i = 0; i < this->numVertex; i++){
95 if(this->matrix[resultEdge.from][i] > 0){
96 resultEdge.to = i;
97 resultEdge.weight = this->matrix[resultEdge.from][i];
98 break;
99 }
100 }
101 return resultEdge;
102 }
103
104 /**********************************************
105 * 函数功能：获取和参数 perEdge 同起点的下一条边
106 * @param:
107 * preEdge： 上一条边
108 * @return:
109 * 边类对象
110 *********************************************/
111 CEdge CGraphM::NextEdge(CEdge preEdge) {
112 CEdge resultEdge; // 函数返回值
113 resultEdge.from = preEdge.from; // 起点
114 if(preEdge.to < this->numVertex - 1){ // 如果上一条边的终点 小于 顶点的个数减1 则存在下一条边
115 for(int i = preEdge.to + 1; i < this->numVertex; i++){
116 if(this->matrix[preEdge.from][i] > 0){
117 resultEdge.to = i;
118 resultEdge.weight = this->matrix[preEdge.from][i];
119 break;
120 }
121 }
122 }
123 return resultEdge;
124 }
125
126 /**********************************************
127 * 函数功能：初始化图
128 * @param:
129 * pWArray2D: 二维邻接矩阵的一维指针
130 * @return:
131 * void
132 *********************************************/
133 void CGraphM::InitGraphM(int *pWArray2D) {
134 int N = this->numVertex;
135 int array_i_j = 0;
136
137 for(int i = 0; i < N; i++){
138 for(int j = 0; j < N; j++){
139 array_i_j = *(pWArray2D + i * N + j); // 用一维数组的方式访问二维数组 *(起点地址 + 行数 * 总行数 + 列数)
140 if(array_i_j > 0){
141 this->SetEdge(i, j, array_i_j);
142 }
143 }
144 }
145 }
146
147 /**********************************************
148 * 函数功能：深度优先搜索
149 * @param:
150 * oneVertex: 开始搜索的起点
151 * @return:
152 * void
153 *********************************************/
154 void CGraphM::DFS(int oneVertex) {
155 this->mark[oneVertex] = CGraph::VISITED;
156 this->Visit(oneVertex);
157
158 for(CEdge edge = this->FirstEdge(oneVertex); this->IsEdge(edge); edge = this->NextEdge(edge)){
159 if(this->mark[edge.to] == CGraph::UNVISITED){
160 this->DFS(edge.to);
161 }
162 }
163 }
164
165 /**********************************************
166 * 函数功能：广度优先搜索
167 * @param:
168 * oneVertex: 开始搜索的起点
169 * @return:
170 * void
171 *********************************************/
172 void CGraphM::BFS(int oneVertex) {
173 queue<int> queueEdge;
174 this->Visit(oneVertex);
175 this->mark[oneVertex] = CGraph::VISITED;
176 queueEdge.push(oneVertex);
177
178 while(!queueEdge.empty()){
179 int u = queueEdge.front();
180 queueEdge.pop();
181 for(CEdge edge = this->FirstEdge(oneVertex); this->IsEdge(edge); edge = this->NextEdge(edge)){
182 if(this->mark[edge.to] == CGraph::UNVISITED){
183 this->Visit(edge.to);
184 this->mark[edge.to] = CGraph::VISITED;
185 queueEdge.push(edge.to);
186 }
187 }
188 }
189 }
190
191
192 /**********************************************
193 * 函数功能：访问顶点
194 * @param:
195 * oneVertex: 要访问的顶点
196 * @return:
197 * void
198 *********************************************/
199 void CGraphM::Visit(int oneVertex) {
200 cout << "C" << oneVertex << " ";
201 }
202
203
204 /**********************************************
205 * 函数功能：图的周游接口合并
206 * @param:
207 * startVertex: 开始周游的起点
208 * travelType: 周游类型
209 * travelType = 0: DFS
210 * travelType = 1: BFS
211 * @return:
212 * void
213 *********************************************/
214 void CGraphM::Travel(int startVertex, int travelType) {
215 for(int i = startVertex, n = 0; n < this->numVertex; i++, n++){
216 i %= this->numVertex;
217 if(this->mark[i] == CGraph::UNVISITED){
218 switch(travelType){
219 case 0:
220 this->DFS(i);
221 break;
222 case 1:
223 this->BFS(i);
224 break;
225 default:
226 cout << "Error: travelType must be in [0, 1]" << endl;
227 break;
228 }
229 }
230 }
231 }
以上就是图的邻接矩阵的具体的实现方法。
有不懂之处，欢迎各位读者留言评论交流。
有不足之处，希望各位读者多多包涵，也希望读者们能留言评论指出我的不足，十分感谢！
下期预告：利用图实现：拓扑排序算法，最小路径算法，最小生成树算法，敬请期待。
赞 (0)