M
tags: DFS, BFS, Graph, Topological Sort, Backtracking
time: O(n)
space: O(n)
- 一堆课用int[2] pair 来表示. [1, 0] 表示要上课1的话, 必须先把课0上了.
- 每一个数字都是一个ndoe, 题目问是否能把所有的课排了
- input是 numOfCourses, 还有这个prerequisites [[]]
- Concept of Indegree: `# of incoming node that depends on me`. It is a graph of `arrows pointing inward to me` structure.
##### Indegree 原理
- Remember: **indegree是周围的node到我这里的次数count**.
- Note: 如果有cycle, 这个node上面会多一些inDegree, 也就无法清0, 它也无法进入 queue && sorted list.
- 如果周围所有node的连线, 都意义切除后, 我的indegree还不等于0, 那么肯定有某些node间接地有重复连线, 也就是有cycle
- Topological problem: almost always care about cycle case (if detecting cycle is not goal)
#### BFS, Topological Sort
- Two structures:
- 1) build inDegreeEdges: `List[] inDegreeEdges`: list of incoming nodes that depends on `node i`,
- 2) build dependencyCount: `int[] dependencyCount`, count # of braches that curr node depends on
- any dependencyCount[node]==0, means this node is now a leaf, add to queue
- Topological Sort Process, Kahn algorithem:
- topologically process:
1) add leaf node to queue, get ready to process;
2) process leafNode, like cutting of leaf
3) if any child node dependencyCount == 0, it is a leaf node now: add this node to queue.
#### DFS
- this problem aims for deteching cycle, not output final list. Simply: visit all nodes and verify cycle
- Option1: array of indegree lists, List[]
- 用 visited int[] 来确认是否有cycle. 1 means `visited`, -1 means `visted from last dfs level`
- Deteching `-1`: 说明这个node在上一级或者以上的同一个dfs path里面已经走过, 那么证明有cycle, return false.
- dfs on curr node indegree dependencies; if all passes w/o failing, set visited[i] = 1
- Similarly, can use `HashMap> map` to replace List[], but exact same idea.
- Optoin2: use a struct `class Node {Boolean visiting; Map inDegreeMap}` to be more generic
- topo sort may output the sort order: 1) at DFS bottom level, put record to a `stack`, 2) rst.insert(0, curr record)
#### Notes
- 还有 List[] arrayOfList = new ArrayList[]; 这样的操作啊, 代替了map. Though: map may be more flexible
- 是topological sort的题目。一般都是给有dependency的东西排序。
- 最终都会到一个sink/leaf node，no further dependency, 在那个点截止
- 画个图的话, prerequisite都是指向那个sink/leaf node
- when building the inDegreeMap/inDegreeEdge: we use sink/leaf node as key/index, which pionts back to inDegree/parent nodes
- BFS: when all braches/dependency count are reduced to 0, then it is now a leaf node, ready to be used.
- DFS Insert Order: rst.insert(0, node); Assume we want leaf/node at index 0 in final output:
- the very bottom-node **depends on everybody**
- any visited node should be added to 0 index of the list, so it will be at tail later
```
/*
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1,
which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[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: 2, [[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.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
Hints:
1. This problem is equivalent to finding if a cycle exists in a directed graph.
If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera
explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.
*/
/*
Method1: Topological sort, BFS Kahn's algorithem.
- 1) build inDegreeEdges, 2) build dependencyCount
- topologically process: 1) add leaf node to queue, get ready to process; 2) process leafNode, like cutting of leaf
- any dependencyCount[node]==0, means this node is now a leaf, add to queue
*/
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (validateInput(numCourses, prerequisites)) return true;
List[] inDegreeEdges = new List[numCourses];
int[] dependencyCount = new int[numCourses];
// Initialize
for (int i = 0; i < numCourses; i++) inDegreeEdges[i] = new ArrayList<>();
// Build inDegreeEdges, and dependencyCount
for (int[] prerequisite : prerequisites) {
inDegreeEdges[prerequisite[1]].add(prerequisite[0]);
dependencyCount[prerequisite[0]]++;
}
// BFS: 1) add leaf nodes into queue. Get ready to process its incoming edges
Queue queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (dependencyCount[i] == 0) queue.add(i); // leaf node that depends on nobody
}
// 2) process leafNode
int count = 0; // count of leaf node that can eventually can be independent: when all its dependencies are exhausted
while (!queue.isEmpty()) {
count++;
int leafNode = queue.poll();
List dependencies = inDegreeEdges[leafNode];
for (int node : dependencies) {
dependencyCount[node]--; // imaging we are cutting off leafNode, so its parent will decrese the dependency count
if (dependencyCount[node] == 0) queue.add(node); // add to result when any node's dependencies count are exhausted
}
}
// BFS will always end. Validate if # of leaf/independent course equals to total numCourses
// If not equal, then there is cycle edges that cannot be resolved to 0
return count == numCourses;
}
private boolean validateInput(int numCourses, int[][] prerequisites) {
return numCourses == 0 || prerequisites == null || prerequisites.length == 0
|| prerequisites[0] == null || prerequisites[0].length == 0;
}
}
/*
Method2: DFS, Option1, using List[] edges to mark inDegree Structure
Similarly, can use HashMap> map; rather than List[].
DFS. This question only asks about true/false (to detect cycle),
so there is no need to record the actual final list.
We'll simply traverse all of the nodes
If there is a cycle, there must be a node being visited again in one loop:
mark last visited node = -1
mark visited starting node after dfs: node = 1
*/
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses == 0 || prerequisites == null) return true;
List[] edges = buildIndegreeEdges(numCourses, prerequisites);
// DFS serach && marking visited
int[] visited = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if(!dfs(edges, visited, i)) return false;
}
return true;
}
private boolean dfs(List[] edges, int[] visited, int node) {
if (visited[node] == 1) return true;
if (visited[node] == -1) return false; // cyclic
visited[node] = -1;
List childNodes = edges[node];
for (int childNode : childNodes) {
if (!dfs(edges, visited, childNode)) return false;
}
visited[node] = 1;
return true;
}
private List[] buildIndegreeEdges(int numCourses, int[][] prerequisites) {
List[] edges = new ArrayList[numCourses];
// Initialize with empty list of indgree edges
for (int i = 0; i < numCourses; i++) edges[i] = new ArrayList<>();
// Populate graph edges. prerequisite[1]=current node; prerequisite[0] = incoming dependency
for (int[] prerequisite : prerequisites) {
edges[prerequisite[1]].add(prerequisite[0]);
}
return edges;
}
}
// DFS Option2: with `class Node {Boolean visiting; Map inDegreeMap}` to build inDegree structure
class Solution {
class Node {
Boolean visiting = null;
Map inDegreeMap = new HashMap<>();
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses == 0 || prerequisites == null) return true;
Node root = buildIndegreeMap(numCourses, prerequisites);
// DFS serach && marking visited
return dfs(root);
}
private boolean dfs(Node node) {
// if visiting: cyclic, return false; visited but now node.visiting == false, return true;
if (node.visiting != null) return !node.visiting;
node.visiting = true;
for (Node childNode : node.inDegreeMap.values()) {
if (!dfs(childNode)) return false;
}
node.visiting = false;
return true;
}
private Node buildIndegreeMap(int numCourses, int[][] prerequisites) {
Node root = new Node();
// Initialize with empty list of indgree edges
for (int i = 0; i < numCourses; i++) root.inDegreeMap.put(i, new Node());
// Populate graph edges. prerequisite[1]=current node; prerequisite[0] = incoming dependency
Map rootIndegreeMap = root.inDegreeMap;
for (int[] prerequisite : prerequisites) {
Node currNode = rootIndegreeMap.get(prerequisite[1]);
Node dependencyNode = rootIndegreeMap.get(prerequisite[0]);
currNode.inDegreeMap.put(prerequisite[0], dependencyNode);
}
return root;
}
}
```