图算法(三)-拓扑排序

本文主要是介绍图算法(三)-拓扑排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[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: numCourses = 2, prerequisites = [[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. 

Constraints:

• 1 <= numCourses <= 105
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

bfs 

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //1.build graph
        //2.build dgree
        Map<Integer,List<Integer>> map = new HashMap();
        int[] degree = new int[numCourses];
        for(int[] pair:prerequisites){
            List<Integer> list = map.getOrDefault(pair[1],new ArrayList());
            list.add(pair[0]);
            map.put(pair[1],list);
            degree[pair[0]]++;
        }
        //3.find the entry(degree==0)
        Queue<Integer> queue = new LinkedList();
        for(int i=0;i<numCourses;i++) if(degree[i]==0) queue.offer(i);
        //4.toplogical
        int count=0;
        while(!queue.isEmpty()){
            int curr = queue.poll();
            count++;
            for(int other:map.getOrDefault(curr,Arrays.asList())){
                if(--degree[other] == 0) queue.offer(other);//入度为0的时候进queue
            }
        }
        return count==numCourses;
    }
}

dfs

这篇关于图算法(三)-拓扑排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！