C/C++浅析邻接表拓扑排序算法的实现_C 语言

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;
}

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;
}