本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：算法从入门到精通
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

算法原理：

本题题意要先搞懂，举个例子：

假设传入的这个数组，以[1,0]来说，它的意思就是要想先修1，就必须先学习0这门课程，依次内推。想这个我们可以画个箭头好理解：0->1 意思就是学1要先学0；

分析到这，我们就可以把这个数组抽象出来：

这个图是不是很熟悉，这不就是我们的有向图吗？

看一下题目问的啥，问能否修完？那这问题的本质不就是给这个图能否拓扑排序，或者问这个图是不是有环.

分析到这，其实就可以动手写代码了，但是我们前言末尾说到过，实现拓扑排序的前提是要建图。我们先打一下理论基础，看如何建图：

首先如何灵活建图的前提我们要合理用我们的容器。
其次要看数据的稠密也就是数据量，我们通常有两种办法：

1. 邻接矩阵
2. 邻接表
   邻接矩阵市面上书籍讲的很多，这里我们采用邻接表的形式。
   什么是邻接表呢？
   
   以刚才例子为例，我们把每个位置相连的点都放在一排，所形成的这个表就是邻接表。

可能有人好奇，那我们岂不是要实现一个链表，才能形成上面的对应关系，其实不然，我们用数组就可以模拟代替链表。

接下来我们可以选择合适的容器，也就是代码如何实现，这里我们给出两种：

1. vector
   我们在vector里嵌套一个vector：

vector<vector<int>> edge;//edge边的意思

为什么二维数组就可以呢？

我们让其下标具有对应关系，咱们得邻接表不就出来了。

2. 哈希表

用哈希表来实现邻接表：

unordered_map<int,vector<int>> edge;
unordered_map<string,vector<string>> edge;

用哈希来反映映射也是可以的。

代码实现：

class Solution 
{
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites) 
    {
        //1.准备工作
        unordered_map<int,vector<int>> edge;//邻接表存图
        //vector<vector<int>> edge(n);
        vector<int> in(n);//用来标记入度

        //2.建图
        for(auto& e:prerequisites)
        {
            int a=e[0],b=e[1];  //b->a的一条边
            //拿到b的这条边
            //把a插入到b的后面
            edge[b].push_back(a);
            //有一条边指向a了，a入度++
            in[a]++;
        }

        //3.拓扑排序
        queue<int> q;
        //(1)把所有入度为0的点加入到队列中
        for(int i=0;i<n;i++)
        {
            //入度为0
            if(in[i]==0)
            //加入队列
            q.push(i);
        }
        //（2）bfs
        while(q.size())
        {
            int t=q.front();
            q.pop();
            //拿出点后，要把这个点相连的边删掉
            for(int a:edge[t])
            {
                //入度--
                in[a]--;
                //如果入度为0，进入队列
                if(in[a]==0)
                q.push(a);
            }
        }
        //4.判断是否有环
        for(int i=0;i<n;i++)
        {
            if(in[i])
            return false;
        } 
        return true;
    }
};

课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

算法原理：

本题跟课程表一模一样，只是返回的结果不一样，本题要返回一个序列，所以我们用一个数组统计一下信息即可。

代码实现：

class Solution 
{
public:
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) 
    {
        
        //1.准备工作
        vector<vector<int>> edge(n);//用来储存图
        //unordered_map<int,vector<int>> edge;
        vector<int> in(n);//用来标记入度

        //2.建图
        for(auto& e:prerequisites)
        {
            int a=e[0],b=e[1];  //b->a的一条边
            //把a插入到b的后面
            edge[b].push_back(a);
            //
            in[a]++;
        }

        //3.拓扑排序
        queue<int> q;
        vector<int> ret;
        //(1)把所有入度为0的点加入到队列中
        for(int i=0;i<n;i++)
        {
            //入度为0
            if(in[i]==0)
            //加入队列
            q.push(i);
        }
        //（2）bfs
        while(q.size())
        {
            int t=q.front();
            q.pop();
            ret.push_back(t);
            for(int a:edge[t])
            {
                //入度--
                in[a]--;
                //如果入度为0，进入队列
                if(in[a]==0)
                q.push(a);
            }
        }
        //4.判断是否有环
        if(ret.size()==n)return ret;
        else return {};
    }
};

总结：

其实用代码建图很简单，对于代码其实也就两三行的事情：

1. 准备工作

//数组模拟
vector<vector<int>> edge(n)//n是大小
//哈希表模拟
unordered_map<int,vector<int>> edge;
//入度
vector<int> in(n);

2. 建图

for(auto& e:prerequisites)
{
	int e[0]=a,e[1]=b;  b->a;
	//找到b这条边
	e[b].push_back(a);
	//有一条边指向了a
	//a入度++
	in[a]++;
}

3. 拓扑排序

排序就根据前言分析的步骤实现。