207 Course Schedule

今天朋友问我什么是拓扑排序，我就想把相关的题目做一下做一个简单的总结题解给他。

Topological Sort

• 可以参考专业解释什么是拓扑排序

• 图论算法的一种，通常用于处理互相有依赖的问题。举一个在选课中很常见的例子，就是存在这样的两种课程，一种是基础课，一种是选修课，高级的选修课都会存在需要的先修课，你需要把这些先修课程修完才可以进行学习。这样我们就需要进行拓扑排序。

• 拓扑排序的算法也非常简单，首先我们记录每个节点的出度（m）和入度（n）。出度可以认为是，这一门课是多少门课的先修课，入度可以认为是，修这一门课需要多少门先修课。
• 当这一门课不需要先修课的时候(即n == 0)， 我们可以修这门课程。
• 修完了这门课程之后，我们需要把以这门课程作为先修课程的其他课程需要先修课程的数量进行-1操作。
• 这个时候，如果存在其他的课程，n == 0我们就可以现在去修这些课程了。
• 这样产生的排序，就称之为拓扑排序。
• 不同的语言，实现起来使用的思路是一样的。

Python

class Solution(object):    
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        in_degrees = dict((u, 0) for u in range(numCourses))
        for prerequisite in prerequisites:
            dest = prerequisite[1]
            in_degrees[dest]+=1
        Q = [u for u in range(numCourses) if in_degrees[u] == 0]
        S = []
        while Q:
            u = Q.pop()
            S.append(u)
            for prerequisite in prerequisites:
                if prerequisite[0] == u:
                    in_degrees[prerequisite[1]] -= 1
                    if in_degrees[prerequisite[1]] == 0:
                        Q.append(prerequisite[1])
        return len(S) == numCourses

Java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        for(int[] prereq: prerequisites){
            indegree[prereq[0]] += 1;
        }
        Set<Integer> zeroIndegree = new HashSet();
        for(int i = 0; i < numCourses; i ++){
            if(indegree[i] == 0)
                zeroIndegree.add(i);
        }
        if(zeroIndegree.isEmpty())
            return false;
        while(!zeroIndegree.isEmpty()){
            Iterator<Integer> it = zeroIndegree.iterator();
            int course = it.next();
            zeroIndegree.remove(course);
            for(int[] preq: prerequisites){
                if(preq[1] == course){
                    indegree[preq[0]] -= 1;
                    if(indegree[preq[0]] == 0){
                        zeroIndegree.add(preq[0]);
                    }
                }
            }
        }
        for(int i:indegree){
            if(i!= 0)
                return false;
        }
        return true;
    }
}