聊聊拓扑排序算法

起因

最近在项目上实现功能时,遇到了一个需求,需要把一个 excel 里的数据按照一定规则转换成 sql,用的实现方法与之前一篇博客 Attribute + TypeConverter 实现 Excel To Json 中的思想类似,使用 attribute (java 里叫 annotation) 来在 model 上标记 property 与 excel 列名的对应关系,但是在分析 excel 时遇到了更复杂的情况,某一列的验证规则需要基于其他列的值,因此在转换列值的时候需要考虑列与列之间的依赖关系,被依赖的列需要先转换。这就需要一种算法来对列的转换顺序进行排序,把被依赖的列放在转换序列的前面,把有依赖的列放在转换序列的后面,这样只要按照这个转换序列来依次转换所有的列,就不会有问题了,举个例子,假如我的 excel 里有 A B C D 4列,其中 A 列的值在验证时需要 判断 D 列的值,假设 D 的值为 true,需要 A 的值为 1, 假设 D 的值为 false,需要 A 的值为 2,也就是说 A 的值需要 D 的值为前提条件进行判断,所以在转换的时候我们需要先转换 D 后转换 A,因此理想的转换序列应该是 D A B C

从另一个角度说,我们也需要一个算法来检查我的 attribute 里是否出现了由于错误引起的循环依赖问题。还是上面的例子,假如 A 依赖 D 的值, D 依赖 C 的值,C 依赖 A 的值,就形成了一个循环依赖
C -> D -> A -> C
这种情况下是无法进行解析的,应该检查是否有逻辑错误。

在网上搜索时发现 拓扑排序算法 刚好就是用来分析各个任务之间的依赖关系,并且能过分析出各个任务之间有没有循环引用的情况,下面来聊聊拓扑排序算法

什么是拓扑排序

拓扑排序(Topological Sorting)是一种把有向无环图(DAG, Directed Acyclic Graph)转换成线性序列的排序算法,算法的输入是一个 有向无环图,经过算法分析把图中的所有节点按照先后顺序(依赖关系)进行拆解,最后得到一个有顺序的队列,在前(被依赖)的节点靠前,越靠后的节点或有多个节点指向该节点,那这个节点在队列中的位置就越靠后。

看下面这个例子

节点 5 和 4 不依赖任何节点,因此在输出队列里也靠前,而 0 和 1 分别有 2 个依赖的节点,因此需要靠后处理,经过拓扑排序后的结果:
5 4 2 3 1 0

需要注意的是拓扑排序的结果可能不唯一,起点通常是一个入度为 0 的节点

下面两种排序结果都是正确的:
5 4 2 3 1 0

4 5 2 3 0 1

入度

这里出现了一个新的概念–入度,入度指的是以该节点为终点的边的数量

上图的 0 和 1 节点 的入度为 2,5 和 4 的入度为 0,2 和 3 的入度为 1

有向无环图

引自维基百科,在图论中,如果一个有向图从任意顶点出发无法经过若干条边回到该点,则这个图是一个有向无环图(DAG,directed acyclic graph)

有向 指的是节点之间的边是有方向的,从一个节点到另一个节点,例如 A -> B,我们可以理解为 B 对 A有依赖,要完成 B 需要先完成 A。

无环 指的是不存在从一个节点出发,最终又回到当前节点的路径。

回到上面的例子,
C -> D -> A -> C
从 C 出发最后又回到了 C,就形成了一个环,代表出现了循环依赖

算法思路

我们可以把排序的过程看做是解依赖的过程,

  1. 把所有没有依赖的节点(入度为 0)放进一个队列
  2. 从队列拿出一个节点,从图中拿掉这个节点(相当于这个任务完成了),同时拿掉它指向别的节点的边,把它指向的节点的入度减 1,如果它指向的节点 入度变为 0(没有依赖了),则把该节点放入队列
  3. 重复第 2 步,直到所有的节点都从图上拿走
  4. 把节点从图上拿走的顺序,就是最终输出的序列

用一张图来表示这个过程,图中的红色数字表示入度

  1. 找到入度为 0 的节点 1
  2. 拿掉 节点 1,此时 节点 2 的入度变为 0,4 的入度变成 1
  3. 拿掉 节点 2,节点 3 的入度变为 1, 节点 4 的入度为 0
  4. 拿掉 节点 4,节点 3 的入度为 0,节点 5 的入度为 1
  5. 拿掉 节点 3,节点 5 的入度为 0
  6. 拿掉 节点 5,结束


最后的输出顺序:
1 2 4 3 5

判断环

如果有环存在,则在不断拿掉点的过程中,出现图上还有节点,但是无法找到入度为 0 的点, 看下面这个图

图中 B-C—E 是一个环,我们看看当只剩 B-C—E 3 个节点时各个节点的入度情况

根据拓扑排序算法,需要找到当前图中所有入度为 0 的节点,依次放入队列并去掉这个节点,把它的边指向的节点入度减 1,但此时 B C E 的入度都为 1,不存在入度为 0 的点,因此算法无法进行下去,所以我们只要判断当入度为 0 的队列为空之后,已经拿掉的节点的个数与原来的节点总个数是否相等,如果相等则表示全部处理完,如果不想等表示有图存在,上图的例子中,拿掉的节点数为 2 (AD),此时图上已经不存在入度为 0 的点,但是顶点总数为 5,与 2 不相等,因此说明图中存在环

算法实现

class Graph {
    Map<String, List<String>> referenceMap; //存放边
    Queue<String> nodeQueue; //用于放入度为 0 的节点
    Map<String, Integer> nodeIndegreeMap; //存放节点和入度

    List<String> topologicalSort() {
      List<String> result = new ArrayList<>();
      for (String nodeName : nodeIndegreeMap.keySet()) {
        if (nodeIndegreeMap.get(nodeName) == 0) {
          nodeQueue.add(nodeName);
        }
      }

      int count = 0;
      while (!nodeQueue.isEmpty()) {
        String node = nodeQueue.poll();
        result.add(node);
        count++;
        for (String c : referenceMap.get(node)) {
          int indegree = nodeIndegreeMap.get(c) - 1;
          nodeIndegreeMap.replace(c, indegree);
          if (indegree == 0) {
            nodeQueue.add(c);
          }
        }
      }

      if (count < referenceMap.size()) {
        String restNodes = nodeIndegreeMap.keySet().stream().filter(k -> !result.contains(k))
            .collect(
                Collectors.joining(","));
        throw new IllegalArgumentException(
            "there are loop reference in the graph, check the config for nodes: "
                + restNodes);
      }

      return result;
    }
  }

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.