課程表

你這個(gè)學(xué)期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。

在選修某些課程之前需要一些先修課程。 先修課程按數(shù)組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學(xué)習(xí)課程 ai 則 必須 先學(xué)習(xí)課程 bi 。

• 例如，先修課程對 [0, 1] 表示：想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 。
  請你判斷是否可能完成所有課程的學(xué)習(xí)？如果可以，返回 true ；否則，返回 false 。

示例1：

輸入： numCourses = 2, prerequisites = [[1,0]]
輸出： true
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0 。這是可能的。

解題思路

• 這個(gè)問題可以轉(zhuǎn)化為判斷有向圖中是否存在環(huán)的問題，如果存在環(huán)，
  則說明存在課程之間的循環(huán)依賴，無法完成所有課程的學(xué)習(xí)；
  如果不存在環(huán)，則說明不存在循環(huán)依賴，可以完成所有課程的學(xué)習(xí)。

• 1、使用拓?fù)渑判騺砼袛嗍欠翊嬖诃h(huán)，即是否可以完成所有課程的學(xué)習(xí)。

• 2、使用鄰接表來表示課程之間的先修關(guān)系。

• 3、統(tǒng)計(jì)每門課程的入度，入度為0表示沒有先修課程。

• 4、將入度為0的課程加入隊(duì)列，并從隊(duì)列中依次彈出課程，將其后繼課程的入度減1。

• 5、如果存在環(huán)，即存在入度為0的課程無法全部彈出，則說明無法完成所有課程的學(xué)習(xí)，返回false；否則返回true。

Java實(shí)現(xiàn)

廣度優(yōu)先搜索（BFS）實(shí)現(xiàn)

public class CourseSchedule {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 構(gòu)建有向圖和入度數(shù)組
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] indegree = new int[numCourses];
        for (int[] prereq : prerequisites) {
            int course = prereq[0];
            int prereqCourse = prereq[1];
            graph.putIfAbsent(prereqCourse, new ArrayList<>());
            graph.get(prereqCourse).add(course);
            indegree[course]++;
        }
        
        // 將入度為 0 的節(jié)點(diǎn)加入隊(duì)列中
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // 使用廣度優(yōu)先搜索進(jìn)行拓?fù)渑判?/span>
        int visited = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            visited++;
            List<Integer> neighbors = graph.getOrDefault(course, new ArrayList<>());
            for (int neighbor : neighbors) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return visited == numCourses;
    }

    public static void main(String[] args) {
        CourseSchedule scheduler = new CourseSchedule();
        int numCourses = 4;
//        int[][] prerequisites = {{1, 0}, {2, 1}, {3, 2}, {3, 1}};
        int[][] prerequisites = {{1, 0}, {2, 1}, {3, 2}, {1, 3}};
        System.out.println(scheduler.canFinish(numCourses, prerequisites));
    }
}

時(shí)間空間復(fù)雜度

• 時(shí)間復(fù)雜度：O(V + E)，其中 V 表示課程數(shù)量，E 表示先修課程的數(shù)量，因?yàn)樾枰獦?gòu)建鄰接表和統(tǒng)計(jì)入度，以及進(jìn)行BFS拓?fù)渑判颉?mark hidden color="red">文章來源：http://www.zghlxwxcb.cn/news/detail-851570.html

• 空間復(fù)雜度：O(V + E)，其中 V 表示課程數(shù)量，E 表示先修課程的數(shù)量，因?yàn)樾枰鎯?chǔ)鄰接表和入度數(shù)組。文章來源地址http://www.zghlxwxcb.cn/news/detail-851570.html

到了這里，關(guān)于【圖論】Leetcode 207. 課程表【中等】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！