拓扑排序原理与解题套路

╰半橙微兮° 2021-12-24 14:29 258阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640][]

**什么是拓扑排序**

其实最开始学习算法，听到拓扑排序这几个字我也是懵逼的，后来学着学着才慢慢知道是怎么一回事。关于 **拓扑** 这个词，在网上找到这么一段解释：

所谓“拓扑”就是把实体抽象成与其大小、形状无关的“点”，而把连接实体的线路抽象成“线”，进而以图的形式来表示这些点与线之间关系的方法，其目的在于研究这些点、线之间的相连关系。

表示点和线之间关系的图被称为拓扑结构图。

拓扑结构与几何结构属于两个不同的数学概念。

在几何结构中，我们要考察的是点、线之间的位置关系，或者说几何结构强调的是点与线所构成的形状及大小。如梯形、正方形、平行四边形及圆都属于不同的几何结构，但从拓扑结构的角度去看，由于点、线间的连接关系相同，从而具有相同的拓扑结构即环型结构。

也就是说，**不同的几何结构可能具有相同的拓扑结构**。

拓扑在计算机领域研究的就是图，既然是图，那就会有节点和边，**节点表示的是现实生活中抽象的东西，边表示的是这些东西之间的关系**。

仔细想想，其实现实生活中的很多东西都能够抽象成计算机世界当中的图。

比如说对于实际的地图，我们可以用节点表示岔路口，边表示岔路口之间的连线；人的朋友圈，我们用节点表示人，用边表示人与人之间的关系；再比如历史事件，我们用节点表示事件，用边表示事件之间的联系；不管是人或者事，只要找到了其对应的联系，往往都可以抽象成图。

**拓扑排序解决的是依赖图问题**。

依赖图表示的是节点的关系是有依赖性的，比如你要做事件 A，前提是你已经做了事件 B。除了 “先有鸡还是先有蛋” 这类问题，一般来说事件的依赖关系是单向的，因此我们都用**有向无环图**来表示依赖关系。

拓扑排序就是根据这些依赖来给出一个做事情，或者是事件的一个顺序。

举个例子，朋友来家里吃饭，你准备做饭，你要做饭，首先得买菜，买菜得去超市，去超市要出门搭车，因此这个顺序就是 出门搭车 -> 到超市 -> 买菜 -> 回家做饭。

当然我举的这个例子你不需要计算机的帮助也能很清楚地知道这个顺序，但是有些事情并不好直接看出来，比如常见的 “一个非常大的项目中，如何确定源代码文件的依赖关系，并给出相应的编译顺序？”。

**我们要学的是一个解决一类问题的普适的方法，而不是学习怎么快速得到一个具体问题的结果，换句话说，在学习之中，思考过程往往比结果和答案更重要**。

**实现原理**

和图相关的问题常见的算法就是搜索，深度和广度，拓扑排序也不例外，我们首先来看看稍微简单，好理解的**广度优先搜索**，先放上代码模版：

public List<...> bfsTopologicalSort() {    // 边界条件检测    if (...) {        return true;    }    Map<..., List<...>> graph = new HashMap<>();    // 构建图    ...    // 这里表示的是对于每个节点，其有多少前置条件（前置节点）    int[] inDegree = new int[totalNodeNumber];    // 根据图中节点的依赖关系去改变 inDegree 数组    for (Entry.Map<..., List<...>> entry : graph.entrySet()) {        ...    }    Queue<...> queue = new LinkedList<>();    for (int i = 0; i < numCourses; ++i) {        if (inDegree[i] == 0) {            queue.offer(...);        }     }    List<...> result = new ArrayList<...>();    while (!queue.isEmpty()) {        int cur = queue.poll();        // 记录当前结果        result.add(...);        // 对于当前节点，解除对其下一层节点的限制        for (... i : map.getOrDefault(cur, new ArrayList<...>())) {            inDegree[i]--;            if (inDegree[i] == 0) {                queue.offer(...);            }        }    }    return result;}
        // 边界条件检测
        if (...) {
        
            return true;
        }
        Map<..., List<...>> graph = new HashMap<>();
        // 构建图
        ...
        // 这里表示的是对于每个节点，其有多少前置条件（前置节点）
        int[] inDegree = new int[totalNodeNumber];
    
        // 根据图中节点的依赖关系去改变 inDegree 数组
        for (Entry.Map<..., List<...>> entry : graph.entrySet()) {
        
            ...
        }
    
        Queue<...> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
        
            if (inDegree[i] == 0) {
        
                queue.offer(...);
            } 
        }
    
        List<...> result = new ArrayList<...>();
        while (!queue.isEmpty()) {
        
            int cur = queue.poll();
    
            // 记录当前结果
            result.add(...);
    
            // 对于当前节点，解除对其下一层节点的限制
            for (... i : map.getOrDefault(cur, new ArrayList<...>())) {
        
                inDegree[i]--;
                if (inDegree[i] == 0) {
        
                    queue.offer(...);
                }
            }
        }
    
        return result;
    }

拓扑排序问题是基于图的算法，那么首先我们要做的就是将问题抽象为图。

这里我用了一个 HashMap 来表示图，其中 Key 表示的是具体的一个节点，Value 表示的是这个节点其下层节点，也就是 List 里面的节点依赖于当前节点，之所以这样表示依赖关系是为了我们后面实现的方便。

接下来我们会用一个 inDegree 数组来表示每个节点有多少个依赖的节点，选出那些不依赖任何节点的节点，这些节点应该被最先输出，按照一般的广度优先搜索思维，我们开一个队列，将这些没有依赖的节点放进去。

最后就是广度优先搜索的步骤，我们保证从队列里面出来的节点是当前没有依赖或者依赖已经被解除的节点，我们将这些节点输出，这个节点输出，其下一层节点的依赖就要相应的减少，我们改变 inDegree 数组中对应的值即可，如果改变后，对应节点没有任何依赖了，表明这个节点可以被输出了，就把它加进队列，等待被输出。

最后的最后就是输出我们得到的答案，但是这里要提醒的是，我们要考虑出现环的情况，就类似 “鸡生蛋，蛋生鸡” 的问题，比如 A 依赖于 B，B 也依赖于 A，这时我们是得不到答案的。

我们再来看看**深度优先搜索**，其思想和前面讲的广度优先搜索略微不同，我们不再需要 inDegree 数组了，而且我们需要去用另一种方式去判断图中是否存在环，先放上代码模版：

public ... dfsTopologicalSort() {    // 边界条件检测    if (...) {    }    Map<..., List<...>> graph = new HashMap<>();    // 构建图    ...    boolean[] visited = new boolean[numCourses];    boolean[] isLooped = new boolean[numCourses];    List<...> result = new ArrayList<...>();    for (int i = 0; i < totalNodeNumber; ++i) {                               if (!visited[i] && !dfs(result, graph, visited, isLooped, i)) {            return new ArrayList<...>();        }    }    return result;}private ... dfs(List<...> result,                Map<..., List<...>>[] graph,                boolean[] visited,                boolean[] isLoop,                ... curNode) {    // 判断是否有环    if (isLoop[curNode]) {        return false;    }    isLoop[curNode] = true;    // 遍历当前节点的前置节点，也就是依赖节点    for (int i : graph.get(curNode) {        if (visited[i]) {            continue;        }        if (!dfs(graph, visited, isLoop, i)) {            return false;        }    }    isLoop[curNode] = false;    // record answer    result.add(curNode)    visited[curNode] = true;    return true;}
        // 边界条件检测
        if (...) {
        
    
        }
    
        Map<..., List<...>> graph = new HashMap<>();
    
        // 构建图
        ...
    
        boolean[] visited = new boolean[numCourses];
        boolean[] isLooped = new boolean[numCourses];
    
        List<...> result = new ArrayList<...>();
        for (int i = 0; i < totalNodeNumber; ++i) {                       
            if (!visited[i] && !dfs(result, graph, visited, isLooped, i)) {
        
                return new ArrayList<...>();
            }
        }
    
        return result;
    }
    
    private ... dfs(List<...> result,
                    Map<..., List<...>>[] graph,
                    boolean[] visited,
                    boolean[] isLoop,
                    ... curNode) {
        
        // 判断是否有环
        if (isLoop[curNode]) {
        
            return false;
        }
    
        isLoop[curNode] = true;
    
        // 遍历当前节点的前置节点，也就是依赖节点
        for (int i : graph.get(curNode) {
        
            if (visited[i]) {
        
                continue;
            }
    
            if (!dfs(graph, visited, isLoop, i)) {
        
                return false;
            }
        }
    
        isLoop[curNode] = false;
    
        // record answer
        result.add(curNode)
        visited[curNode] = true;
    
        return true;
    }

有一点需要注意的是，构建图的时候，我们需要和之前的广度优先搜索反转一下，也就是这里的 Key 表示的是一个节点，Value 中存的是其所依赖的节点，这也是和我们的实现方式有关，我们需要用到递归，递归用到函数栈，先处理的函数（节点）后输出结果。

理解了上面这一点，下面就是用递归去解决这个深度优先搜索问题，但是有一点是我们需要用到两个 boolean 数组，一个（visited 数组）是记录我们访问过的节点，避免重复访问，另外一个是防止环的出现，怎么避免，**深度优先搜索是沿着一条路径一直搜索下去，我们需要保证这一条路径不会经过某个节点两次**，注意我这里说的是一条路径。

两种算法算是两种实现的方式，但是目的都是一样的，思想是类似的。

**相关习题**

## 课程表 II ##

题目来源于 LeetCode 上第 210 号问题：课程表 II。题目难度为 Medium，目前通过率为 46.6% 。

### 题目描述 ###

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

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

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

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

**示例 1:**

输入: 2, [[1,0]] 输出: [0,1]解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。1,0]] 
    输出: [0,1]
    解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

**示例 2:**

输入: 4, [[1,0],[2,0],[3,1],[3,2]]输出: [0,1,2,3] or [0,2,1,3]解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。[2,0],[3,1],[3,2]]
    输出: [0,1,2,3] or [0,2,1,3]
    解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
    
    因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

### 题目解析 ###

有一些课程，每个课程都有前置课程，必须把前置课程修完了才能修这门课程。这道题就是单纯使用了拓扑排序，这里我把两种实现方式都列下来：

按照上面的模板有两个版本的实现方式：

### 基于深度优先搜索版本 ###

public int[] findOrder(int numCourses, int[][] prerequisites) {            List<Integer> result = new ArrayList<>();    List<Integer>[] graph = new ArrayList[numCourses];    for (int i = 0; i < numCourses; ++i) {        graph[i] = new ArrayList<Integer>();    }    for (int i = 0; i < prerequisites.length; ++i) {        graph[prerequisites[i][0]].add(prerequisites[i][1]);    }    boolean[] visited = new boolean[numCourses];    boolean[] isLooped = new boolean[numCourses];    for (int i = 0; i < numCourses; ++i) {        if (!visited[i] && !dfs(graph, visited, isLooped, i, result)) {            return new int[0];        }    }    int[] output = new int[numCourses];    int index = 0;    for (int i : result) {        output[index++] = i;    }    return output;}private boolean dfs(List<Integer>[] graph,                    boolean[] visited,                    boolean[] isLooped,                    int curCourse,                    List<Integer> result) {    if (isLooped[curCourse]) {        return false;    }    isLooped[curCourse] = true;    for (int i : graph[curCourse]) {        if (!visited[i] && !dfs(graph, visited, isLooped, i, result)) {            return false;        }    }    isLooped[curCourse] = false;    visited[curCourse] = true;    result.add(curCourse);    return true;}int[] findOrder(int numCourses, int[][] prerequisites) {        
        List<Integer> result = new ArrayList<>();
    
        List<Integer>[] graph = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; ++i) {
        
            graph[i] = new ArrayList<Integer>();
        }
    
        for (int i = 0; i < prerequisites.length; ++i) {
        
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
    
        boolean[] visited = new boolean[numCourses];
        boolean[] isLooped = new boolean[numCourses];
        for (int i = 0; i < numCourses; ++i) {
        
            if (!visited[i] && !dfs(graph, visited, isLooped, i, result)) {
        
                return new int[0];
            }
        }
    
        int[] output = new int[numCourses];
        int index = 0;
        for (int i : result) {
        
            output[index++] = i;
        }
    
        return output;
    }
    
    private boolean dfs(List<Integer>[] graph,
                        boolean[] visited,
                        boolean[] isLooped,
                        int curCourse,
                        List<Integer> result) {
        
        if (isLooped[curCourse]) {
        
            return false;
        }
    
        isLooped[curCourse] = true;
        for (int i : graph[curCourse]) {
        
            if (!visited[i] && !dfs(graph, visited, isLooped, i, result)) {
        
                return false;
            }
        }
    
        isLooped[curCourse] = false;
        visited[curCourse] = true;
        result.add(curCourse);
    
        return true;
    }

### 基于广度优先搜索版本 ###

public int[] findOrder(int numCourses, int[][] prerequisites) {    if (prerequisites == null) {        return new int[0];    }    int[] inDegree = new int[numCourses];    Map<Integer, List<Integer>> map = new HashMap<>();    for (int i = 0; i < numCourses; ++i) {        map.put(i, new ArrayList<Integer>());    }    for (int i = 0; i < prerequisites.length; ++i) {        map.get(prerequisites[i][1]).add(prerequisites[i][0]);        inDegree[prerequisites[i][0]]++;    }    Queue<Integer> queue = new LinkedList<>();    for (int i = 0; i < numCourses; ++i) {        if (inDegree[i] == 0) {            queue.offer(i);        }     }    List<Integer> result = new ArrayList<>();    while (!queue.isEmpty()) {        int cur = queue.poll();        result.add(cur);        for (int i : map.getOrDefault(cur, new ArrayList<Integer>())) {            inDegree[i]--;            if (inDegree[i] == 0) {                queue.offer(i);            }        }    }    int[] output = new int[result.size()];    int index = 0;    for (int i : result) {        output[index++] = i;    }    return output.length == numCourses ? output : new int[0];}int[] findOrder(int numCourses, int[][] prerequisites) {
        
        if (prerequisites == null) {
        
            return new int[0];
        }
    
        int[] inDegree = new int[numCourses];
    
        Map<Integer, List<Integer>> map = new HashMap<>();
    
        for (int i = 0; i < numCourses; ++i) {
        
            map.put(i, new ArrayList<Integer>());
        }
    
        for (int i = 0; i < prerequisites.length; ++i) {
        
            map.get(prerequisites[i][1]).add(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
    
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
        
            if (inDegree[i] == 0) {
        
                queue.offer(i);
            } 
        }
    
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
        
            int cur = queue.poll();
            result.add(cur);
            for (int i : map.getOrDefault(cur, new ArrayList<Integer>())) {
        
                inDegree[i]--;
                if (inDegree[i] == 0) {
        
                    queue.offer(i);
                }
            }
        }
    
        int[] output = new int[result.size()];
        int index = 0;
        for (int i : result) {
        
            output[index++] = i;
        }
    
        return output.length == numCourses ? output : new int[0];
    }

**总结**

拓扑排序其实就是图类问题当中的一个简单应用，它其实是有固定的实现方式的，我们只需要掌握这些实现方式中的算法思想，相信它不再是一个难题。

**我们做题不是为了训练我们的做题速度，编码能力，更重要的是学习算法里面的一种思考问题的方式和方法，这种先进的思想或者说是思维模式可以引领着我们朝计算机领域更广阔、更深层次的地方去**。

## END ##

## ![640?wx\_fmt=png][640_wx_fmt_png] ##

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[☞][Link 2][一道腾讯面试题：厉害了我的杯][Link 3]

[☞][Link 4][十大经典排序算法动画与解析，看我就够了][Link 5]

[☞][Link 4][这或许是东半球分析十大排序算法最好的一篇文章][Link 6]

[☞][Link 4][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png 1] 你点的每个“在看”，我都认真当成了喜欢

[640]: /images/20211223/a83cc83fd86044509292b8e88911e300.png
[640_wx_fmt_png]: /images/20211223/d6535052ff5a41c68b65d6b97ccee7c1.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 6]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png 1]: /images/20211223/cc9c634a5b3d42d8970cc33b5dd159b6.png