拓撲排序(課程順序113)

拓撲排序

1. 拓撲排序的定義

拓撲排序：無環，含有依賴的有向圖

算法實作：

    1. 統計每個點的入度，以及所有的連邊

    2. 将入度為0的點放入隊列

    3.從隊列中取出一個點，将其連邊的入度-1

    4. 一旦有新的入度為0的點，放入隊列中，重複3-4

則隊列出隊的順序就是拓撲排序。

2. 案例

題目：課程順序

現在總共有 numCourses 門課需要選，記為 0 到 numCourses-1。

給定一個數組 prerequisites ，它的每一個元素 prerequisites[i] 表示兩門課程之間的先修順序。 例如 prerequisites[i] = [ai, bi] 表示想要學習課程 ai ，需要先完成課程 bi 。

請根據給出一個可行的修課序列。

輸入: numCourses = 2, prerequisites = [[1,0]] 
輸出: [0,1]
解釋: 總共有 2 門課程。要學習課程 1，你需要先完成課程 0。是以，正确的課程順序為 [0,1]            

題解

    求拓撲排序的結構，拓撲排序的模闆如下：

class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            Queue<Integer> queue = new ArrayDeque<>();
            Map<Integer, List<Integer>> map = new HashMap<>();
            int book[] = new int[numCourses], index = 0, res[] = new int[numCourses];

            for (int i = 0; i < prerequisites.length; i++) {
                int later = prerequisites[i][1];
                int first = prerequisites[i][0];

                book[first]++;
                map.putIfAbsent(later, new ArrayList<>());
                map.get(later).add(first);
            }

            for (int i = 0; i < numCourses; i++) {
                if (book[i] == 0) {
                    queue.add(i);
                }
            }

            while (!queue.isEmpty()) {
                int temp = queue.poll();
                res[index++] = temp;

                if (map.get(temp) != null) {
                    for (int num : map.get(temp)) {
                        book[num]--;
                        if (book[num] == 0) queue.add(num);
                    }
                }
            }

            return index==numCourses?res:new int[0];
        }
    }