在一個有向圖為頂點表示活動的網(wǎng)中，我們稱為AOV網(wǎng)（Activity On Vertex Network）。設(shè)G={V,E}是一個具有n個頂點的有向圖，V中的頂點序列v1,v2,…,vn,滿足若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在vj之前。則我們稱這樣的頂點為一個拓撲序列。

所謂拓撲排序，其實就是對一個有向圖構(gòu)造拓撲序列的過程。如果所有的頂點被輸出，則說明有向圖中不存在回路，反之則是有回路。

一、拓撲排序算法的思路

拓撲排序往往用在有向鄰接表中，這里也就只用有向鄰接表來實現(xiàn)。

先找出所有節(jié)點的入度。

再在AOV網(wǎng)中選擇一個入度為0的頂點輸出，然后刪除此頂點，將其連接的節(jié)點的入度減一直至輸出所有頂點或者AOV網(wǎng)中不存在入度為0的頂點為止。

二、實現(xiàn)步驟

1.求個頂點的入度

設(shè)置一個indegree數(shù)組來存放各個頂點的入度。

int* indegree = (int*)malloc(sizeof(int) * G.vexnum);
//對單個節(jié)點p求入度
void CountIndegree(AdjList g, int* indegree, ArcNode* p) {
	while (p != NULL) {
		indegree[p->adjvex]++;
		p = p->nextarc;
	}
	return;
}

2.拓撲排序的實現(xiàn)

這里對棧的使用還是調(diào)用stl中的stack，比較方便。

bool TopoSort(AdjList g, int* indegree) {
	//先清空申請的indegree數(shù)組，或者也可以在初始化時采用calloc，就不用在這里置為0了
	for (int i = 0; i < g.vexnum; i++) {
		indegree[i] = 0;
	}
	//遍歷邊表中的每一個頂點，用CountIndegree()遍歷單個節(jié)點
	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用來表示已經(jīng)輸出的節(jié)點個數(shù)
	//如果所有的頂點被輸出，則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;
}