C++实现图的邻接矩阵表示

本文实例为大家分享了C++实现图的邻接矩阵表示代码，供大家参考，具体内容如下

1.遇到的问题：教材中写着子类Graphmtx(我用GrapMatrix)继承基类Graph

但是我在子类GraphMatrix中使用父类Graph的保护成员属性：maxVertices 显示没有声明（如下图）。

原来，c++中声明一个模板类及子类，在子类中如果需要访问父类的protected变量，需要使用父类的类作用域限定符，否则会报“identifier not found”错误。如果不是模板类，可以直接访问。

例如：要如下这样使用父类的保护成员属性，太麻烦了。

所以，我就不用继承基类的方法了。直接把Graph父类的保护成员属性放到GrapMatrix类中。

2.实现程序：

（1）GraphMatrix.h

1. #ifndef GraphMatrix_h
2. #define GraphMatrix_h
3. #include <iostream>
4. using namespace std;
5.  
6. const int DefaultVertices = 30; // 默认最大顶点数
7.  
8. template <class T, class E>
9. class GraphMatrix {
10. public:
11. const E maxWeight = 100000; // 代表无穷大的值（=∞）
12. GraphMatrix(int sz=DefaultVertices); // 构造函数
13. ~GraphMatrix(); // 析构函数
14. void inputGraph(); // 创建基于邻接矩阵的图
15. void outputGraph(); // 输出图的所有顶点和边信息
16. T getValue(int i); // 取顶点i的值，i不合理返回0
17. E getWeight(int v1, int v2); // 取边(v1, v2)上的权值
18. int getFirstNeighbor(int v); // 取顶点v的第一个邻接顶点
19. int getNextNeighbor(int v, int w); // 取v的邻接顶点w的下一个邻接顶点
20. bool insertVertex(const T& vertex); // 插入顶点vertice
21. bool insertEdge(int v1, int v2, E cost); // 插入边(v1, v2)权值为cost
22. bool removeVertex(int v); // 删去顶点v和所有与它相关联的边
23. bool removeEdge(int v1, int v2); // 在图中删去边(v1, v2)
24. int getVertexPos(T vertex); // 给出顶点vertice在图中的位置
25. private:
26. int maxVertices; // 图中最大的顶点数
27. int numEdges; // 当前边数
28. int numVertices; // 当前顶点数
29. T *VerticesList; // 顶点表
30. E **Edge; // 邻接矩阵
31. };
32.  
33. // 构造函数
34. template <class T, class E>
35. GraphMatrix<T, E>::GraphMatrix(int sz) {
36. int i, j;
37.  
38. maxVertices = sz;
39. numVertices = 0;
40. numEdges = 0;
41. VerticesList = new T[maxVertices]; // 创建顶点表数组
42. Edge = new E*[maxVertices]; // 创建邻接矩阵数组
43. for(i = 0; i < maxVertices; i++)
44. Edge[i] = new E[maxVertices];
45. for(i = 0; i < maxVertices; i++) { // 邻接矩阵初始化
46. for(j = 0; j < maxVertices; j++)
47. {
48. if(i == j) // 矩阵对角处，即为同一顶点
49. Edge[i][j] = 0;
50. else // 不是同一顶点的，即两顶点一开始没有边相连，为无穷大∞
51. Edge[i][j] = maxWeight;
52. }
53. }
54. }
55.  
56. // 析构函数
57. template <class T, class E>
58. GraphMatrix<T, E>::~GraphMatrix() {
59. delete []VerticesList; // 释放动态分配的空间
60. delete []Edge;
61. }
62.  
63. // 创建基于邻接矩阵的图
64. template <class T, class E>
65. void GraphMatrix<T, E>::inputGraph() {
66. int i, j, k;
67. int n, m; // 要输入的顶点数和边数
68. T e1, e2; // 边的两端顶点
69. E weight; // 边对应的权值
70.  
71. cout << "请输入顶点数和边数:" << endl;
72. cin >> n >> m;
73. cout << "请输入顶点：" << endl;
74. for(i = 0; i < n; i++) { // 建立顶点表数据
75. cin >> e1;
76. insertVertex(e1); // 插入
77. }
78. cout << "请输入边的两端顶点和权值:" << endl;
79. i = 0;
80. while(i < m){ // 输入边
81. cin >> e1 >> e2 >> weight; // 输入端点信息
82. j = getVertexPos(e1); // 查顶点号
83. k = getVertexPos(e2);
84. if(j == -1 || k == -1)
85. cout << "边两端点信息有误，重新输入!" << endl;
86. else {
87. insertEdge(j, k, weight);
88. i++;
89. }
90. } // for结束
91. }
92.  
93. // 输出图的所有顶点和边信息
94. template <class T, class E>
95. void GraphMatrix<T, E>::outputGraph() {
96. int i, j, n, m;
97. T e1, e2;
98. E w;
99.  
100. n = numVertices;
101. m = numEdges;
102. cout << "顶点数为：" << n << "，边数为：" << m << endl;
103. for(i = 0; i < n; i++) {
104. for(j = i+1; j < n; j++) {
105. w = getWeight(i, j); // 取边上权值
106. if(w > 0 && w < maxWeight) { // 有效，即这两顶点存在边
107. e1 = getValue(i);
108. e2 = getValue(j);
109. cout << "(" << e1 << "," << e2 << "," << w << ")" << endl;
110. }
111. }
112. } // for
113. }
114.  
115. // 给出顶点vertice在图中的位置
116. template <class T, class E>
117. int GraphMatrix<T, E>::getVertexPos(T vertex) {
118. for(int i = 0; i < numVertices; i++)
119. if(VerticesList[i] == vertex)
120. return i;
121. return -1;
122. }
123.  
124. // 取顶点i的值，i不合理返回NULL
125. template <class T, class E>
126. T GraphMatrix<T, E>::getValue(int i) {
127. if(i >= 0 && i < numVertices)
128. return VerticesList[i];
129. return NULL;
130. }
131.  
132. // 取边(v1, v2)上的权值
133. template <class T, class E>
134. E GraphMatrix<T, E>::getWeight(int v1, int v2) {
135. if(v1 != -1 && v2 != -1) // 存在这两个顶点
136. return Edge[v1][v2];
137. return 0;
138. }
139.  
140. // 取顶点v的第一个邻接顶点
141. template <class T, class E>
142. int GraphMatrix<T, E>::getFirstNeighbor(int v) {
143. if(v != -1) {
144. for(int col = 0; col < numVertices; col++)
145. if(Edge[v][col] > 0 && Edge[v][col] <maxWeight)
146. return col;
147. }
148. return -1;
149. }
150.  
151. // 取v的邻接顶点w的下一个邻接顶点
152. template <class T, class E>
153. int GraphMatrix<T, E>::getNextNeighbor(int v, int w) {
154. if(v != -1 && w != -1) {
155. for(int col = w+1; col < numVertices; col++) {
156. if(Edge[v][col] > 0 && Edge[v][col] < maxWeight)
157. return col;
158. }
159. }
160. return -1;
161. }
162.  
163. // 插入顶点vertice
164. template <class T, class E>
165. bool GraphMatrix<T, E>::insertVertex(const T& vertex) {
166. if(numVertices == maxVertices) // 顶点表满
167. return false;
168. VerticesList[numVertices++] = vertex;
169. return true;
170. }
171.  
172. // 插入边(v1, v2)权值为cost
173. template <class T, class E>
174. bool GraphMatrix<T, E>::GraphMatrix<T, E>::insertEdge(int v1, int v2, E cost) {
175. if(v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices && Edge[v1][v2] == maxWeight) { // 顶点v1,v2都存在，并且v1，v2没有边
176. Edge[v1][v2] = Edge[v2][v1] = cost;
177. numEdges++;
178. return true;
179. }
180. return false;
181. }
182.  
183. // 删去顶点v和所有与它相关联的边
184. template <class T, class E>
185. bool GraphMatrix<T, E>::removeVertex(int v) {
186. if(v < 0 && v > numVertices) // v不在图中，不删除
187. return false;
188. if(numVertices == 1) // 只剩一个顶点，不删除
189. return false;
190. int i, j;
191.  
192. VerticesList[v] = VerticesList[numVertices-1]; // 用最后一个顶点替代当前要删的顶点
193. // 删除与v相关联边数
194. for(i = 0; i < numVertices; i++) {
195. if(Edge[i][v] > 0 && Edge[i][v] < maxWeight)
196. numEdges--;
197. }
198. // 用最后一列，填补第v列
199. for(i = 0; i < numVertices; i++)
200. Edge[i][v] = Edge[i][numVertices-1];
201. numVertices--; // 顶点数减1
202. // 用最后一行，填补第v行
203. for(j = 0; j < numVertices; j++)
204. Edge[v][j] = Edge[numVertices][j];
205. return true;
206. }
207.  
208. // 在图中删去边(v1, v2)
209. template <class T, class E>
210. bool GraphMatrix<T, E>::removeEdge(int v1, int v2) {
211. if(v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices && Edge[v1][v2] < maxWeight) {
212. Edge[v1][v2] = Edge[v2][v1] = maxWeight;
213. numEdges--; // 边数减1
214. return true;
215. }
216. return false;
217. }
218.  
219. #endif /* GraphMatrix_h */

（2）main.cpp

1. // 测试数据：
2. /*
3. 5 7
4. A B C D E
5. A B 24 A C 46 B C 15 B E 67 C B 37 C D 53 E D 31
6. */
7.  
8. #include "GraphMatrix.h"
9.  
10. int main(int argc, const char * argv[]) {
11. GraphMatrix<char, int> st; // 声明对象
12. bool finished = false;
13. int choice;
14. char e1, e2, next;
15. int weight;
16.  
17. while(!finished) {
18. cout << "[1]创建基于邻接矩阵的图" << endl;
19. cout << "[2]输出图的所有顶点和边信息" << endl;
20. cout << "[3]取顶点v的第一个邻接顶点" << endl;
21. cout << "[4]取v的邻接顶点w的下一个邻接顶点" << endl;
22. cout << "[5]插入顶点" << endl;
23. cout << "[6]插入边" << endl;
24. cout << "[7]删除顶点" << endl;
25. cout << "[8]删除边" << endl;
26. cout << "[9]退出" << endl;
27. cout << "请输入选择[1-9]：";
28. cin >> choice;
29. switch(choice) {
30. case 1:
31. st.inputGraph();
32. break;
33. case 2:
34. st.outputGraph();
35. break;
36. case 3:
37. cout << "请输入顶点:";
38. cin >> e1;
39. e2 = st.getValue(st.getFirstNeighbor(st.getVertexPos(e1)));
40. if(e2)
41. cout << "顶点" << e1 << "的第一个邻接顶点为:" << e2 << endl;
42. else
43. cout << "顶点" << e1 << "没有邻接顶点！" << endl;
44. break;
45. case 4:
46. cout << "请输入顶点v和邻接顶点w:";
47. cin >> e1 >> e2;
48. next = st.getValue(st.getNextNeighbor(st.getVertexPos(e1), st.getVertexPos(e2)));
49. if(next)
50. cout << "顶点" << e1 << "的邻接顶点" << e2 << "的下一个邻接顶点为:" << next << endl;
51. else
52. cout << "顶点" << e1 << "的邻接顶点" << e2 << "没有下一个邻接顶点！" << endl;
53. break;
54. case 5:
55. cout << "请输入要插入的顶点：";
56. cin >> e1;
57. if(st.insertVertex(e1))
58. cout << "插入成功！" << endl;
59. else
60. cout << "表已满，插入失败！" << endl;
61. break;
62. case 6:
63. cout << "请输入要插入的边的信息:" << endl;
64. cin >> e1 >> e2 >> weight;
65. st.insertEdge(st.getVertexPos(e1), st.getVertexPos(e2), weight);
66. break;
67. case 7:
68. cout << "请输入要删除的顶点：";
69. cin >> e1;
70. if(st.removeVertex(st.getVertexPos(e1)))
71. cout << "顶点" << e1 << "已删除!" << endl;
72. else
73. cout << "顶点" << e1 << "不在图中!" << endl;
74. break;
75. case 8:
76. cout << "请输入要删除的边的两个端点：" << endl;
77. cin >> e1 >> e2;
78. st.removeEdge(st.getVertexPos(e1), st.getVertexPos(e2));
79. break;
80. case 9:
81. finished = true;
82. break;
83. default:
84. cout << "选择输入错误，请重新输入!" << endl;
85. }
86. }
87. return 0;
88. }

测试结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

原文链接：https://blog.csdn.net/chuanzhouxiao/article/details/88686127