[Java]聊聊拓扑排序算法

起因
什么是拓扑排序
入度
有向无环图
算法思路
判断环
算法实现

起因

最近在项目上实现功能时，遇到了一个需求，需要把一个 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，就形成了一个环，代表出现了循环依赖

算法思路

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

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

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

找到入度为 0 的节点 1
拿掉节点 1，此时节点 2 的入度变为 0，4 的入度变成 1
拿掉节点 2，节点 3 的入度变为 1，节点 4 的入度为 0
拿掉节点 4，节点 3 的入度为 0，节点 5 的入度为 1
拿掉节点 3，节点 5 的入度为 0
拿掉节点 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;
    }
  }

0 0 votes

Article Rating