Topological Sorting

Tue, May 4, 2021 2-minute read

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

step1: whether it is a Directed Acyclic Graphpic

step1.1: build graphic

List<Integer> buildGraph(int num, int[][] prerequisites) {
  // the number of nodes. numCourses = 2, prerequisites = [[1,0],[0,1]]
  List<Integer>[] graph = new LinkedList[num];
  for (int i = 0; i < num; i++) {
    graph[i] = new LinkedList<>(); // graph[0], graph[1]
  }

  // build edge
  for (int[] edge : preprequisites) {
       // edge = [1,0], edge = [0,1]
       int from = edge[1]; // edge[1] = 0, egde[1] = 1;
       int to = edge[0]; //edge[0] = 1, edge[0] = 0;
       graph[from].add(to); // graph[0].add(1); //graph[0] = [1, 0]; graph[1] = [1, 0];
  }
  return graph;
}

step1.2: DFS to traverse

boolean[] visited;

boolean canFinish(int num, int[][] prerequisites) {

  // the number of nodes. numCourses = 2, prerequisites = [[1,0],[0,1]]
  List<Integer>[] graph = buildGraph(num, prerequisites);

  visited = new boolean[num];
  
  for (int i = 0; i < num; i++) {
    traverse(graph, i); // graph[0], graph[1]
  }
}

void traverse(List<Integer>[] graph, int s) {
  if (visited[s]) {
    return;
  }

  visited[s] = true;
  for (int t : graph[s]) {
    traberse(graph, t);
  }
}

step1.3: record the traverse path

boolean[] onPath;

boolean hasCycle = false;
boolean[] visited;

void traverse(List<Integer>[] graph, int s) {
  if (onPath(s)) {
    hasCycle = true;
  }

  if (visited[s]) {
    return;
  }

  visited[s] = true;
  onPath[s] = true;

  for (int t : graph[s]) {
    traberse(graph, t);
  }
  onPath[s] = false;
}