C++实现拓扑排序（AOV网络）

本文实例为大家分享了C++实现拓扑排序的具体代码，供大家参考，具体内容如下

一、思路

先扫描所有顶点，把入度为0的顶点（如C,E）进栈。然后，取栈顶元素，退栈，输出取得的栈顶元素v（即入度为0的顶点v）。接着，把顶点v的邻接顶点w的入度减1，如果w的入度变为0，则进栈。接着，取顶点w的兄弟结点（即取顶点v的邻接顶点w的下一邻接顶点），做同样的操作。重复上面步骤，直到输出n个顶点。

如上图：

（1）扫描所有顶点，把入度为0的顶点进栈：将顶点C，E进栈；

（2）取栈顶元素，退栈，输出取得的栈顶元素E。接着，把顶点E的邻接顶点A、B和F的入度减1，如果入度变为0，则进栈。因为顶点A入度变为0，所以要进栈；

（3）重复（2）步骤，直到输出n个顶点。

二、实现程序：

1.Graph.h:有向图

1. #ifndef Graph_h
2. #define Graph_h
3.  
4. #include <iostream>
5. using namespace std;
6.  
7. const int DefaultVertices = 30;
8.  
9. template <class T, class E>
10. struct Edge { // 边结点的定义
11. int dest; // 边的另一顶点位置
12. Edge<T, E> *link; // 下一条边链指针
13. };
14.  
15. template <class T, class E>
16. struct Vertex { // 顶点的定义
17. T data; // 顶点的名字
18. Edge<T, E> *adj; // 边链表的头指针
19. };
20.  
21. template <class T, class E>
22. class Graphlnk {
23. public:
24. const E maxValue = 100000; // 代表无穷大的值（=∞）
25. Graphlnk(int sz=DefaultVertices); // 构造函数
26. ~Graphlnk(); // 析构函数
27. void inputGraph(int count[]); // 建立邻接表表示的图
28. void outputGraph(); // 输出图中的所有顶点和边信息
29. T getValue(int i); // 取位置为i的顶点中的值
30. bool insertVertex(const T& vertex); // 插入顶点
31. bool insertEdge(int v1, int v2); // 插入边
32. bool removeVertex(int v); // 删除顶点
33. bool removeEdge(int v1, int v2); // 删除边
34. int getFirstNeighbor(int v); // 取顶点v的第一个邻接顶点
35. int getNextNeighbor(int v,int w); // 取顶点v的邻接顶点w的下一邻接顶点
36. int getVertexPos(const T vertex); // 给出顶点vertex在图中的位置
37. int numberOfVertices(); // 当前顶点数
38. private:
39. int maxVertices; // 图中最大的顶点数
40. int numEdges; // 当前边数
41. int numVertices; // 当前顶点数
42. Vertex<T, E> * nodeTable; // 顶点表(各边链表的头结点)
43. };
44.  
45. // 构造函数:建立一个空的邻接表
46. template <class T, class E>
47. Graphlnk<T, E>::Graphlnk(int sz) {
48. maxVertices = sz;
49. numVertices = 0;
50. numEdges = 0;
51. nodeTable = new Vertex<T, E>[maxVertices]; // 创建顶点表数组
52. if(nodeTable == NULL) {
53. cerr << "存储空间分配错误！" << endl;
54. exit(1);
55. }
56. for(int i = 0; i < maxVertices; i++)
57. nodeTable[i].adj = NULL;
58. }
59.  
60. // 析构函数
61. template <class T, class E>
62. Graphlnk<T, E>::~Graphlnk() {
63. // 删除各边链表中的结点
64. for(int i = 0; i < numVertices; i++) {
65. Edge<T, E> *p = nodeTable[i].adj; // 找到其对应链表的首结点
66. while(p != NULL) { // 不断地删除第一个结点
67. nodeTable[i].adj = p->link;
68. delete p;
69. p = nodeTable[i].adj;
70. }
71. }
72. delete []nodeTable; // 删除顶点表数组
73. }
74.  
75. // 建立邻接表表示的图
76. template <class T, class E>
77. void Graphlnk<T, E>::inputGraph(int count[]) {
78. int n, m; // 存储顶点树和边数
79. int i, j, k;
80. T e1, e2; // 顶点
81.  
82. cout << "请输入顶点数和边数：" << endl;
83. cin >> n >> m;
84. cout << "请输入各顶点：" << endl;
85. for(i = 0; i < n; i++) {
86. cin >> e1;
87. insertVertex(e1); // 插入顶点
88. }
89.  
90. cout << "请输入图的各边的信息：" << endl;
91. i = 0;
92. while(i < m) {
93. cin >> e1 >> e2;
94. j = getVertexPos(e1);
95. k = getVertexPos(e2);
96. if(j == -1 || k == -1)
97. cout << "边两端点信息有误，请重新输入！" << endl;
98. else {
99. insertEdge(j, k); // 插入边
100. count[k]++; // 记录入度
101. i++;
102. }
103. } // while
104. }
105.  
106. // 输出有向图中的所有顶点和边信息
107. template <class T, class E>
108. void Graphlnk<T, E>::outputGraph() {
109. int n, m, i;
110. T e1, e2; // 顶点
111. Edge<T, E> *p;
112.  
113. n = numVertices;
114. m = numEdges;
115. cout << "图中的顶点数为" << n << ",边数为" << m << endl;
116. for(i = 0; i < n; i++) {
117. p = nodeTable[i].adj;
118. while(p != NULL) {
119. e1 = getValue(i); // 有向边<i, p->dest>
120. e2 = getValue(p->dest);
121. cout << "<" << e1 << ", " << e2 << ">" << endl;
122. p = p->link; // 指向下一个邻接顶点
123. }
124. }
125. }
126.  
127. // 取位置为i的顶点中的值
128. template <class T, class E>
129. T Graphlnk<T, E>::getValue(int i) {
130. if(i >= 0 && i < numVertices)
131. return nodeTable[i].data;
132. return NULL;
133. }
134.  
135. // 插入顶点
136. template <class T, class E>
137. bool Graphlnk<T, E>::insertVertex(const T& vertex) {
138. if(numVertices == maxVertices) // 顶点表满，不能插入
139. return false;
140. nodeTable[numVertices].data = vertex; // 插入在表的最后
141. numVertices++;
142. return true;
143. }
144.  
145. // 插入边
146. template <class T, class E>
147. bool Graphlnk<T, E>::insertEdge(int v1, int v2) {
148. if(v1 == v2) // 同一顶点不插入
149. return false;
150. if(v1 >= 0 && v1 < numVertices && v2 >= 0 && v2 < numVertices) {
151. Edge<T, E> *p = nodeTable[v1].adj; // v1对应的边链表头指针
152. while(p != NULL && p->dest != v2) // 寻找邻接顶点v2
153. p = p->link;
154. if(p != NULL) // 已存在该边，不插入
155. return false;
156. p = new Edge<T, E>; // 创建新结点
157. p->dest = v2;
158. p->link = nodeTable[v1].adj; // 链入v1边链表
159. nodeTable[v1].adj = p;
160. numEdges++;
161. return true;
162. }
163. return false;
164. }
165.  
166. // 有向图删除顶点较麻烦
167. template <class T, class E>
168. bool Graphlnk<T, E>::removeVertex(int v) {
169. if(numVertices == 1 || v < 0 || v > numVertices)
170. return false; // 表空或顶点号超出范围
171.  
172. Edge<T, E> *p, *s;
173. // 1.清除顶点v的边链表结点w 边<v,w>
174. while(nodeTable[v].adj != NULL) {
175. p = nodeTable[v].adj;
176. nodeTable[v].adj = p->link;
177. delete p;
178. numEdges--; // 与顶点v相关联的边数减1
179. } // while结束
180. // 2.清除<w, v>，与v有关的边
181. for(int i = 0; i < numVertices; i++) {
182. if(i != v) { // 不是当前顶点v
183. s = NULL;
184. p = nodeTable[i].adj;
185. while(p != NULL && p->dest != v) {// 在顶点i的链表中找v的顶点
186. s = p;
187. p = p->link; // 往后找
188. }
189. if(p != NULL) { // 找到了v的结点
190. if(s == NULL) { // 说明p是nodeTable[i].adj
191. nodeTable[i].adj = p->link;
192. } else {
193. s->link = p->link; // 保存p的下一个顶点信息
194. }
195. delete p; // 删除结点p
196. numEdges--; // 与顶点v相关联的边数减1
197. }
198. }
199. }
200. numVertices--; // 图的顶点个数减1
201. nodeTable[v].data = nodeTable[numVertices].data; // 填补,此时numVertices，比原来numVertices小1，所以，这里不需要numVertices-1
202. nodeTable[v].adj = nodeTable[numVertices].adj;
203. // 3.要将填补的顶点对应的位置改写
204. for(int i = 0; i < numVertices; i++) {
205. p = nodeTable[i].adj;
206. while(p != NULL && p->dest != numVertices) // 在顶点i的链表中找numVertices的顶点
207. p = p->link; // 往后找
208. if(p != NULL) // 找到了numVertices的结点
209. p->dest = v; // 将邻接顶点numVertices改成v
210. }
211. return true;
212. }
213.  
214. // 删除边
215. template <class T, class E>
216. bool Graphlnk<T, E>::removeEdge(int v1, int v2) {
217. if(v1 != -1 && v2 != -1) {
218. Edge<T, E> * p = nodeTable[v1].adj, *q = NULL;
219. while(p != NULL && p->dest != v2) { // v1对应边链表中找被删除边
220. q = p;
221. p = p->link;
222. }
223. if(p != NULL) { // 找到被删除边结点
224. if(q == NULL) // 删除的结点是边链表的首结点
225. nodeTable[v1].adj = p->link;
226. else
227. q->link = p->link; // 不是，重新链接
228. delete p;
229. return true;
230. }
231. }
232. return false; // 没有找到结点
233. }
234.  
235. // 取顶点v的第一个邻接顶点
236. template <class T, class E>
237. int Graphlnk<T, E>::getFirstNeighbor(int v) {
238. if(v != -1) {
239. Edge<T, E> *p = nodeTable[v].adj; // 对应链表第一个边结点
240. if(p != NULL) // 存在，返回第一个邻接顶点
241. return p->dest;
242. }
243. return -1; // 第一个邻接顶点不存在
244. }
245.  
246. // 取顶点v的邻接顶点w的下一邻接顶点
247. template <class T, class E>
248. int Graphlnk<T, E>::getNextNeighbor(int v,int w) {
249. if(v != -1) {
250. Edge<T, E> *p = nodeTable[v].adj; // 对应链表第一个边结点
251. while(p != NULL && p->dest != w) // 寻找邻接顶点w
252. p = p->link;
253. if(p != NULL && p->link != NULL)
254. return p->link->dest; // 返回下一个邻接顶点
255. }
256. return -1; // 下一个邻接顶点不存在
257. }
258.  
259. // 给出顶点vertex在图中的位置
260. template <class T, class E>
261. int Graphlnk<T, E>::getVertexPos(const T vertex) {
262. for(int i = 0; i < numVertices; i++)
263. if(nodeTable[i].data == vertex)
264. return i;
265. return -1;
266. }
267.  
268. // 当前顶点数
269. template <class T, class E>
270. int Graphlnk<T, E>::numberOfVertices() {
271. return numVertices;
272. }
273.  
274. #endif /* Graph_h */

2.TopLogicalSort.h

1. #ifndef TopLogicalSort_h
2. #define TopLogicalSort_h
3. #include "Graph.h"
4.  
5. template <class T, class E>
6. void TopLogicalSort(Graphlnk<T, E> &G) {
7. int i, w, v;
8. int n; // 顶点数
9. int *count = new int[DefaultVertices]; // 入度数组
10. int top = -1;
11.  
12. // 清零
13. for(i = 0; i< DefaultVertices; i++)
14. count[i] = 0;
15. // 输入顶点和边
16. G.inputGraph(count);
17. n = G.numberOfVertices(); // 获取图的顶点数
18. for(i = 0; i < n; i++) { // 检查网络所有顶点
19. if(count[i] == 0) { // 入度为0的顶点进栈
20. count[i] = top;
21. top = i;
22. }
23. }
24. // 进行拓扑排序，输出n个顶点
25. for(i = 0; i < n; i++) {
26. if(top == -1) { // 空栈
27. cout << "网络中有回路！" << endl;
28. return;
29. } else {
30. v = top;
31. top = count[top];
32. cout << G.getValue(v) << " "; // 输出入度为0的顶点
33. w = G.getFirstNeighbor(v); // 邻接顶点
34. while(w != -1) { // 扫描出边表
35. if(--count[w] == 0) { // 邻接顶点入度减1，如果入度为0则进栈
36. count[w] = top;
37. top = w;
38. }
39. w = G.getNextNeighbor(v, w); // 兄弟结点（取顶点v的邻接顶点w的下一邻接顶点）
40. }
41. }
42. }
43. cout << endl;
44. }
45.  
46. #endif /* TopLogicalSort_h */
47. 3.main.cpp
48.  
49. #include "TopLogicalSort.h"
50.  
51. int main(int argc, const char * argv[]) {
52. Graphlnk<char, int> G; // 声明图对象
53.  
54. TopLogicalSort(G); // AOV网络的拓扑排序
55. return 0;
56. }

测试数据：

6 8
A B C D E F
A B
A D
B F
C B
C F
E A
E F
E B

测试结果：

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

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