本文共 4703 字，大约阅读时间需要 15 分钟。
对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
只有当一幅有向图是无环图时才能进行拓扑排序。
任务调度、课程安排、继承
共有n门课程你必须参加，标签从0到n-1。
有些课程可能有先决条件，例如，要参加课程0，您必须首先参加课程1，这表示为一对：[0,1]
考虑到课程总数和先决条件对列表，您是否可以完成所有课程？可以返回true，不可以返回false
Input: 2, [[1,0]] Output: trueInput: 2, [[1,0],[0,1]]Output: false
这道不需要使用拓扑排序，只需要检测有向图是否存在环即可，在这里采用DFS，递归来实现
/***采用深度优先遍历解决有无环*如果采用BFS会更快**/class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List [] graphic = new List[numCourses]; boolean [] marked = new boolean[numCourses]; //判断那个数是否被标记 for (int i = 0;i < numCourses;i++){ graphic[i] = new ArrayList(); //对每个数字生成一个链表 } for (int [] pre : prerequisites){ graphic[pre[0]].add(pre[1]); } for (int i = 0;i < numCourses;i++){ if(hasCycle(graphic,marked,i)){ return false; } } return true; } //判断是否含环 private boolean hasCycle(List [] graphic,boolean [] marked,int cur){ if (marked[cur]){ return true; //如果被标记，则直接返回true } marked[cur] = true; for (int next : graphic[cur]){ if (hasCycle(graphic,marked,next)){ return true; } } marked[cur] = false; return false; }} 总共有n门课程你必须参加，标签从0到n-1。
有些课程可能有先决条件，例如，要参加课程0，您必须首先参加课程1，这表示为一对：[0,1]
给定课程总数和先决条件对列表，返回完成所有课程所需的课程顺序。
可能有多个正确的订单，您只需返回其中一个。如果无法完成所有课程，则返回空数组。
Input: 2, [[1,0]] Output: [0,1] Input: 4, [[1,0],[2,0],[3,1],[3,2]]Output: [0,1,2,3] or [0,2,1,3]
这道属于典型拓扑排序，可以考虑用DFS或者BFS来完成，在LeetCode上显示第一种这种解法比第二种更快点。
DFS:使用一个栈存储后序遍历结果，这个栈的逆序结果就是拓扑排序结果，这里有一个globalMarked全局判断，可以减少判断次数。
class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { List [] graphic = new List[numCourses]; for (int i = 0;i < numCourses;i++){ graphic[i] = new ArrayList<>(); } for(int [] a : prerequisites){ graphic[a[0]].add(a[1]); } boolean [] globalMarked = new boolean[numCourses]; //增加一个全局判断，可以减少时间 boolean [] localMarked = new boolean[numCourses]; Stack postOrder = new Stack<>(); //使用栈存储后序遍历结果 for(int i = 0;i < numCourses;i++){ if(hasCycle(globalMarked,localMarked,postOrder,graphic,i)){ return new int[0]; } } int [] order = new int[numCourses]; for(int i = numCourses - 1;i >= 0;i--){ order[i] = postOrder.pop(); //逆序输出 } return order; } //DFS,判断是否有环 private boolean hasCycle(boolean [] globalMarked,boolean [] localMarked,Stack postOrder, List [] graphic,int i ){ if(localMarked[i]){ return true; } if(globalMarked[i]){ return false; //减少判断 } localMarked[i] = true; globalMarked[i] = true; for(int next : graphic[i]){ if(hasCycle(globalMarked,localMarked,postOrder,graphic,next)){ return true; } } localMarked[i] = false; postOrder.add(i); return false; }} BFS：首先遍历图中所有的顶点，将入度为0的顶点入队列，然后将入度为0的顶点出队列，并更新与之邻接的顶点的入度，若邻接顶点的入度降为0，则入队列，最后判断index与numCourses得大小，如果有环，index的值 一定小numCourses。
public int[] findOrder(int numCourses, int[][] prerequisites) { if (numCourses == 0) return null; // 将图形表示从边转换为相邻列表 int indegree[] = new int[numCourses], order[] = new int[numCourses], index = 0; //判断哪些有先决条件得课程 for (int i = 0; i < prerequisites.length; i++) indegree[prerequisites[i][0]]++; Queue queue = new LinkedList (); for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) { // 将课程添加到订单中，因为它没有先决条件，即将入度为0的顶点入队列 order[index++] = i; queue.offer(i); } while (!queue.isEmpty()) { int prerequisite = queue.poll(); //更新与之邻接的顶点的入度 for (int i = 0; i < prerequisites.length; i++) { if (prerequisites[i][1] == prerequisite) { indegree[prerequisites[i][0]]--; if (indegree[prerequisites[i][0]] == 0) { //如果Indegree为零，则将课程添加到order中 order[index++] = prerequisites[i][0]; queue.offer(prerequisites[i][0]); } } } } //如果有环，index的值 一定小于numCourses return (index == numCourses) ? order : new int[0];} 转载地址：http://ierwi.baihongyu.com/