Topological Sort

BFS with indegrees

思路如下：

Map<Node, Integer> indegrees;  // indegrees for each node

// initialize indegrees
for (Node node: nodes) {
  for (Node nextNode: node.neighbors) {
     indegrees[nextNode]++
  }
}

// put nodes with indegrees 0 to queue
Queue<Node> queue
for (Node node: nodes) {
  queue.offer(node) if indegrees[node] == 0
}

// get the order of nodes
List<Node> orderedRes
while (!queue.isEmpty()) {
  Node node = queue.poll();
  orderedRes.add(node);
  for (Node nextNode: node.neighbors) {
    indegrees[nextNode]--;
    queue.offer(nextNode) if indegrees[nextNode] == 0;
  }
}

// can complete, if orderedRes.size() == nodes.count

RunTime: O(n + v)
Space: O(n)

For Course Schedule, orderedRes 可以为判断是否能完成所有课程，以及完成课程的顺序。BFS 还可以判断需要多少个 semester 来完成所有课程。

DFS

boolean hasNoCycle(Node node) {
  return true if node is visited
  return false if node is visiting

  mark node as visiting
  for (nextNode in node.neighbors) {
    if (!hasNoCycle(nextNode)) {
      return false;
    }
  }
  mark node as NOT visiting
  mark node as visited
  orderedRes.add(node);

  return true
}

RunTime: O(n + v)
Space: O(n)