【每日算法Day 49】拓扑排序

拓扑排序的经典题目-选课

# LeetCode 207. 课程表 (opens new window)

# 题目描述

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

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

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

# 示例

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

示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

1
2
3
4
5
6
7
8
9

# 解题思路

该问题其实就是在判断选课关系构成的图是否是一个有向无环图（DAG），那么我们首先要根据输入的每一条有向边构建图的邻接表。接下来可以选择用BFS或DFS进行拓扑排序。

BFS：构建入度统计表。使用一个队列来进行拓扑遍历，首先将所有入度为0的点入队列。接下来将这些点出队列表示已经遍历完毕，总计数numCourses减一表示删去了一个点，同时将该点所有的邻接点入度减一，如果有入度变为0的则入队列。就这样，如果图中没有环则所有节点入度最终都会变成0，节点都会从图中删去。否则一定有节点入度始终不为0，队列为空时图中的点没有删干净。

public boolean canFinish(int numCourses, int[][] prerequisites) {
    //邻接表
    List<Integer>[] adjacency = new List[numCourses];
    //入度统计表
    int[] inDegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
        adjacency[i] = new ArrayList<>();
    }
    for (int[] pre : prerequisites) {
        adjacency[pre[1]].add(pre[0]);
        inDegree[pre[0]]++;
    }

    //BFS用到的队列
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    //BFS拓扑排序
    while (!queue.isEmpty()) {
        //"删除"入度为0的点temp
        int temp = queue.poll();
        numCourses--;
        for (int i : adjacency[temp]) {
            //temp的邻接点如果入度-1后为0则放入队列中
            if (--inDegree[i] == 0)
                queue.offer(i);
        }
    }
    //如果存在环则一定有节点的入度始终不为0，则删不完图中节点
    return numCourses == 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

DFS：构建访问状态表，默认0表示未访问过，1表示当前路径访问过，-1表示其他路径中访问过。使用回溯思想查找在一条DFS路径中是否存在已经访问过的节点。不过上面的BFS队列的输出是拓扑排序的结果，而这里的DFS就不能用作拓扑排序了，仅能用于确认是否为DAG（如果需要进行拓扑排序需要使用一个成员变量栈）。

public boolean canFinish(int numCourses, int[][] prerequisites) {
    //邻接表
    List<Integer>[] adjacency = new List[numCourses];

    for (int i = 0; i < numCourses; i++) {
        adjacency[i] = new ArrayList<>();
    }
    for (int[] pre : prerequisites) {
        adjacency[pre[1]].add(pre[0]);
    }

    //访问状态表
    int[] status = new int[numCourses];
    //不需要刻意从入度为0的点开始DFS因为访问过就会标记为-1，而遇到-1就会直接返回
    for (int i = 0; i < numCourses; i++) {
        if (!dfs(status,adjacency,i)) return false;
    }
    return true;
}

private boolean dfs(int[] status, List<Integer>[] adjacency, int currentVisit) {
    //回溯终止条件
    if (status[currentVisit]==-1) return true;
    if (status[currentVisit]==1) return false;
    
    //做选择
    status[currentVisit]=1;
    for (int neighbour : adjacency[currentVisit]) {
        if (!dfs(status,adjacency,neighbour)) return false;
    }
    //撤销选择
    status[currentVisit] = -1;
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# LeetCode 210. 课程表 II (opens new window)

# 题目描述

在上一题的基础上，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

# 示例

输入: 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
3
4

# 解题思路

在上一题BFS方法的基础上，用一个数组按顺序保存出队列时的值就可以了，没有环则返回数组。

public int[] findOrder(int numCourses, int[][] prerequisites) {
    //邻接表
    List<Integer>[] adjacency = new List[numCourses];
    //入度统计表
    int[] inDegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
        adjacency[i] = new ArrayList<>();
    }
    for (int[] pre : prerequisites) {
        adjacency[pre[1]].add(pre[0]);
        inDegree[pre[0]]++;
    }

    //BFS用到的队列
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    /*
        用数组按出队列顺序保存元素
        */
    int[] result=new int[numCourses];
    int index=0;
    //BFS拓扑排序
    while (!queue.isEmpty()) {
        //"删除"入度为0的点temp
        int temp = queue.poll();
        result[index++]=temp;
        numCourses--;
        for (int i : adjacency[temp]) {
            //temp的邻接点如果入度-1后为0则放入队列中
            if (--inDegree[i] == 0)
                queue.offer(i);
        }
    }
    //如果存在环则一定有节点的入度始终不为0
    return numCourses == 0 ? result : new int[0];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

如果使用DFS，需要结合一个栈来保存回溯时的节点：

class Solution {
    /*
     * 用栈在回溯时保存访问过的节点，最终出栈的顺序也是拓扑排序
     */
    Deque<Integer> stack = new ArrayDeque<>();

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //邻接表
        List<Integer>[] adjacency = new List[numCourses];

        for (int i = 0; i < numCourses; i++) {
            adjacency[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) {
            adjacency[pre[1]].add(pre[0]);
        }

        //访问状态表
        int[] status = new int[numCourses];
        //不需要刻意从入度为0的点开始DFS因为访问过就会标记为-1，而遇到-1就会直接返回
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(status,adjacency,i)) return new int[0];
        }

        //将栈输出到结果
        int[] result = new int[numCourses];
        for(int i=0;i<numCourses;i++){
            result[i]=stack.pop();
        }
        return result;
    }

    private boolean dfs(int[] status, List<Integer>[] adjacency, int currentVisit) {
        //回溯终止条件
        if (status[currentVisit]==-1) return true;
        if (status[currentVisit]==1) return false;

        //做选择
        status[currentVisit]=1;
        for (int neighbour : adjacency[currentVisit]) {
            if (!dfs(status,adjacency,neighbour)) return false;
        }
        //撤销选择
        status[currentVisit] = -1;
        //回溯前入栈
        stack.push(currentVisit);
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

Wallace's Blog

Choose mode