拓扑排序

理论基础

• 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点$u$和$v$，若边$<u,v>\in E(G)$，**则$u$在线性序列中出现在$v$之前。**通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

• 拓扑排序主要用来解决有向图中的依赖解析（dependency resolution）问题。

  举例来说，如果我们将一系列需要运行的任务构成一个有向图，图中的有向边则代表某一任务必须在另一个任务之前完成这一限制。那么运用拓扑排序，我们就能得到满足执行顺序限制条件的一系列任务所需执行的先后顺序。当然也有可能图中并不存在这样一个拓扑顺序，这种情况下我们无法根据给定要求完成这一系列任务，这种情况称为循环依赖（circular dependency）。

• 拓扑排序存在的前提

  当且仅当一个有向图为有向无环图（directed acyclic graph，或称DAG）时，才能得到对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。

• 如何得到一个有向无环图的拓扑排序?

  要想完成拓扑排序，我们每次都应当从入度为0的结点开始遍历。因为只有入度为0的结点才能够成为拓扑排序的起点。否则根据拓扑排序的定义，只要一个结点v的入度不为0，则至少有一条边起始于其他结点而指向v，那么这条边的起点在拓扑排序的顺序中应当位于v之前，则v不能成为当前遍历的起点。

  • BFS

    与普通的广度优先遍历唯一的区别在于需要维护每一个节点对应的入度，并在遍历的每一层时选取入度为0的节点开始遍历（而普通的广度优先遍历则无此限制，可以从每一层任意一个节点开始遍历）。这个算法描述如下：

    1. 统计图的每一个节点的入度存储与数组inDeg。

    2. 选取入度为0的节点加入队列【贪心】

    3. 从队列中取出一个节点，

       • 将该节点加入输出
       • 将该节点的所有邻接点的入度树减1，减1后入度数变为0的节点加入队列

    4. 重复步骤3，直到遍历完所有的结点。

    5. 如果无法遍历完所有的结点，则意味着当前的图不是有向无环图。不存在拓扑排序。

       在基于广度优先搜索的拓扑排序中，可以根据最终拓扑排序输出列表的长度是否等于图的节点数，来判断输入图是否存在拓扑排序。

  • DFS

    使用深度优先搜索实现拓扑排序的基本思想是：对于一个特定节点，如果该节点的所有相邻节点都已经搜索完成，则该节点也会变成已经搜索完成的节点，在拓扑排序中，该节点位于其所有相邻节点的前面。一个节点的相邻节点指的是从该节点出发通过一条有向边可以到达的节点。

    由于拓扑排序的顺序和搜索完成的顺序相反，因此需要使用一个栈存储所有已经搜索完成的节点。深度优先搜索的过程中需要维护每个节点的状态，每个节点的状态可能有三种情况：

    • 0：未访问；
    • 1：访问中；
    • 2：已访问；
    • 初始时，所有节点的状态都是「未访问」。

    每一轮搜索时，任意选取一个「未访问」的节点 u，从节点 u 开始深度优先搜索。将节点 u 的状态更新为「访问中」，对于每个与节点 u 相邻的节点 v，判断节点 v 的状态，执行如下操作：

    • 如果节点 v 的状态是「未访问」，则继续搜索节点 v；
    • 如果节点 v 的状态是「访问中」，则找到有向图中的环，因此不存在拓扑排序；
    • 如果节点 v 的状态是「已访问」，则节点 v 已经搜索完成并加入输出排序列表，节点 u 尚未完成搜索，因此节点 u 的拓扑顺序一定在节点 v 的前面，不需要执行任何操作。
    • 当节点 u 的所有相邻节点的状态都是「已访问」时，将节点 u 的状态更新为「已访问」，并将节点 u 加入输出排序列表。
    • 当所有节点都访问结束之后，如果没有找到有向图中的环，则存在拓扑排序，所有节点从栈顶到栈底的顺序即为拓扑排序。

• BSF实现【掌握】

  int[] topoSort(int k, int[][] edges) {
          List<Integer>[] g = new ArrayList[k];
          Arrays.setAll(g, e -> new ArrayList<>());
          var inDeg = new int[k];// 入度
          for (var e : edges) {
              int x = e[0] - 1, y = e[1] - 1; // 顶点编号从 0 开始，方便计算
              g[x].add(y);
              ++inDeg[y];
          }
  
          var order = new ArrayList<Integer>();
          var q = new ArrayDeque<Integer>();
          for (var i = 0; i < k; ++i)
              if (inDeg[i] == 0) q.push(i);
          while (!q.isEmpty()) {
              var x = q.pop();
              order.add(x);
              for (var y : g[x])
                  if (--inDeg[y] == 0) q.push(y);
          }
          return order.stream().mapToInt(x -> x).toArray();
      }
  
  作者：灵茶山艾府
  链接：https://leetcode.cn/problems/build-a-matrix-with-conditions/solutions/1781092/by-endlesscheng-gpev/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

  • 复杂度

    • 时间复杂度：$O(E+V)$，$E$表示邻边的跳数，V为结点的个数

    • 空间复杂度：$O(V)$

相关题目

课程表 II【LC210】

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

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

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

• 思路：拓扑排序

  由于在选修课程 ai 前 必须 先选修 bi ，因此我们可以构建一条由bi 指向 ai的边，然后使用拓扑排序，优先遍历入度为0的节点，并将其加入拓扑排序数组中，如果最后数组的大小与节点个数不相同，那么证明有向图中有环存在，不可能完成所有课程

• 实现

  class Solution {
      public int[] findOrder(int numCourses, int[][] prerequisites) {
          int[] inDeg = new int[numCourses];
          List<Integer>[] g = new ArrayList[numCourses];
          Arrays.setAll(g, e -> new ArrayList<>());
          for (int[] p : prerequisites){
              int u = p[1], v = p[0];
              g[u].add(v);
              inDeg[v]++;
          }
          Deque<Integer> queue = new LinkedList<>();
          List<Integer> order = new ArrayList<>();
          for (int i = 0; i < numCourses; i++){
              if (inDeg[i] == 0){
                  queue.addLast(i);
              }
          }
          while (!queue.isEmpty()){
              int u = queue.pollFirst();
              order.add(u);
              for (int v : g[u]){
                  inDeg[v]--;
                  if (inDeg[v] == 0){
                      queue.addLast(v);
                  }
              }
          }
          return order.size() == numCourses ? order.stream().mapToInt(x -> x).toArray() : new int[]{};
  
  
  
      }
  }
  

  • 复杂度

    • 时间复杂度：$O(E+V)$，$E$表示邻边的跳数，V为结点的个数

    • 空间复杂度：$O(V)$

并行课程 III【LC2050】

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）。同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。

请你根据以下规则算出完成所有课程所需要的 最少 月份数：

• 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
• 你可以 同时 上 任意门课程 。

请你返回完成所有课程所需要的 最少 月份数。

**注意：**测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。

• 思路：拓扑排序+dp

  同[课程表 II【LC210】](#课程表 II【LC210】)我们需要求出所有课程的拓扑排序，然后定义状态$dp[i]$为完成某门课程的需要花费的最少月数。由于我们必须将所有的先修课$j$上完才能开始这门课程，因此有状态转移方程
  $$dp[i]=max(dp[j])+time[i]$$
  最终答案为$max(dp[i])$

• 实现

  由于题目保证一定存在拓扑排序，因此可以边拓扑边dp

  class Solution {
      public int minimumTime(int n, int[][] relations, int[] time) {
          List<Integer>[] g = new List[n];
          Arrays.setAll(g, e -> new ArrayList<>());
          int[] costs = new int[n];
          int[] inDeg = new int[n];
          Deque<Integer> queue = new LinkedList<>();
          // 邻接表
          for (int[] relation : relations){
              int u = relation[0] - 1, v = relation[1] - 1;
              g[u].add(v);
              inDeg[v]++;
          }
          // dp计算最少月份数 修完某课程的最少月份数为其先修课的最大时间+其完成需要的时间
          // dp[v] = time[v] + max(dp[u]);
          int res = 0;        
          // 入度
          for (int i = 0; i < n; i++){
              if (inDeg[i] == 0){
                  queue.addLast(i);
              }
          }
          // 拓扑排序
          while (!queue.isEmpty()){
              int u = queue.pollFirst();
              costs[u] += time[u];
              res = Math.max(res, costs[u]);
              // order[index++] = u;
              for (int v : g[u]){
                  costs[v] = Math.max(costs[v], costs[u]);
                  if (--inDeg[v] == 0){
                      queue.addLast(v);
                  }
              }             
          }
          return res;
          
  
      }
  }
  

  • 复杂度

    • 时间复杂度：$O(E+V)$，$E$表示邻边的跳数，V为结点的个数

    • 空间复杂度：$O(V)$

给定条件下构造矩阵【LC2392】

给你一个 正 整数 k ，同时给你：

• 一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [abovei, belowi] 和
• 一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti, righti] 。

两个数组里的整数都是 1 到 k 之间的数字。

你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。

矩阵还需要满足以下条件：

• 对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的 行 必须在数字 belowi 所在行的上面。
• 对于所有 0 到 m - 1 之间的下标 i ，数字 lefti 所在的 列 必须在数字 righti 所在列的左边。

返回满足上述要求的 任意 矩阵。如果不存在答案，返回一个空的矩阵。

• 思路

  • 通过rowConditions和 colConditions获得数字所在行和所在列的拓扑排序，如果不存在拓扑排序，那么返回空矩阵
  • 然后通过拓扑排序将数字填入相应位置，先遍历行的拓扑排序记录每个数字应填入的行，然后再遍历列拓扑，将每个数字填入对应的位置

• 实现

  class Solution {
      public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
          int[] rowOrder = topoSort(k, rowConditions);
          int[] colOrder = topoSort(k, colConditions);
          if (rowOrder.length < k || colOrder.length < k) return new int[][]{};
          int[][] res = new int[k][k];
          int[] pos = new int[k + 1];// 记录数字i位于的行
          for (int i = 0; i < k; i++){
              pos[rowOrder[i]] = i;
          }
          for (int i = 0; i < k; i++){
              res[pos[colOrder[i]]][i] = colOrder[i];
          }
          return res;
      }
      public int[] topoSort(int k, int[][] edges){
          List<Integer>[] g = new List[k + 1];
          Arrays.setAll(g, e -> new ArrayList<>());
          int[] inDeg = new int[k + 1];
          Deque<Integer> q = new LinkedList<>();
          List<Integer> res = new ArrayList<>();
          for (int[] edge : edges){
              int u = edge[0], v = edge[1];
              g[u].add(v);
              inDeg[v]++;
          }
          for (int i = 1; i <= k; i++){
              if (inDeg[i] == 0){
                  q.addLast(i);
              }
          }
          while(!q.isEmpty()){
              int u = q.pollFirst();
              res.add(u);
              for (int v : g[u]){
                  if (--inDeg[v] == 0){
                      q.addLast(v);
                  }
              }
          }
          return res.stream().mapToInt(x -> x).toArray();
      }
  }
  

  • 复杂度

    • 时间复杂度：$O(E+V)$，$E$表示邻边的跳数，V为结点的个数

    • 空间复杂度：$O(V)$

收集树中金币【LC2603】

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

• 收集距离当前节点距离为 2 以内的所有金币，或者
• 移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

• 思路：拓扑排序

  • 首先，我们可以去掉不包含金币的子树，因为访问其中任何一个点都毫无意义。
  • 如果所有在叶子上的金币全部都能收集到，那么我们可以收集到树上所有金币。因此可以去除两轮叶子，剩余的结点即为必须经过的结点【两轮拓扑排序】
  • 从距离叶子为2的节点处出发【局部最优】，收集树中所有的金币，并且回到出发节点时经过的边数最少【全局最优】。

• 实现

  • 无向图，节点度为1时为叶子

  class Solution {
      public int collectTheCoins(int[] coins, int[][] edges) {
          int n = coins.length;
          List<Integer> g[] = new ArrayList[n];
          Arrays.setAll(g, e -> new ArrayList<>());
          var deg = new int[n];
          for (var e : edges) {
              int x = e[0], y = e[1];
              g[x].add(y);
              g[y].add(x); // 建图
              ++deg[x];
              ++deg[y];
          }
  
          // 用拓扑排序「剪枝」：去掉没有金币的子树
          var q = new ArrayDeque<Integer>();
          for (int i = 0; i < n; ++i)
              if (deg[i] == 1 && coins[i] == 0) // 无金币叶子
                  q.add(i);
          while (!q.isEmpty()) {
              int x = q.peek();
              q.pop();
              for (int y : g[x])
                  if (--deg[y] == 1 && coins[y] == 0)
                      q.add(y);
          }
  
          // 再次拓扑排序
          for (int i = 0; i < n; ++i)
              if (deg[i] == 1 && coins[i] == 1) // 有金币叶子
                  q.add(i);
          if (q.size() <= 1) return 0; // 至多一个有金币的叶子，直接收集
          var time = new int[n];
          while (!q.isEmpty()) {
              int x = q.peek();
              q.pop();
              for (int y : g[x])
                  if (--deg[y] == 1) {
                      time[y] = time[x] + 1; // 记录入队时间
                      q.add(y);
                  }
          }
  
          // 统计答案
          int ans = 0;
          for (var e : edges)
              if (time[e[0]] >= 2 && time[e[1]] >= 2)
                  ans += 2;
          return ans;
      }
  }
  
  作者：灵茶山艾府
  链接：https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/2191371/tuo-bu-pai-xu-ji-lu-ru-dui-shi-jian-pyth-6uli/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

  • 复杂度

    • 时间复杂度：$O(E+V)$，$E$表示邻边的跳数，V为结点的个数

    • 空间复杂度：$O(V)$

• 升级：如果把题目中的 2 换成 0,1,2,3,⋯ ,n−1，你能把这些情况对应的答案全部算出来吗？
  遍历所有的边，如果两个节点的入队时间均大于q（最大距离），那么表示这条边必须要经过，结果+2