图

课程表 leetcode

题目描述

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

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

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

思路

判断是否能完成课程的关键在于，是否存在课程b即为课程a的进阶课程，又是课程a的先修课程。也就是判断图中是否存在环。如果存在环，则课程无法完成。

拓扑排序：拓扑排序是一种用于处理有向图（Directed Graph）的算法，目的是找到一个顶点的合理的顺序，使得每个顶点都位于其前面的顶点的后面。

 1  public class 课程表 {
 2      List<List<Integer>> edges;
 3      int[] visited;
 4      boolean valid = true;
 5
 6      public boolean canFinish(int numCourses, int[][] prerequisites) {
 7          edges = new ArrayList<List<Integer>>();
 8          for (int i = 0; i < numCourses; i++) {
 9              edges.add(new ArrayList<Integer>());
10          }
11          visited = new int[numCourses];
12          for (int[] info : prerequisites) {
13              edges.get(info[1]).add(info[0]); // v 能到达的 u 节点列表 v -> u
14          }
15          for (int i = 0; i < numCourses && valid; i++) {
16              if (visited[i] == 0) { // 还没有搜索过
17                  dfs(i);
18              }
19          }
20          return valid;
21      }
22
23      public void dfs(int u) {
24          visited[u] = 1; // 状态为搜索中
25          for (int v : edges.get(u)) {
26              if (visited[v] == 0) { // 未搜索节点
27                  dfs(v); // 深度搜索
28                  if (!valid) {
29                      return;
30                  }
31              } else if (visited[v] == 1) {
32                  valid = false;
33                  return;
34              }
35          }
36          visited[u] = 2; // 节点搜索过并且回溯过
37      }
38
39      @Test
40      public void test() {
41          int numCourses = 2;
42          // int[][] prerequisites = { { 1, 0 }, { 0, 1 } };
43          // int[][] prerequisites = { { 1, 0 } };
44          int[][] prerequisites = { { 0, 1 } };
45
46          boolean ans = canFinish(numCourses, prerequisites);
47          System.out.println(ans);
48      }
49  }