7月22日：课程表

题目如下：

这个题的题目叫做课程表，第一眼看这个题目会以为是数据库相关的题目，但实际上确实一道算法题。刚开始我拿到这道题的时候还是不太理解题意，然后过了几分中没有思路以后就直接打开了题解，看着题解都是直接按照图来解，也就是把这个题归纳成有向图的遍历问题，进而可以用拓扑排序思想来解题，拓扑排序也就是广度优先遍历算法。

下面是它的题解

下面是它的Java实现的拓扑排序代码：

这个代码我也看了好几遍，可是并没有看懂，那是吃完饭之前做的一道题，当时看题解看得不太懂，然后心里就很不舒服，因为这样的题目都看不懂怎么能搞定秋招呢！很不甘心，所以吃饭的时候也一直想着这个题，然后晚上的时候就冷静了下来，不行还是得自个儿写一遍，不就是广度优先遍历算法嘛（bfs），实际上我觉得我广度优先遍历算法还是蛮熟的，由于前段时间参加华为软件精英大赛就是图的深度优先遍历算法（dfs），这种图的遍历算法整整搞了两个月，所以搞来搞去对图也还算熟悉了，然后就一步一步来做。

首先做这类题就得先将问题中课程的先后顺序映射成有向图中的起点与终点。

然后就是得构建图，构建图的方式一般有两种，一种是邻接矩阵，第二种就是邻接表。这道题我采用邻接表来做。

构建邻接表首先得构建顶点集合，构建完顶点集合后统计每个顶点的入度情况，并存入对应的集合数组中。‘

创建邻接表，此处邻接表用一个双层的列表表示。

由于拓扑排序是每次从入度为0的顶点出发开始遍历，所以首先将所有入度为0的点存入队列中，然后再依次出队，出队以后将该点从节点集合中删除并且将所有以该节点为入度的的点的入度减一，并同时判断入度减一后的点的入度是否为0，如果为0则将该节点加入到队列中，一直循环直到队列为空，也就是顶点集合中不存在入度为0的节点了，若此时节点集合中还有节点，则说明该有向图中有环（题意就是无法修满所有课程）。

下面是我自己写的代码：

class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {

//创建顶点数组。

        int[] rudu = new int[numCourses];

//创建邻接表双层列表

        List<List<Integer>> linjie = new ArrayList<>();

//构建一个队列

        Queue<Integer> que = new LinkedList<>();

//按照题目要求构建邻接表

        for(int i=0;i<numCourses;i++){

            linjie.add(new ArrayList<Integer>());

        }

        for(int i=0;i<prerequisites.length;i++){

            linjie.get(prerequisites[i][0]).add(prerequisites[i][1]);

            rudu[prerequisites[i][1]]++;

        }

//将入度为0的顶点加入到队列中

        for(int i=0;i<rudu.length;i++){

            if(rudu[i]==0)

                que.add(i);

        }

//循环找出所有入度为0的顶点

        while(!que.isEmpty()){

            int chu = que.poll();

            numCourses--;

            for(int x:linjie.get(chu)){

                if(--rudu[x]==0) que.add(x);

            }

        }

        return numCourses==0;

    }

}