邻接表拓扑排序算法【C/C++】

---

前言

在软件开发、施工过程、教学安排等等的一系列活动中，往往需要一个有向无环图来表示其是否成成功进行下去。

在一个有向图为顶点表示活动的网中，我们称为AOV网（Activity On Vertex Network）。设G={V,E}是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在vj之前。则我们称这样的顶点为一个拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。如果所有的顶点被输出，则说明有向图中不存在回路，反之则是有回路。

---

一、拓扑排序算法的思路

拓扑排序往往用在有向邻接表中，这里也就只用有向邻接表来实现。

先找出所有节点的入度。

再在AOV网中选择一个入度为0的顶点输出，然后删除此顶点，将其连接的节点的入度减一直至输出所有顶点或者AOV网中不存在入度为0的顶点为止。

二、实现步骤

1.求个顶点的入度

设置一个indegree数组来存放各个顶点的入度。

int* indegree = (int*)malloc(sizeof(int) * G.vexnum);
//对单个节点p求入度
void CountIndegree(AdjList g, int* indegree, ArcNode* p) {
	while (p != NULL) {
		indegree[p->adjvex]++;
		p = p->nextarc;
	}
	return;
}
1
2
3
4
5
6
7
8
9

2.拓扑排序的实现

这里对栈的使用还是调用stl中的stack，比较方便。

bool TopoSort(AdjList g, int* indegree) {
	//先清空申请的indegree数组，或者也可以在初始化时采用calloc，就不用在这里置为0了
	for (int i = 0; i < g.vexnum; i++) {
		indegree[i] = 0;
	}
	//遍历边表中的每一个顶点，用CountIndegree()遍历单个节点
	for (int i = 0; i < g.vexnum; i++) {
		ArcNode* p = g.vertexlist[i].firstarc;
		CountIndegree(g, indegree, p);
	}
	stack<int>S;
	//如果该顶点的入度为0，则入栈。
	for (int i = 0; i < g.vexnum; i++) {
		if (indegree[i] == 0) {
			S.push(i);
		}
	}
	//count用来表示已经输出的节点个数
	//如果所有的顶点被输出，则count==g.vexnum，无回路，反之count<g.vexnum,则是有回路。
	int count = 0;
	while (!S.empty()) {
		int top = S.top();
		printf("%c ", g.vertexlist[top].data);
		S.pop();
		count++;
		ArcNode* p = g.vertexlist[top].firstarc;
		for (p; p != NULL; p = p->nextarc) {
			int i = p->adjvex;
			if (--indegree[i] == 0) {
				S.push(i);
			}
		}
	}
	if (count == g.vexnum) {
		return true;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

三、测试结果

自己花了一个看起来挺复杂的图，一下也看不出来有没有环

首先算一算入度，顺带打印一下。

接下来是拓扑排序的结果

完美！

四、全部代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
#define MAX 20
#define INFINITY 65535//代表正无穷
typedef char VertexData;//顶点数据类型
typedef int EdgeData;//带权图上的权值数据类型
typedef int MatrixAdjType;
using namespace std;
//图的存储结构

//邻接表法
typedef struct ArcNode {//弧节点
	int adjvex;//该弧指向的顶点位置
	struct ArcNode* nextarc;//指向下一个弧的指针
	//EDGETYPE info;//权值
	int weight;
}ArcNode;
typedef struct VertexNode {
	VertexData data;//顶点数据
	ArcNode* firstarc;//指向该顶点的第一条弧的指针
}VertexNode;
typedef struct {
	VertexNode vertexlist[MAX];
	int vexnum, arcnum;
}AdjList;

//求顶点位置函数
int LocateVertex(AdjList* G, VertexData v) {
	for (int i = 0; i < G->vexnum; i++) {
		if (G->vertexlist[i].data == v) {
			return i;
		}
	}
}
//创建邻接表
void CreateAdjList(AdjList* g) {
	int i, j, k, weight;
	char vi, vj;
	printf("请输入顶点数和边数：\n");
	scanf("%d,%d", &g->vexnum, &g->arcnum);
	for (i = 0; i < g->vexnum; i++) {
		g->vertexlist[i].data = 'A' + i;
		g->vertexlist[i].firstarc = NULL;
	}
	printf("请输入弧的起点，终点和权值：\n");
	for (k = 0; k < g->arcnum; k++) {
		scanf(" %c ,%c,%d", &vi, &vj, &weight);
		ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = LocateVertex(g, vj);
		p->weight = weight;
		ArcNode* tmp = g->vertexlist[LocateVertex(g, vi)].firstarc;
		if (tmp == NULL) {
			g->vertexlist[LocateVertex(g, vi)].firstarc = p;
			p->nextarc = NULL;
		}
		else {
			while (tmp->nextarc != NULL) {
				tmp = tmp->nextarc;
			}
			p->nextarc = tmp->nextarc;
			tmp->nextarc = p;
		}

		//无向图有
#if 0
		ArcNode* s = (ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex = LocateVertex(g, vi);
		s->weight = weight;
		ArcNode* tmp2 = g->vertexlist[LocateVertex(g, vj)].firstarc;
		if (tmp2 == NULL) {
			s->nextarc = g->vertexlist[LocateVertex(g, vj)].firstarc;
			g->vertexlist[LocateVertex(g, vj)].firstarc = s;
		}
		else {
			while (tmp2->nextarc != NULL) {
				tmp2 = tmp2->nextarc;
			}
			s->nextarc = tmp2->nextarc;
			tmp2->nextarc = s;
		}
#endif
	}
}

//邻接表递归实现DFS
int visited[MAX];
void DepthFirstSearch(AdjList g, int v0) {
	printf("%c ", g.vertexlist[v0].data);
	visited[v0] = 1;

	ArcNode* p = g.vertexlist[v0].firstarc;
	/*while (p != NULL) {
		if (!visited[p->adjvex]) {
			DepthFirstSearch(g, p->adjvex);
		}
		p = p->nextarc;
	}
	*/
	for (p; p != NULL; p = p->nextarc) {
		if (!visited[p->adjvex]) {
			DepthFirstSearch(g, p->adjvex);
		}
	}
}
void TraverseGraph(AdjList g) {
	for (int vi = 0; vi < g.vexnum; vi++) {
		visited[vi] = 0;
	}
	for (int vi = 0; vi < g.vexnum; vi++) {
		if (!visited[vi]) {
			DepthFirstSearch(g, vi);
		}
	}
}

//邻接表非递归实现DFS
void NoReDepthFirstSearch(AdjList g, int v0) {
	printf("%c ", g.vertexlist[v0].data);
	//visit(v0);
	visited[v0] = 1;
	stack<int>S;
	S.push(v0);
	while (!S.empty()) {
		int top = S.top();
		ArcNode* p = g.vertexlist[top].firstarc;
		/*
		while (p != NULL) {
			if (!visited[p->adjvex]) {
				printf("%c ", g.vertexlist[p->adjvex].data);
				//visit(p->adjvex);
				visited[p->adjvex] = 1;
				S.push(p->adjvex);
				p = p->nextarc;
				break;
			}
			p = p->nextarc;
		}
		*/
		for (p; p != NULL; p = p->nextarc) {
			if (!visited[p->adjvex]) {
				printf("%c ", g.vertexlist[p->adjvex].data);
				//visit(p->adjvex);
				visited[p->adjvex] = 1;
				S.push(p->adjvex);
				break;
			}
		}
		if (p == NULL) {
			S.pop();
		}
	}
}
void NoReTraverseGraph(AdjList g) {
	for (int vi = 0; vi < g.vexnum; vi++) {
		visited[vi] = 0;
	}
	for (int vi = 0; vi < g.vexnum; vi++) {
		if (!visited[vi]) {
			NoReDepthFirstSearch(g, vi);
		}
	}
}

//邻接表非递归实现BFS
void NoReBroadFirstSearch(AdjList g, int v) {
	printf("%c ", g.vertexlist[v].data);
	visited[v] = 1;
	queue<int>Q;
	Q.push(v);
	while (!Q.empty()) {
		int front = Q.front();
		ArcNode* p = g.vertexlist[front].firstarc;
		for (p; p != NULL; p = p->nextarc) {
			if (!visited[p->adjvex]) {
				printf("%c ", g.vertexlist[p->adjvex].data);
				visited[p->adjvex] = 1;
				Q.push(p->adjvex);
			}
		}
		if (p == NULL) {
			Q.pop();
		}
	}
}
void NoReTraverseGrap(AdjList g) {
	for (int vi = 0; vi < g.vexnum; vi++) {
		visited[vi] = 0;
	}
	for (int vi = 0; vi < g.vexnum; vi++) {
		if (!visited[vi]) {
			NoReBroadFirstSearch(g, vi);
		}
	}
}

//对单个节点p求入度
void CountIndegree(AdjList g, int* indegree, ArcNode* p) {
	while (p != NULL) {
		indegree[p->adjvex]++;
		p = p->nextarc;
	}
	return;
}

//拓扑排序
bool TopoSort(AdjList g, int* indegree) {
	//先清空申请的indegree数组，或者也可以在初始化时采用calloc，就不用在这里置为0了
	for (int i = 0; i < g.vexnum; i++) {
		indegree[i] = 0;
	}
	//遍历边表中的每一个顶点，用CountIndegree()遍历单个节点
	for (int i = 0; i < g.vexnum; i++) {
		ArcNode* p = g.vertexlist[i].firstarc;
		CountIndegree(g, indegree, p);
	}
	stack<int>S;
	//如果该顶点的入度为0，则入栈。
	for (int i = 0; i < g.vexnum; i++) {
		if (indegree[i] == 0) {
			S.push(i);
		}
	}
	//count用来表示已经输出的节点个数
	//如果所有的顶点被输出，则count==g.vexnum，无回路，反之count<g.vexnum,则是有回路。
	int count = 0;
	while (!S.empty()) {
		int top = S.top();
		printf("%c ", g.vertexlist[top].data);
		S.pop();
		count++;
		ArcNode* p = g.vertexlist[top].firstarc;
		for (p; p != NULL; p = p->nextarc) {
			int i = p->adjvex;
			if (--indegree[i] == 0) {
				S.push(i);
			}
		}
	}
	if (count == g.vexnum) {
		return true;
	}
	return false;
}

void test() {
	AdjList G;
	CreateAdjList(&G);
	printf("递归DFS\n");
	TraverseGraph(G);
	printf("\n");
	printf("非递归DFS\n");
	NoReTraverseGraph(G);
	printf("\n");
	printf("非递归BFS\n");
	NoReTraverseGrap(G);
	printf("\n");
	//拓朴排序
#if 1
	//计算入度
	int* indegree = (int*)malloc(sizeof(int) * G.vexnum);
	//打印入度
	for (int i = 0; i < G.vexnum; i++) {
		indegree[i] = 0;
	}
	for (int i = 0; i < G.vexnum; i++) {
		ArcNode* p = G.vertexlist[i].firstarc;
		CountIndegree(G, indegree, p);
	}
	for (int i = 0; i < G.vexnum; i++) {
		printf("%c 的入度是 %d\n", G.vertexlist[i].data, indegree[i]);
	}

	int ret = TopoSort(G, indegree);
	printf("\n");
	if (ret == 1) {
		printf("拓扑排序成功,为有向无环图\n");
	}
	else {
		printf("拓扑排序失败，图中有环\n");
	}
#endif
	return;
}

int main() {
	test();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291

---

总结

每个顶点进栈一次出战一次，度减一的操作执行了e次，所以整个算法的时间复杂度为O(n+e)。