拓扑排序

算法思路：

对于拓扑排序来说， 我们的中心思想是要我们可以找到一个顺序，每一次我们可以进行的工序是现在没有先序依赖的工序，
按照这个顺序可以流畅的完成我们的任务。
思路基于BFS的队列实现。区别在于统计每个节点的入度数。此法也可用于无向图。

1. 根据边统计每个节点的入度数记入in[i]，其他节点（含无边节点）入度数为0
2. 找出度数为0的节点加入到Queue
3. 取出队首节点，把此节点邻接的节点度数减1，如果度数为0，加入到队列，循环直到队列为空
4. 如果队列为空但仍有节点度数不为0，存在循环，否则不存在

应用：

1. 求最长或最短路径(Leetcode 310)
2. 判断拓扑顺序(Leetcode外星人字典)
3. 判断循环(Python代码返回None)

注意事项：

1. graph要含所有节点，包括没有边的节点。否则结果会有遗漏
2. in_degree初始化要对所有节点赋0
3. 第四步判断是否含循环必不可少，要根据题目要求来处理。除非L310 min height明确一定有解，而L269外星人字典就明确可能无解

Python代码：

def topological_sort(self, graph: List[List[int]], n: int) -> List[int]:
	in_degree = [0] * n
	for i in range(len(graph)):
		for j in range(len(graph[i])):
			in_degree[graph[i][j]] += 1

	start_nodes = [i for i in range(len(in_degree)) if in_degree[i] == 0]
	queue, res = deque(start_nodes), []

	while queue:
		root = queue.popleft()
		res.append(root)
		for i in graph[root]:
			in_degree[i] -= 1
			if in_degree[i] == 0:
				queue.append(i)
	return res if len(res) == n else None

Java代码：

/*
 * graph: 邻接表
 * num: 节点个数 
 */
public void topologicalSort(ArrayList<ArrayList<Integer>> graph, int num) {
	int[] inDegree = new int[num];
	//populate inDegree
	for(ArrayList<Integer> adjacencyList : graph){
		for(Integer node : adjacencyList){
			inDegree[node]++;
		}       	
	}
	Queue<Integer> q = new LinkedList<Integer>();
	for(int i=0;i<inDegree.length;i++){
		if(inDegree[i]==0)
			q.offer(i);
	}
	int count = 0;
	while(!q.isEmpty()){
		Integer v = q.poll();
		count++;
		System.out.print(v + "->");
		for(int neighbor : graph.get(v)){
			if(--inDegree[neighbor]==0)
				q.offer(neighbor);
		}
	}
	/* check isCyclic  or not
	return count == num;;
	*/
}

算法分析：

时间复杂度为O(n)，w为树的所有层里面的最大长度，空间复杂度O(w)。