关于智能合约:拓扑排序YYDS

读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：

207. 课程表

210. 课程表 II

———–

​很多读者留言说要看「图」相干的算法，那就满足大家，联合算法题把图相干的技巧给大家过一遍。

前文 学习数据结构的框架思维 说了，数据结构相干的算法无非两点：遍历 + 拜访。那么图的根本遍历办法也很简略，前文 图算法根底 就讲了如何从多叉树的遍历框架扩大到图的遍历。

图这种数据结构还有一些比拟非凡的算法，比方二分图判断，有环图无环图的判断，拓扑排序，以及最经典的最小生成树，单源最短门路问题，更难的就是相似网络流这样的问题。

不过以我的教训呢，像网络流这种问题，你又不是打比赛的，除非本人特地有趣味，否则就没必要学了；像最小生成树和最短门路问题，尽管从刷题的角度用到的不多，但它们属于经典算法，学有余力能够把握一下；像拓扑排序这一类，属于比拟根本且有用的算法，应该比拟熟练地把握。

那么本文就联合具体的算法题，来说两个图论算法：有向图的环检测、拓扑排序算法。

判断有向图是否存在环

先来看看力扣第 207 题「课程表」：

函数签名如下：

int[] findOrder(int numCourses, int[][] prerequisites);

题目应该不难理解，什么时候无奈修完所有课程？当存在循环依赖的时候。

其实这种场景在现实生活中也非常常见，比方咱们写代码 import 包也是一个例子，必须正当设计代码目录构造，否则会呈现循环依赖，编译器会报错，所以编译器实际上也应用了相似算法来判断你的代码是否可能胜利编译。

看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只有图中存在环，那就阐明存在循环依赖 。

具体来说，咱们首先能够把课程看成「有向图」中的节点，节点编号别离是 0, 1, ..., numCourses-1，把课程之间的依赖关系看做节点之间的有向边。

比如说必须修完课程 1 能力去修课程 3，那么就有一条有向边从节点 1 指向 3。

所以咱们能够依据题目输出的 prerequisites 数组生成一幅相似这样的图：

如果发现这幅有向图中存在环，那就阐明课程之间存在循环依赖，必定没方法全副上完；反之，如果没有环，那么必定能上齐全部课程 。

好，那么想解决这个问题，首先咱们要把题目的输出转化成一幅有向图，而后再判断图中是否存在环。

如何转换成图呢？咱们前文 图论根底 写过图的两种存储模式，邻接矩阵和邻接表。

以我刷题的教训，常见的存储形式是应用邻接表，比方上面这种构造：

List<Integer>[] graph;

graph[s] 是一个列表，存储着节点 s 所指向的节点 。

所以咱们首先能够写一个建图函数：

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 图中共有 numCourses 个节点
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {graph[i] = new LinkedList<>();}
    for (int[] edge : prerequisites) {int from = edge[1];
        int to = edge[0];
        // 修完课程 from 能力修课程 to
        // 在图中增加一条从 from 指向 to 的有向边
        graph[from].add(to);
    }
    return graph;
}

图建进去了，怎么判断图中有没有环呢？

先不要急，咱们先来思考如何遍历这幅图，只有会遍历，就能够判断图中是否存在环了 。

前文 图论根底 写了 DFS 算法遍历图的框架，无非就是从多叉树遍历框架扩大进去的，加了个 visited 数组罢了：

// 避免反复遍历同一个节点
boolean[] visited;
// 从节点 s 开始 BFS 遍历，将遍历过的节点标记为 true
void traverse(List<Integer>[] graph, int s) {if (visited[s]) {return;}
    /* 前序遍历代码地位 */
    // 将以后节点标记为已遍历
    visited[s] = true;
    for (int t : graph[s]) {traverse(graph, t);
    }
    /* 后序遍历代码地位 */
}

那么咱们就能够间接套用这个遍历代码：

// 避免反复遍历同一个节点
boolean[] visited;

boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    
    visited = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {traverse(graph, i);
    }
}

void traverse(List<Integer>[] graph, int s) {// 代码见上文}

留神图中并不是所有节点都相连，所以要用一个 for 循环将所有节点都作为终点调用一次 DFS 搜索算法。

这样，就能遍历这幅图中的所有节点了，你打印一下 visited 数组，应该全是 true。

前文 学习数据结构和算法的框架思维 说过，图的遍历和遍历多叉树差不多，所以到这里你应该都能很容易了解。

那么如何判断这幅图中是否存在环呢？

咱们前文 回溯算法外围套路详解 说过，你能够把递归函数看成一个在递归树上游走的指针，这里也是相似的：

你也能够把 traverse 看做在图中节点上游走的指针，只须要再增加一个布尔数组 onPath 记录以后 traverse 通过的门路：

boolean[] onPath;

boolean hasCycle = false;
boolean[] visited;

void traverse(List<Integer>[] graph, int s) {if (onPath[s]) {
        // 发现环！！！hasCycle = true;
    }
    if (visited[s]) {return;}
    // 将节点 s 标记为已遍历
    visited[s] = true;
    // 开始遍历节点 s
    onPath[s] = true;
    for (int t : graph[s]) {traverse(graph, t);
    }
    // 节点 s 遍历实现
    onPath[s] = false;
}

这里就有点回溯算法的滋味了，在进入节点 s 的时候将 onPath[s] 标记为 true，来到时标记回 false，如果发现 onPath[s] 曾经被标记，阐明呈现了环。

PS：参考贪吃蛇没绕过弯儿咬到本人的场景 。

这样，就能够在遍历图的过程中顺便判断是否存在环了，残缺代码如下：

// 记录一次 traverse 递归通过的节点
boolean[] onPath;
// 记录遍历过的节点，避免走回头路
boolean[] visited;
// 记录图中是否有环
boolean hasCycle = false;

boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    
    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];
    
    for (int i = 0; i < numCourses; i++) {
        // 遍历图中的所有节点
        traverse(graph, i);
    }
    // 只有没有循环依赖能够实现所有课程
    return !hasCycle;
}

void traverse(List<Integer>[] graph, int s) {if (onPath[s]) {
        // 呈现环
        hasCycle = true;
    }
    
    if (visited[s] || hasCycle) {
        // 如果曾经找到了环，也不必再遍历了
        return;
    }
    // 前序遍历代码地位
    visited[s] = true;
    onPath[s] = true;
    for (int t : graph[s]) {traverse(graph, t);
    }
    // 后序遍历代码地位
    onPath[s] = false;
}

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {// 代码见前文}

这道题就解决了，外围就是判断一幅有向图中是否存在环。

不过如果出题人持续恶心你，让你不仅要判断是否存在环，还要返回这个环具体有哪些节点，怎么办？

你可能说，onPath 外面为 true 的索引，不就是组成环的节点编号吗？

不是的，假如下图中绿色的节点是递归的门路，它们在 onPath 中的值都是 true，但显然成环的节点只是其中的一部分：

这个问题留给大家思考，我会在公众号留言区置顶正确的答案。

那么接下来，咱们来再讲一个经典的图算法：拓扑排序 。

拓扑排序

看下力扣第 210 题「课程表 II」：

这道题就是上道题的进阶版，不是仅仅让你判断是否能够实现所有课程，而是进一步让你返回一个正当的上课程序，保障开始修每个课程时，前置的课程都曾经修完。

函数签名如下：

int[] findOrder(int numCourses, int[][] prerequisites);

这里我先说一下拓扑排序（Topological Sorting）这个名词，网上搜进去的定义很数学，这里罗唆用百度百科的一幅图来让你直观地感触下：

直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图外面，所有箭头方向都是统一的 ，比方上图所有箭头都是朝右的。

很显然，如果一幅有向图中存在环，是无奈进行拓扑排序的，因为必定做不到所有箭头方向统一；反过来，如果一幅图是「有向无环图」，那么肯定能够进行拓扑排序。

然而咱们这道题和拓扑排序有什么关系呢？

其实也不难看出来，如果把课程形象成节点，课程之间的依赖关系形象成有向边，那么这幅图的拓扑排序后果就是上课程序 。

首先，咱们先判断一下题目输出的课程依赖是否成环，成环的话是无奈进行拓扑排序的，所以咱们能够复用上一道题的主函数：

public int[] findOrder(int numCourses, int[][] prerequisites) {if (!canFinish(numCourses, prerequisites)) {
        // 不可能实现所有课程
        return new int[]{};
    }
    // ...
}

那么关键问题来了，如何进行拓扑排序？是不是又要秀什么高大上的技巧了？

其实特地简略，将后序遍历的后果进行反转，就是拓扑排序的后果 。

间接看解法代码：

boolean[] visited;
// 记录后序遍历后果
List<Integer> postorder = new ArrayList<>();

int[] findOrder(int numCourses, int[][] prerequisites) {
    // 先保障图中无环
    if (!canFinish(numCourses, prerequisites)) {return new int[]{};}
    // 建图
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    // 进行 DFS 遍历
    visited = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {traverse(graph, i);
    }
    // 将后序遍历后果反转，转化成 int[] 类型
    Collections.reverse(postorder);
    int[] res = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {res[i] = postorder.get(i);
    }
    return res;
}

void traverse(List<Integer>[] graph, int s) {if (visited[s]) {return;}
    
    visited[s] = true;
    for (int t : graph[s]) {traverse(graph, t);
    }
    // 后序遍历地位
    postorder.add(s);
}

// 参考上一题的解法
boolean canFinish(int numCourses, int[][] prerequisites);

// 参考前文代码
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites);

代码尽管看起来多，然而逻辑应该是很分明的，只有图中无环，那么咱们就调用 traverse 函数对图进行 BFS 遍历，记录后序遍历后果，最初把后序遍历后果反转，作为最终的答案。

那么为什么后序遍历的反转后果就是拓扑排序呢 ？

我这里也防止数学证实，用一个直观地例子来解释，咱们就说二叉树，这是咱们说过很屡次的二叉树遍历框架：

void traverse(TreeNode root) {
    // 前序遍历代码地位
    traverse(root.left)
    // 中序遍历代码地位
    traverse(root.right)
    // 后序遍历代码地位
}

二叉树的后序遍历是什么时候？遍历完左右子树之后才会执行后序遍历地位的代码。换句话说，当左右子树的节点都被装到后果列表外面了，根节点才会被装进去。

后序遍历的这一特点很重要，之所以拓扑排序的根底是后序遍历，是因为一个工作必须在等到所有的依赖工作都实现之后能力开始开始执行 。

你把每个工作了解成二叉树外面的节点，这个工作所依赖的工作了解成子节点，那你是不是应该先把所有子节点解决完再解决父节点？这是不是就是后序遍历？

再说一说为什么还要把后序遍历后果反转，才是最终的拓扑排序后果。

咱们说一个节点能够了解为一个工作，这个节点的子节点了解为这个工作的依赖，但你留神咱们之前说的依赖关系的示意：如果做完 A 能力去做 B，那么就有一条从 A 指向 B 的有向边，示意 B 依赖 A。

那么，父节点依赖子节点，体现在二叉树外面应该是这样的：

是不是和咱们失常的二叉树指针指向反过来了？所以失常的后序遍历后果应该进行反转，才是拓扑排序的后果 。

以上，我简略解释了一下为什么「拓扑排序的后果就是反转之后的后序遍历后果」，当然，我的解释尽管比拟直观，但并没有严格的数学证实，有趣味的读者能够本人查一下。

总之，你记住拓扑排序就是后序遍历反转之后的后果，且拓扑排序只能针对有向无环图，进行拓扑排序之前要进行环检测，这些知识点曾经足够了。

_____________

查看更多优质算法文章 点击我的头像，手把手带你刷力扣，致力于把算法讲清楚！我的 算法教程 曾经取得 90k star，欢送点赞！