一、拓扑排序的概念

对于一个有向无环图 $G(V,E)$ 来说，其拓扑排序是$G$中所有节点的一种线性次序，该次序满足如下条件：如果图G包含边$(u,v)$，则节点$u$在拓扑排序中处于节点$v$的前面。显然，如果图$G$包含环路，则不可能排出一个线性次序。

我们可以将图的拓扑排序看做是将图中的所有节点在同一水平线上排开，图的所有有向边都从左边指向右边，因此，图的拓扑排序与冒泡排序、堆排序等通常意义上的“排序”是不同的。

接下来代码的实现中，假定采用邻接表的方式存储图。拓扑排序的实现依赖于图的深度优先搜索和广度优先搜索算法，对这两种搜索算法的实现和性质的详细介绍可以参考图的基本算法(一) 图的广度优先搜索和深度优先搜索。

在学习完拓扑排序后，可以尝试完成Leetcode上一道经典的拓扑排序问题：课程表

二、深度优先搜索实现拓扑排序

2.1 算法基本思想与正确性

在介绍深度优先搜索时，我们发现DFS具有如下性质：

1. 对于一个节点$u$，如果它的所有相邻节点$v$都已经搜索完成，那么在搜索回溯到$u$的时候，本身也会变成一个已经搜索完成的节点。这里的「相邻节点」指的是从$u$出发通过一条有向边可以到达的所有节点。

2. 对于一个有向图$G=(V,E)$是无环的当且仅当对其进行深度优先搜索不产生后向边。

我们对深度优先搜索过程作用的节点进行标记，按照是否被搜索可以分为三个状态：

$\cdot$「未搜索」：我们还没有搜索到这个节点，用0表示，标记为白色；

$\cdot$「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成，用1表示，标记为灰色；

$\cdot$「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求，用2表示，标记为绿色。

如果我们将已经完成搜索的节点按照搜索完成时间放入一个栈中，栈中的栈顶节点$u$一定有：栈内其他所有节点都在节点$u$之前完成搜索，并且节点$u$的相邻节点都在栈中。即：

​ 对于一对节点对$u,v\in G.V$,如果图$G$包含一条从节点$u$到节点$v$的边$(u,v)$，那么节点$v$一定先于节点$u$完成搜索。

证明如下：如下图，考虑算法DFS(G)所探索的任意一条边，当这条边被探索时，节点$v$的状态不可能是灰色，因为如果那样的话，节点$v$将会成为节点$u$的祖先，这样$(u,v)$将会成为一条后向边。因此，节点$v$只有可能是白色或绿色(即未被搜索或者已经完成搜索)。当节点$v$未被搜索，其为白色，是节点$u$的后代，因此节点$v$更早完成搜索；如果节点$v$已经完成搜索，其为绿色，即节点$v$更早完成搜索。综上，对于任意一条边$(u,v)$，节点$v$一定先于$u$节点完成搜索。

于是我们可以得到：当所有节点都被放入栈中时，按照从栈顶到栈底的顺序，就可以得到图$G=(V,E)$的拓扑序列。

特别的，若某次访问节点的邻接点时，其状态为搜索中，那么说明图G是一个有环图，无法进行拓扑排序。

2.2 算法执行过程与具体代码

通过DFS实现拓扑排序的过程如下：

1. 初始化设置所有节点的状态为「未搜索」。

2. 对每个节点执行DFS操作，当某个节点完成了搜索，处于「已完成」状态，放入栈中

3. 当所有节点都完成了搜索，按照从栈顶到栈底的顺序即可得到图G的拓扑序列。

具体代码如下：

​// 判断有向图中是否有环
bool valid;
// 栈
int* stack;
int top;

void dfs(ALGraph G, int* visited, int u) {
	// 设置当前节点状态为访问中(1)
	visited[u] = 1;
	// 访问节点u的所有临节点v
	EdgeNode* e = G.vertices[u].firstEdge;
	while (e) {
		int v = e->adjvex;
		if (!visited[v]) 
			dfs(G, visited, v);
		// 如果节点v的状态为搜索中(1),则有向图有环
		else if (visited[v] == 1) {
			valid = false;
			return;
		}
		e = e->next;
	}

	// 设置当前节点状态为已访问(2)并入栈
	visited[u] = 2;
	stack[top++] = u;
}

void TopologicalSort(ALGraph G) {
	// 设置每个顶点的状态为未搜索(0)
	int* visited = calloc(G.vertexNum, sizeof(int));
	stack = malloc(sizeof(int) * G.vertexNum);
	valid = true;
	for (int i = 0; i < G.vertexNum; i++) {
		if (!valid)   break;
		if (!visited[i]) {
			dfs(G, visited, i);
		}
	}
	if (!valid)
		printf("There are loops in Graph\n");
	while (top) 
		printf("%d ", stack[--top]);
}

2.3 算法复杂度分析

时间复杂度：$O(|V|+|E|)$，这就是对图进行深度优先搜索，访问所有节点的时间消耗。

空间复杂度：$O(|V|)$，深度优先搜索最多需要$O(|V|)$的栈空间，并且需要若干个大小为$O(|V|)$的空间来存储拓扑序列、各个节点的状态。

三、广度优先搜索实现拓扑排序

3.1 算法基本思想与正确性

我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，即入度为0。当将一个节点加入答案后，我们就可以移除该节点的所有出边，若该节点的某个邻接$v$点在移除出边后入度减少为0，就可以认为它可以作为满足当前拓扑序列的一个节点。按照这样的流程，我们不断地将入度为0的节点加入答案，直到答案包含所有的节点或者不存在入度为0的节点。上面的想法类似于广度优先搜索。

我们使用一个队列来进行广度优先搜索，开始时，将所有入度为0的节点都放入队列中，它们可以认为是拓扑排序中最前面的节点，并且它们的相对顺序并不影响答案。然后按照上面的思想进行广度优先搜索，将入度为0的节点入队，每次都出队一个入度为0的节点，并且删除该节点的全部出边，直到队列为空，那么出队序列就是图$G$的拓扑序列，该算法的成立依赖于BFS作用在图$G$上的以下性质：

图$G$中所有的节点都会入队并且出队当且仅当图 $G$ 是一个无环图。

证明过程如下：一方面假设某个顶点$v_0$没有入队和出队，那么有指向$v_0$的边，使得$v_0$的入度不为0，这说明至少有一条边$(v_1,v_0)$始终没有被删除，那么说明节点$v_1$没有被删除，那么可以得到至少有一条指向它的边$(v_2,v_1)$没有被删除。一直重复以上过程，我们可以一条无限长的路径$(\cdots \to v_2\to v_1\to v_0)$，由于图的顶点个数是有限的，因此路径内一定存在某段$(v_i\to \cdots \to v_j)$，其中$v_i=v_j$，即图中含有一个环。

对于无向图 $G=(V,E)$ 中的任意一条边$(u,v)$,节点 $u$ 一定先于节点 $v$ 入队和出队。

证明过程如下：根据节点的入队规则，节点$v$只有在入度为0时才会入队，而当节点$u$也存在时，边$(u,v)$并未被“删除”，于是节点$v$的入度一定不为0，因此，只有在边$(u,v)$被删除的前提下，节点$v$才有可能入队，而此时节点$u$已经入队。

3.2 算法执行过程与具体代码

通过BFS实现拓扑排序的过程如下：

1. 首先初始化一个队列$Q$，然后计算每个节点的入度，将所有入度为0的节点放入队列$Q$中
2. 开始执行BFS，对于BFS中的每一步，我们取出队首的节点$u$：将$u$放入答案；移除$u$的所有出边，即将$u$的所有相邻节点的入度减少1，如果某个相邻节点$v$的入度变为0，就将$v$放入队列$Q$中。
3. 当BFS结束后，如果答案中包含了$|V|$个节点，那么我们得到了图$G$的拓扑排序，否则说明图中存在环，不存在拓扑排序。
   
   具体代码如下：

void TopologicalSort_BFS(ALGraph G) {
	Queue q;
	QueueInit(&q);
	int* indegree = calloc(G.vertexNum, sizeof(int));
	int* ans = malloc(sizeof(int) * G.vertexNum);
	int ansSize = 0;
	// 计算每个节点的入度
	for (int i = 0; i < G.vertexNum; i++) {
		EdgeNode* e = G.vertices[i].firstEdge;
		while (e) {
			int v = e->adjvex;
			indegree[v]++;
			e = e->next;
		}
	}
	// 将入度为0的节点放入队列Q中
	for (int i = 0; i < G.vertexNum; i++) {
		if (!indegree[i])
			QueuePush(&q, i);
	}
	while (!QueueEmpty(&q)) {
		// 从队首取出一个顶点放入答案
		int u = QueueFront(&q);
		QueuePop(&q);
		ans[ansSize++] = u;
		// 将节点u的出边删除，修改相邻节点的入度
		EdgeNode* e = G.vertices[u].firstEdge;
		while (e) {
			int v = e->adjvex;
			// 将入度为0的节点放入队列Q中
			if (--indegree[v] == 0)
				QueuePush(&q, v);
			e = e->next;
		}

	}
	// 图中有环
	if(ansSize != G.vertexNum)
		printf("There are loops in Graph\n");;
	for (int i = 0; i < ansSize; i++)   printf("%d ", ans[i]);
	printf("\n");
}

3.3 算法复杂度分析

时间复杂度：$O(|V|+|E|)$，其中，初始化计算每个节点的入度时需要扫描每个顶点和每条边，消耗为$O(|V|+|E|)$，接下来处理队列中的每个顶点，“删除”它的所有出边，删除边(修改相邻节点入度)的操作最多总共执行$O(|E|)$次，入队和出队操作最多总共执行$O(|V|)$次。
空间复杂度：$O(|V|)$，需要$O(|V|)$的空间来存储每个节点的入度以及答案，队列的大小需要为$O(|V|)$。