拓扑排序（C++类封装+数组模拟队列和邻接表）

拓扑序列

对于任何无回路的AOV网，其顶点均可排成拓扑序列，并且其拓扑序列未必唯一。步骤如下：

1.从网中选择一个入度为0的顶点且输出。

2.从网中删除该顶点及其所有出边。

3.执行1，2，直至所有顶点已输出，或网中剩余顶点均不为0，说明网中存在回路，无法继续拓扑排列。（因此拓扑排列算法也可用来判断一个有向图中是否存在回路。）

准备工作

假定AOV网用邻接表的形式存储，为实现拓扑排序算法，事先需做好以下两项准备工作：

1.建立一个数组count[ ]，count[i]的元素值取对应顶点i的入度。

2.建立一个堆栈，栈中存放入度为0的顶点，每当一个顶点的入度为0，就将其压入栈。

优化模拟堆栈

事实上，可以不为该顶点栈另外分配存储空间，而实直接利用入度为0的顶点的count[ ]数组元素的值来模拟堆栈的压入和弹出。方法如下：

1.设置一个”栈顶指针“top，以指示当前”栈顶“位置（这里的”栈“是模拟的，实际并不存在真正的堆栈）。

2.初始化“栈”时，top值设为-1，表示”栈“空。

3.当顶点i的入度为0，应该进“栈”时，将“栈顶指针”所指的顶点序号放在count[i]中，并更新“栈顶指针”top，令其指向顶点i：

count[I]=top;

top=i;

4.当应该从“栈”中弹出一个顶点时，把原“栈顶”位置记录下来，top退到“次栈顶”：

j=top;

top=count[top];

入度为0的顶点均要被压入“栈”，故每一次“弹出”的顶点（top所指向的顶点）入度都是0，显然，顶点的被弹出次序实际是“栈顶”指针top的变化次序，也就是拓扑排序时顶点的输出次序。如果“栈顶指针”top值变为-1，而顶点却未被全部输出，说明网中有回路，此时算法强制终止拓扑排序。

实现代码 

形式一：类封装

//对包含n个顶点的AOV网进行拓扑排序
void Graph_List::TopoOrder() {
	int n = graphsize;
	int* count = new int[n];
	//计算count数组
	for (int i = 0; i < n; i++) count[i] = 0;
	for (int i = 0; i < n; i++) {
		Edge* p = Head[i].adjacent;
		while (p != NULL) {
			count[p->VerAdj]++;
			p = p->link;
		}
	}
	int top = -1;  //初始化“栈顶指针”
	for (int i = 0; i < n; i++) {
		if (count[i] == 0) {
			count[i] = top;
			top = i;
		}
	}
	for (int i = 0; i < n; i++) {
		//若循环体尚未被执行n次，栈顶指针已为-1，说明有回路，终止程序
		if (top == -1) {
			cout << "There is a cycle in network!" << endl;
			return;
		}
		else {
			int j = top;  //从栈中弹出一个顶点j
			top = count[top];
			cout << j << endl;  //输出该顶点
			Edge* p = Head.adjacent;  //令p为j的边链表头指针
			while (p != NULL) {  //从当前的图中删除与j关联的边
				int k = p->VerAdj;  //k为边终点
				if (--count[k] == 0) {  //入度-1
					count[k] = top;  //若入度为0，则k入栈
					top = k;
				}
				p = p->link;
			}
		}
	}
	delete[] count;
}

形式二：数组模拟队列和邻接表 

const int N=100010;
int n; //顶点数
//数组模拟队列和邻接表的拓扑排序
void topsort() {
	int q[N];  //模拟队列的数组q
	int hh = 0, tt = -1;  //队头hh，队尾tt
	int	count[N] = { 0 };  //存储图中所有顶点的入度
	int h[N]={ -1 }, e[N], ne[N], idx = 0;  //h为顶点结点，e存储顶点值，ne表示链接关系,-1表示无邻接点
	//计算所有顶点的入度
	for (int i = 1; i <= n; i++) {
		for (int j = h[i]; j != -1; j = ne[j]) {
			count[e[j]]++;
		}
	}
	//将n个顶点中所有入度为0的顶点入队
	for (int i = 1; i <= n; i++) {
		if (count[i] == 0) q[++tt] = i;
	}
	//
	while (hh <= tt) {
		int t = q[hh++];  //队头取出顶点
		//遍历所有与t邻接的顶点
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];  //与t邻接的顶点j的入度都-1
			count[j]--;  
			if (count[j] == 0) q[++tt] = j;  //若入度为0，则入队
		}
	}
	//若队尾tt=n-1，则证明n个顶点全部遍历
	if (tt == n - 1) {
		//此时队列内存储的便是拓扑序列
		for (int i = 0; i < n; i++) cout << q[i] << " ";
	}
	//否则，未全部遍历，存在回路
	else cout << "There is a cycle in network!" << endl;
}

《数据结构》刘大友||第6章 图||6.4拓扑排序