提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
图这种数据结构有一些比较特殊的算法，比如二分图判断，有环图无环图的判断，拓扑排序，以及最经典的最小生成树，单源最短路径问题，更难的就是类似网络流这样的问题
一、力扣210. 课程表 II（DFS）
class Solution {
boolean[] onPath;
boolean[] visited;
boolean flag = false;
List<Integer> res = new LinkedList<>();
public int[] findOrder(int numCourses, int[][] prerequisites) {
onPath = new boolean[numCourses];
visited = new boolean[numCourses];
List<Integer>[] graph = builderGraph(numCourses, prerequisites);
for(int i = 0; i < numCourses; i ++){
traverse(graph,i);
}
if(flag){
return new int[]{
};
}
Collections.reverse(res);
return res.stream().mapToInt(Integer::intValue).toArray();
}
public void traverse(List<Integer>[] graph, int s){
if(onPath[s]){
flag = true;
return;
}
if(visited[s] || flag){
return;
}
onPath[s] = true;
visited[s] = true;
for(int a : graph[s]){
traverse(graph, a);
}
res.add(s);
onPath[s] = false;
}
public List<Integer>[] builderGraph(int numCourses, int[][] prerequisites){
List<Integer>[] graph = new LinkedList[numCourses];
for(int i = 0; i < numCourses; i ++){
graph[i] = new LinkedList<>();
}
for(int[] arr: prerequisites){
int to = arr[0];
int from = arr[1];
graph[from].add(to);
}
return graph;
}
}
二、力扣力扣210. 课程表 II（BFS）
class Solution {
int[] degree;
public int[] findOrder(int numCourses, int[][] prerequisites) {
degree = new int[numCourses];
List<Integer>[] graph = builderGraph(numCourses, prerequisites);
Deque<Integer> deq = new LinkedList<>();
int[] res = new int[numCourses];
int count = 0;
for(int i = 0; i < numCourses; i ++){
if(degree[i] == 0){
deq.offerLast(i);
res[count++] = i;
}
}
while(!deq.isEmpty()){
int cur = deq.pollFirst();
for(int a : graph[cur]){
degree[a] --;
if(degree[a] == 0){
res[count++] = a;
deq.offerLast(a);
}
}
}
if(count != numCourses){
return new int[]{
};
}
return res;
}
public List<Integer>[] builderGraph(int numCourses, int[][] prerequisites){
List<Integer>[] graph = new LinkedList[numCourses];
for(int i = 0;i < numCourses; i ++){
graph[i] = new LinkedList<>();
}
for(int[] arr : prerequisites){
int from = arr[1];
int to = arr[0];
graph[from].add(to);
degree[to] ++;
}
return graph;
}
}
