刷题笔记25——图论课程表

为了最终理解你所不理解的，你必须经历一条愚昧无知的道路。为了占有你从未占有的东西，你必须经历被剥夺的道路。为了达到你现在所不在的名位,你必须经历那条你不在其中的道路。——艾略特

797. 所有可能的路径（已经告知：是有向无环图，所以不需要设置visited）

• 非常奇妙，我最初的错误是如下，在找到目标节点后直接加入到res中，但是发现结果输出的数量是对的，但是都是空的
• 可能的原因是：path就算被加入到res中，但是只是加入了地址，后序path的修改还是会影响到res
• 修改：在加入 res 的时候新建空间，问题解决

		if(n == sz-1){
            res.add(result);
        }
1
2
3

class Solution {
    List<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<List<Integer>>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        traverse(graph,0);
        return res;
    }

    void traverse(int[][] graph,int n){
        path.add(n);
        int sz = graph.length;
        if(n == sz-1){
            List<Integer> result = new LinkedList<>(path);
            res.add(result);
        }
        else{
            for(int node:graph[n]){
                traverse(graph,node);
            }
        }
        path.remove(path.size()-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 比如我们写代码 import 包也是一个例子，必须合理设计代码目录结构，否则会出现循环依赖，编译器会报错，所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

207. 课程表

• visited是以整个图为维度判断是否重复遍历，onPath是以路径为维度判断是否有环，区别在于后续遍历的处理。两者不能互相替代。
• 目前感觉最大的问题就是对数据类型的定义，像graph要用什么类型来存，以及graph如果是两层的话，那么需要对下一层再进行new
• arraylist和linkedlist都可以用，功能也相近，但是要看具体算法中，是更多索引操作还是增删操作
• 其余的话就都是照抄板子

List<Integer>[] graph = new LinkedList[numCourses];
for(int i=0;i<numCourses;i++){
	graph[i] = new LinkedList<>();
}
1
2
3
4

class Solution {
    boolean[] visited;
    boolean[] path;
    boolean isCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = generateGraph(numCourses,prerequisites);
        visited = new boolean[numCourses];
        path = new boolean[numCourses];
        for(int i=0;i<numCourses;i++){
            traverse(graph,i);   
        }
        return !isCycle;
    }

    void traverse(List<Integer>[] graph,int n){
        if(path[n]){
            isCycle = true;
        }
        if(visited[n]||isCycle){
            return;
        }
        visited[n] = true;
        path[n] = true;
        for(int node:graph[n]){
            traverse(graph,node);
        }
        path[n] = false;
    }

    List<Integer>[] generateGraph(int numCourses, int[][] prerequisites){
        List<Integer>[] graph = new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i] = new LinkedList<>();
        }
        for(int i=0;i<prerequisites.length;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        return graph;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

210. 课程表 II (有点像不明白为什么是在后序遍历那块记录路径，可能就是后序的时候，可以保证每个节点的前导节点已经遍历过了)

class Solution {
    boolean[] visited;
    boolean[] path;
    int[] res;
    boolean isCycle = false;
    int i=0;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = generateGraph(numCourses,prerequisites);
        visited = new boolean[numCourses];
        path = new boolean[numCourses];
        res = new int[numCourses];
        for(int i=0;i<numCourses;i++){
            traverse(graph,i);
        }

        if(!isCycle){
            int[] result = new int[numCourses];
            for(int i=0;i<numCourses;i++){
                result[i] = res[numCourses-i-1];
            }
            return result;
        }else{
            return new int[]{};
        }
        
    }

    void traverse(List<Integer>[] graph,int n){
        if(path[n]){
            isCycle = true;
        }
        if(path[n] || visited[n]){
            return;
        }

        visited[n] = true;
        path[n] = true;
        
        for(int node:graph[n]){
            traverse(graph,node);
        }
        path[n] = false;
        res[i] = n;
        i++;
    }

    List<Integer>[] generateGraph(int numCourses, int[][] prerequisites){
        List<Integer>[] graph = new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i] = new LinkedList();
        }

        for(int i=0;i<prerequisites.length;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        return graph;
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61