12.拓扑排序

一.课程表
1.题目描述：
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

2.示例：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的

3.解:
（1）我的答案：
class Solution {
ArrayList<ArrayList<integer>> everyCourseNext;//存放每门课程的后继课程
int[] state;//记录没门课程的状态（未搜索/搜索中/搜索完）
boolean result = true;//判断结果</integer>

public boolean canFinish(int numCourses, int[][] prerequisites) {
    //初始化everyCourseNext
    everyCourseNext = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) everyCourseNext.add(new ArrayList<>());
    for (int[] temp : prerequisites) everyCourseNext.get(temp[1]).add(temp[0]);

    //初始化state
    state = new int[numCourses];

    //回溯操作，深度优先遍历
    for (int i = 0; i < numCourses && result; i++) {
        if (state[i] == 0) recall(i);
    }

    return result;
}

public void recall(int root) {
    state[root] = 1;//搜索中
    for (int temp : everyCourseNext.get(root)) {
        if (state[temp] == 1) {
            result = false;
            return;
        } else if (state[temp] == 0 && result) {
            recall(temp);
        }
    }
    state[root] = 2;//搜索完
}

}

class Solution {
ArrayList<ArrayList<integer>> everyCourseNext;//存放每门课程的后继课程
int[] preNum;//记录每门课程先修课程的个数</integer>

public boolean canFinish(int numCourses, int[][] prerequisites) {
    //初始化everyCourseNext 初始化preNum
    preNum = new int[numCourses];
    everyCourseNext = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) everyCourseNext.add(new ArrayList<>());
    for (int[] temp : prerequisites) {
        everyCourseNext.get(temp[1]).add(temp[0]);
        preNum[temp[0]]++;
    }

    Queue<Integer> noPreCourseTempQueue = new LinkedList<>();//暂存没有前继课程的课程
    Queue<Integer> topologSort = new LinkedList<>();//最终输出的排序


    //找到最初没有任何前继课程的课程，如果没有，则说明不是DAG,无法输出拓扑序列
    for (int i = 0; i < numCourses; i++) {
        if (preNum[i] == 0) noPreCourseTempQueue.offer(i);
    }

    //广度优先搜索
    while (!noPreCourseTempQueue.isEmpty()) {
        for (int temp : everyCourseNext.get(noPreCourseTempQueue.peek())){
            preNum[temp]--;
            if (preNum[temp] == 0) noPreCourseTempQueue.offer(temp);
        }
        topologSort.offer(noPreCourseTempQueue.poll());
    }

    return topologSort.size() == numCourses;
}

}
4.总结
拓扑排序什么时候用呢？答案是用于DAG图。使用深度优先遍历方法有几部分要做的：1.必须构建邻接表，所谓邻接表就是存放每个坐标的后继坐标集合，是一个二维数据结构。2.必须建立指定每个坐标当前状态的数据结构并初始化，状态有三种：未搜索/搜索中/搜索完 3.仍然使用回溯，但是不同的是要在主方法中多次调用回溯方法，因为图相当于多个树，有多个根节点。4.若要输出拓扑排序则还需要建立一个栈结构，存放拓扑排序结果。每搜索完一个坐标就令该坐标入栈。这样得到的栈从栈顶到栈底就是一个拓扑排序。使用广度优先遍历方法有几部分要做的：1.必须建立邻接表。2.必须建立记录每个坐标的前继坐标个数的数据结构并初始化。3.必须建立一个暂存没有前继坐标的坐标的队列。4.建立一个队列存放拓扑排序。只要暂存队列非空，就读取暂存队列的队首中存放的坐标，然后遍历这个坐标的每个后继坐标并斩断每个后继坐标和该坐标之间的连线，然后将这些后继坐标的前继坐标个数减一，再一次判断每个是否没有了前继坐标，若没有了，就加入暂存队列中。最后将暂存队列的队首坐标加入到存放拓扑序列的队列中。如此循环往复，直到暂存队列为空，则拓扑序列也生成了。

二.课程表ii
1.题目描述：
现在你总共有 n 门课需要选，记为 0 到 n-1。

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

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

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

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

3.解:
（1）我的答案：
class Solution {

ArrayList<ArrayList<Integer>> everyCourseNext;//存放每门课程的后继课程
int[] preNum;//记录每门课程先修课程的个数

public int[] findOrder(int numCourses, int[][] prerequisites) {
    //初始化everyCourseNext 初始化preNum
    preNum = new int[numCourses];
    everyCourseNext = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) everyCourseNext.add(new ArrayList<>());
    for (int[] temp : prerequisites) {
        everyCourseNext.get(temp[1]).add(temp[0]);
        preNum[temp[0]]++;
    }

    Queue<Integer> noPreCourseTempQueue = new LinkedList<>();//暂存没有前继课程的课程
    Queue<Integer> topologSort = new LinkedList<>();//最终输出的排序


    //找到最初没有任何前继课程的课程，如果没有，则说明不是DAG,无法输出拓扑序列
    for (int i = 0; i < numCourses; i++) {
        if (preNum[i] == 0) noPreCourseTempQueue.offer(i);
    }

    //广度优先搜索
    while (!noPreCourseTempQueue.isEmpty()) {
        for (int temp : everyCourseNext.get(noPreCourseTempQueue.peek())) {
            preNum[temp]--;
            if (preNum[temp] == 0) noPreCourseTempQueue.offer(temp);
        }
        topologSort.offer(noPreCourseTempQueue.poll());
    }


    if (numCourses == topologSort.size()) {
        int[] topologSortResult = new int[numCourses];
        for (int i = 0; i < numCourses; i++) topologSortResult[i] = topologSort.poll();
        return topologSortResult;
    }

    return new int[0];
}

}

4.总结
和上一题一样，只不过把拓扑序排序输出就行。