【問題描述】[第210 題][課程表 II][中等]

現在你總共有 n 門課需要選，記為 0 到 n-1。在選修某些課程之前需要一些先修課程。 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [0,1]給定課程總量以及它們的先決條件，返回你為了學完所有課程所安排的學習順序。可能會有多個正確的順序，你只要返回一種就可以了。如果不可能完成所有課程，返回一個空數組。輸入: 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. 拓撲排序 BFS+貪心(重點)

// 方法 1 最簡單的 BFSpublic int[] findOrder(int numCourses, int[][] prerequisites) {if (numCourses == 0) return new int[0];int[] inDegrees = new int[numCourses];// 建立入度表for (int[] p : prerequisites) { // 對于有先修課的課程，計算有幾門先修課inDegrees[p[0]]++;}// 入度為0的節點隊列Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < inDegrees.length; i++) {if (inDegrees[i] == 0) queue.offer(i);}int count = 0; // 記錄可以學完的課程數量int[] res = new int[numCourses]; // 可以學完的課程// 根據提供的先修課列表，刪除入度為 0 的節點while (!queue.isEmpty()){int curr = queue.poll();res[count++] = curr; // 將可以學完的課程加入結果當中for (int[] p : prerequisites) {if (p[1] == curr){inDegrees[p[0]]--;if (inDegrees[p[0]] == 0) queue.offer(p[0]);}}}if (count == numCourses) return res;return new int[0];}

2. DFS

遞歸 腦子一定要清醒

時間復雜度：O(N^2) 空間復雜度：O(N)

// 方法 2：鄰接矩陣 + DFS 由于用的數組，每次都要遍歷，效率比較低public int[] findOrder(int numCourses, int[][] prerequisites) {if (numCourses == 0) return new int[0];// 建立鄰接矩陣int[][] graph = new int[numCourses][numCourses];for (int[] p : prerequisites) {graph[p[1]][p[0]] = 1;}// 記錄訪問狀態的數組，訪問過了標記 -1，正在訪問標記 1，還未訪問標記 0int[] status = new int[numCourses];Stack<Integer> stack = new Stack<>(); // 用棧保存訪問序列for (int i = 0; i < numCourses; i++) {if (!dfs(graph, status, i, stack)) return new int[0]; // 只要存在環就返回}int[] res = new int[numCourses];for (int i = 0; i < numCourses; i++) {res[i] = stack.pop();}return res;}private boolean dfs(int[][] graph, int[] status, int i, Stack<Integer> stack) {if (status[i] == 1) return false; // 當前節點在此次 dfs 中正在訪問，說明存在環if (status[i] == -1) return true;status[i] = 1;for (int j = 0; j < graph.length; j++) {// dfs 訪問當前課程的后續課程，看是否存在環if (graph[i][j] == 1 && !dfs(graph, status, j, stack)) return false;}status[i] = -1; // 標記為已訪問stack.push(i);return true;}

【總結】

1.拓撲排序

優化 HASHSET作為鄰接矩陣

// 方法 2 升級版：用 HashSet 作為鄰接矩陣，加速查找速度public int[] findOrder(int numCourses, int[][] prerequisites) {if (numCourses == 0) return new int[0];// HashSet 作為鄰接矩陣HashSet<Integer>[] graph = new HashSet[numCourses];for (int i = 0; i < numCourses; i++) {graph[i] = new HashSet<>();}for (int[] p : prerequisites) {graph[p[1]].add(p[0]);}int[] mark = new int[numCourses]; // 標記數組Stack<Integer> stack = new Stack<>(); // 結果棧for (int i = 0; i < numCourses; i++) {if(!isCycle(graph, mark, i, stack)) return new int[0];}int[] res = new int[numCourses];for (int i = 0; i < numCourses; i++) {res[i] = stack.pop();}return res;}private boolean isCycle(HashSet<Integer>[] graph, int[] mark, int i, Stack<Integer> stack) {if (mark[i] == -1) return true;if (mark[i] == 1) return false;mark[i] = 1;for (int neighbor : graph[i]) {if (!isCycle(graph, mark, neighbor, stack)) return false;}mark[i] = -1;stack.push(i);return true;}

2.有向圖解題思路 拓撲排序（優先） DFS

3. 遙想備戰藍橋杯 只是死記硬背 根本記不住 理解才是王道！

4.相關題目[Leetcode][第207題][JAVA][課程表][拓撲排序][DFS]

轉載鏈接：https://leetcode-cn.com/problems/course-schedule-ii/solution/java-jian-dan-hao-li-jie-de-tuo-bu-pai-xu-by-kelly/
參考鏈接：https://leetcode-cn.com/problems/course-schedule-ii/solution/tuo-bu-pai-xu-shen-du-you-xian-bian-li-python-dai-/

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第210 题][课程表 II][拓扑排序][BFS][DFS][有向图]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。