力扣207——课程表

这道题主要利用拓扑排序,判断该图是否有环,其中还会涉及到邻接矩阵。

原题

现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?

示例 1:

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

说明:

  1. 输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

提示:

  1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。
  2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程(21分钟),介绍拓扑排序的基本概念。
  3. 拓扑排序也可以通过 BFS 完成。

原题url:https://my.openwrite.cn/user/...

解题

这是我第一次遇到图相关的题目,讲道理,有向图、无向图、出度、入度之类的概念还能记得,但是拓扑排序、邻接矩阵、逆邻接矩阵却只是知道有这么一个概念,但具体内容也已经忘光了。我会在下面的解题过程中为大家呈现这些概念。

先介绍一下拓扑排序:

在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。

从上面的概念中可以看出,这道题目就是要判断给定的图是否是有向无环图,也就是其是否有拓扑排序

求一个图是否有拓扑排序,我们一般有两种办法:广度优先搜索 + 邻接矩阵深度优先搜索 + 逆邻接矩阵。接下来我们逐一来为大家分析:

广度优先搜索 + 邻接矩阵

首先看一下什么是邻接矩阵

在图论中,邻接矩阵(英语:adjacency matrix)是表示一种图结构的常用表示方法。它用数字方阵记录各点之间是否有边相连,数字的大小可以表示边的权值大小。

这么看有点抽象,简单点说:就是一个图中各个节点的后继节点链表。

举个例子:

这样一个图,其邻接矩阵为:

1 -> 2 -> 3 -> null
2 -> 4 -> null
3 -> 4 -> null
4 -> null

好了,弄懂了邻接矩阵,我们来想想如何使用广度优先搜索

假设有向图无环,那么从入度为 0 的点,依次删除,这里并不是真正意义上的删除,只是如果该节点消失后,其后继节点的入度需要减1,此时再判断是否又有新的入度为0的节点,如果最终所有节点都会被减到0,那么说明有向图无环,让我们看一下代码:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 利用入度表和DFS进行拓扑排序
        // 下标i对应的节点,其入度的数组
        int[] indegressArray = new int[numCourses];
        // key:节点i,value:其所有出度节点
        Map> map = new HashMap<>(numCourses * 4 / 3 + 1);
        for (int[] pre : prerequisites) {
            indegressArray[pre[0]] += 1;
            List list = map.get(pre[1]);
            if (list == null) {
                list = new LinkedList<>();
                map.put(pre[1], list);
            }
            list.add(pre[0]);
        }
        // 将入度为0的入队列
        LinkedList list = new LinkedList<>();
        for (int i = 0; i < indegressArray.length; i++) {
            int indegress = indegressArray[i];
            if (indegress != 0) {
                continue;
            }
            list.add(i);
        }

        while (!list.isEmpty()) {
            // 获取第一个节点,并将这个节点"删除"
            int node = list.removeFirst();
            numCourses--;
            // 那么以node作为前驱节点的节点,其入度-1
            List preList = map.get(node);
            if (preList == null) {
                continue;
            }
            for (Integer suffixNode : preList) {
                indegressArray[suffixNode] -= 1;
                // 如果该节点入度减为0,则也入队
                if (indegressArray[suffixNode] == 0) {
                    list.add(suffixNode);
                }
            }
        }

        // 如果最终所有节点都入队并且也出队,那么说明该图无环。
        return numCourses == 0;
    }
}

提交OK,执行用时:8 ms,内存消耗:45 MB,执行用时只战胜了84.74%的 java 提交记录,我们再优化优化试试。

广度优先搜索 + 邻接矩阵 优化

map 虽然理论上查找速度为 O(1),但需要先计算 hash 值,而数组的话,其获取地址是根据下标的。而我们这里的数字是连续的,并且从 0 开始,因此很适用数组的情况,因此做一个改造:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 利用入度表DFS进行拓扑排序
        // 下标i对应的节点,其入度的数组
        int[] indegressArray = new int[numCourses];
        // 邻接矩阵,数组下标:节点i,list:其所有后继节点
        List[] adjacencyMatrix = new LinkedList[numCourses];
        for (int[] pre : prerequisites) {
            // 入度表相应节点的入度+1
            indegressArray[pre[0]] += 1;
            // 邻接矩阵
            List list = adjacencyMatrix[pre[1]];
            if (list == null) {
                list = new LinkedList<>();
                adjacencyMatrix[pre[1]] = list;
            }
            list.add(pre[0]);
        }
        // 将入度为0的入队列
        LinkedList list = new LinkedList<>();
        for (int i = 0; i < indegressArray.length; i++) {
            int indegress = indegressArray[i];
            if (indegress != 0) {
                continue;
            }
            list.add(i);
        }

        while (!list.isEmpty()) {
            // 获取第一个节点,并将这个节点"删除"
            int node = list.removeFirst();
            numCourses--;
            // 那么以node作为前驱节点的后继节点,入度-1
            List preList = adjacencyMatrix[node];
            if (preList == null) {
                continue;
            }
            for (Integer prefixNode : preList) {
                indegressArray[prefixNode] -= 1;
                // 如果该节点入度减为0,则也入队
                if (indegressArray[prefixNode] == 0) {
                    list.add(prefixNode);
                }
            }
        }

        // 如果最终所有节点都入队并且也出队,那么说明该图无环。
        return numCourses == 0;
    }
}

提交OK,执行用时:5 ms,内存消耗:45 MB,执行用时战胜了94.01%的 java 提交记录,应该差不多了。

深度优先搜索

既然知道了邻接矩阵,那么逆连接矩阵就是指的各个节点的前驱节点链表。还是以之前的那个例子:

这样一个图,其逆逆邻接矩阵为:

1 -> null
2 -> 1 -> null
3 -> 1 -> null
4 -> 2 -> 3 -> null

那么如何进行深度优先遍历呢?也就是以一个节点出发,访问其相邻节点,一直遍历下去,如果发现一个节点被访问两次,说明有环,那么返回失败,否则就标记该节点已经全部访问完成。当访问完全部节点成功后,说明有向图无环。

这么一看,深度优先遍历的时候,其实只要保证相邻即可,无所谓邻接矩阵还是逆邻接矩阵。

我们来看看代码:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 利用逆邻接矩阵,进行深度优先搜索
        HashSet[] inadjacencyMatrix = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            inadjacencyMatrix[i] = new HashSet<>();
        }
        // 构造逆连接矩阵(每个节点的所有后继节点)
        for (int[] array : prerequisites) {
            inadjacencyMatrix[array[1]].add(array[0]);
        }

        // 所有节点的被使用情况,如果正在使用的节点,再次被访问,说明有环
        // 0:未使用;1:正在使用;2:已经使用完成;
        int[] used = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (dfs(i, inadjacencyMatrix, used)) {
                return false;
            }
        }

        return true;
    }

    public boolean dfs(int index, HashSet[] inadjacencyMatrix, int[] used) {
        // 如果当前节点已经处于正在被访问的状态,现在又再次访问,说明有环
        if (used[index] == 1) {
            return true;
        }
        // 如果当前节点已经访问结束,则可以不用再次被访问
        if (used[index] == 2) {
            return false;
        }

        // used[index] == 0,说明该节点从未被访问过,那么现在开始访问该节点
        used[index] = 1;
        // 深度遍历该节点的后继节点
        HashSet suffixNodes = inadjacencyMatrix[index];
        for (int suffixNode : suffixNodes) {
            if (dfs(suffixNode, inadjacencyMatrix, used)) {
                return true;
            }
        }
        // 深度遍历完成该节点,直接结束
        used[index] = 2;
        return false;
    }
}

提交OK,执行用时:8 ms,内存消耗:44.6 MB,优化的话,暂时并没有想到好方法。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这也是我第一次解决图相关的题目,涉及的知识点有些多,需要好好消化。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

你可能感兴趣的