拓扑排序（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;  //从栈中弹出一个顶点jtop = count[top];cout << j << endl;  //输出该顶点Edge* p = Head.adjacent;  //令p为j的边链表头指针while (p != NULL) {  //从当前的图中删除与j关联的边int k = p->VerAdj;  //k为边终点if (--count[k] == 0) {  //入度-1count[k] = top;  //若入度为0，则k入栈top = k;}p = p->link;}}}delete[] count;
}

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

const int N=100010;
int n; //顶点数
//数组模拟队列和邻接表的拓扑排序
void topsort() {int q[N];  //模拟队列的数组qint hh = 0, tt = -1;  //队头hh，队尾ttint	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的入度都-1count[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拓扑排序