拓扑排序【学习算法】

前言

2023-9-24 15:32:23

以下内容源自《【学习算法】》
仅供学习交流使用

版权

禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://blog.csdn.net/qq_51625007
禁止其他平台发布时删除以上此话

推荐

无

拓扑排序

核心思想

就是先找到入度为0的结点

删除它发出的边

继续找入度为0的结点

直到找不到为止

判断剩下有没有结点

207. 课程表

207. 课程表

解法一

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n=numCourses;
        HashMap<Integer,ArrayList<Integer>> map=new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(i,new ArrayList<>());
        }

        for(int[] course:prerequisites){
            map.get(course[0]).add(course[1]);
        }

        return topo(map,n);

        
    }


    public boolean topo(HashMap<Integer,ArrayList<Integer>> map,int n){
        int count=0;
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < n; i++) {
            //找到入度为0的点
            if (map.get(i).size()==0){
                stack.add(i);
            }
        }
        while (!stack.isEmpty()) {
            Integer i=stack.pop();
            for (int j = 0; j < map.size(); j++) {
                if (map.get(j).contains(i)){
                    map.get(j).remove(i);
                    if (map.get(j).size()==0){
                        stack.add(j);
                    }
                }
            }
            count++;

        }
        return count == n;
    }    
}
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

解法二

一个入度矩阵 indeg

一个访问变量 visited

class Solution {
    List<List<Integer>> edges;//有向图
    int [] indeg;//入度
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges=new ArrayList<List<Integer>>();
        for(int i=0;i<numCourses;i++){
            edges.add(new ArrayList<Integer>());
        }
        indeg=new int[numCourses];
        for(int[] info:prerequisites){
            edges.get(info[1]).add(info[0]);
            indeg[info[0]]++;
        }

        //拓扑排序
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i=0;i<numCourses;i++){
            if(indeg[i]==0){
                queue.offer(i);
            }
        }
        //广度优先搜索
        int visited=0;
        while(!queue.isEmpty()){
            visited++;
            int u=queue.poll();
            for(int v:edges.get(u)){
                indeg[v]--;
                if(indeg[v]==0){
                    queue.offer(v);
                }
            }
        }

        return visited==numCourses;

    }

}
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

最后

2023-9-24 15:45:02

我们都有光明的未来

祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦