本文共 2896 字，大约阅读时间需要 9 分钟。

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

输入: 2, [[1,0]]

输出: [0,1]

解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]

输出: [0,1,2,3] or [0,2,1,3]

解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。

因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。

你可以假定输入的先决条件中没有重复的边。

解题思路：

• 每个课程对应图中的一个结点
• 先修要求构成有向边
• 拓扑排序：对于有向图的结点按照访问顺序排序

考点：

• 考点1：能否正确构造图
• 考点2：基于深度优先搜索/广度优先 搜索的拓扑排序

构建图：

解题思路 1：基于广度优先搜索的拓扑排序

package com.lcz.leetcode;// 课程表IIimport java.util.*;public class Leetcode210 {
   	class Solution {
   		//构造图		List
   
    
     > edges;		// 存储入度结点		int[] indeg;		// 存储结果		int[] res;		// 存储结果的索引		int index;			    public int[] findOrder(int numCourses, int[][] prerequisites) {
   	    	// 对上述初始化	    	edges = new ArrayList
     
      
       >();	    	for(int i=0;i
       
        ());	    	}	    	indeg = new int[numCourses];	    	res   = new int[numCourses];	    	index = 0;	    	// 构建图	    	for(int[] info:prerequisites) {
   	    		edges.get(info[1]).add(info[0]);	    		res[info[0]]++;	    	}	    	// 广度优先搜索 队列	    	Queue
        
          queue = new LinkedList
         
          (); // 将入度为0的结点都放入队列中 for(int i=0;i
         
        
       
      
     
    
   

基于深度优先搜索的拓扑排序

class Solution {
       // 存储有向图    List
   
    
     > edges;    // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成    int[] visited;    // 用数组来模拟栈，下标 n-1 为栈底，0 为栈顶    int[] result;    // 判断有向图中是否有环    boolean valid = true;    // 栈下标    int index;    public int[] findOrder(int numCourses, int[][] prerequisites) {
           edges = new ArrayList
     
      
       >();        for (int i = 0; i < numCourses; ++i) {
               edges.add(new ArrayList
       
        ());        }        visited = new int[numCourses];        result = new int[numCourses];        index = numCourses - 1;        for (int[] info : prerequisites) {
               edges.get(info[1]).add(info[0]);        }        // 每次挑选一个「未搜索」的节点，开始进行深度优先搜索        for (int i = 0; i < numCourses && valid; ++i) {
               if (visited[i] == 0) {
                   dfs(i);            }        }        if (!valid) {
               return new int[0];        }        // 如果没有环，那么就有拓扑排序        return result;    }    public void dfs(int u) {
           // 将节点标记为「搜索中」        visited[u] = 1;        // 搜索其相邻节点        // 只要发现有环，立刻停止搜索        for (int v: edges.get(u)) {
               // 如果「未搜索」那么搜索相邻节点            if (visited[v] == 0) {
                   dfs(v);                if (!valid) {
                       return;                }            }            // 如果「搜索中」说明找到了环            else if (visited[v] == 1) {
                   valid = false;                return;            }        }        // 将节点标记为「已完成」        visited[u] = 2;        // 将节点入栈        result[index--] = u;    }}
       
      
     
    
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/110916615 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！