打卡!!!每日一题

今天给大家分享一道拓扑排序的问题，本题也是一道经典的「拓扑排序」问题，通过这道题也顺便帮大家拓展一下拓扑排序的知识。

题目描述：

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

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

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

题目示例：

1.什么是拓扑序列

在了解什么叫拓扑序列之前，我们需要先知道数据结构中的图，其图分为有向图和无向图。

而在有向图中，如果该图中存在环，则此图将不会有拓扑序列

给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：

对于图 G 中的任意一条有向边 (u, v)，u 在排列中都出现在 v 的前面。

如何构造出拓扑序列：

从上图可以看出，拓扑排序就是依次去找入度为0的结点，所以一旦一个有向图中存在环的话，就像下图所示有向有环图：

1能到3，而3也能到1的话，则表示1，3所构成的路径中含有环，就无法产生拓扑序列，因为在上图中，没有入度为0的点。

在我们本题中，要求的就是没有环，判断有向图中有没有环的方法就是拓扑排序。

2.有向图和题目之间的联系

我们以题目示例2为例：

numCourses = 2, prerequisites = [ [1,0],[0,1]]

numCourses则表示我们的结点数，prerequisites表示路径，则该路径构成的图如下所示：

很明显：是有环的，有环则表示无法构成拓扑序列，说明不可能完成所有课程的学习。

那么问题来了，我们又该如何去将我们的课程结点以及路径构成图结构呢？

这个问题就涉及到图的存储方式了，最简单也是最常见的就是邻接表法，这是表示方法也多适用于稀疏图（PS：数据结构这门课程建议大家牢牢掌握，对我们的开发以及设计大有裨益），当然能够存储图的还有很多方式：

• 邻接矩阵
• 十字链表
• 邻接多重表

我们下面通过邻接表的方式来构建图

是不是很简单，我们有几个结点就构建几个链表，然后链表中就存储和其邻接的结点
所以对于本题，我们需要构建numCourses个链表。同时我们还需要用一个辅助的数组来存储每个节点的入度，方便我们去遍历和访问

最终题目代码如下：

    //初始化邻接表--用于存储图结构
    List<List<Integer>> edges;
    int[] indeg;

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


        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        indeg = new int[numCourses];//存储所有点的入度
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            ++indeg[info[0]];
        }
        Queue<Integer> queue = new LinkedList<Integer>(); //遍历--只要存在环，就会遍历失败
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

        int visited = 0;
        while (!queue.isEmpty()) {
            ++visited;
            int u = queue.poll();
            for (int v : edges.get(u)) {//获取其临接点
                --indeg[v];//更新入度
                if (indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        return visited == numCourses;//存在拓扑序列的话 所有的点都可以被访问到，否则就会访问失败
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

相关题目还有一个基本一样的：210. 课程表 II

今天大家顺便一起解决了。

题目描述：

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

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

题目示例：

本题和上一题基本就是一模一样，唯一的不同的就是我们需要记录一下拓扑序列的输出顺序。

    List<List<Integer>> edgs;
    int[] indeg;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edgs = new ArrayList<>();
        indeg = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edgs.add(new ArrayList<Integer>());
        }
        //生成邻接表
        for (int[] t : prerequisites) {
            edgs.get(t[1]).add(t[0]);
            indeg[t[0]] = indeg[t[0]] + 1;
        }
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> ansList = new ArrayList<>();
        //让所有入度为0的点入队
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int t = queue.poll();
            ansList.add(t);
            List<Integer> tList = edgs.get(t);
            for (int i : tList) {
                indeg[i] = indeg[i] - 1;
                if (indeg[i] == 0) {
                    queue.add(i);
                }
            }
        }
        int[] ans = new int[ansList.size()];
        if (ansList.size() == numCourses) {
            for (int i = 0; i < ansList.size(); i++) {
                ans[i] = ansList.get(i);
            }
        } else ans = new int[0];

        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

数据结构的图结构原本就要比其他的数据结构要难一点，当然主要是见得比较少，所以对该题不是很理解，也不要气馁，慢慢来由浅入深，因为你做不出这道题目的原因绝对不是因为你的能力不行，而是知识点的欠缺。

最后给大家留下一句话共勉：

未来的你一定会感谢现在努力的自己。