42拓扑排序：如何确定代码源文件的编译依赖关系

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

本节开始进入高级篇。相对于基础篇“开篇问题 - 知识讲解 - 回答开篇 - 总结 - 课后思考”这样的文章结构，高级篇的组织结构为“问题阐述 - 算法解析 - 总结引申 - 课后思考”。也就是高级篇会围绕一个实际软件开发的问题，在阐述具体解决方法的过程中，将涉及的知识点给你详细讲解出来。

本节主要解决的问题是，如何确定代码源文件的编译依赖关系？一个完整的项目往往有很多代码源文件。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件。比如，A.cpp 依赖 B.cpp，那在编译的时候，编译器需要先编译 B.cpp，才能编译 A.cpp。

编译器通过分析源文件或者程序员事先写好的编译配置文件（比如Makefile文件），来获得局部依赖关系。对于前者，那编译器该如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序呢？

算法解析

这个问题的解决思路与“图”这种数据结构的一个经典算法“拓扑排序算法”有关。那什么叫做拓扑排序呢？

其实，生活中穿衣服时因为衣服与衣服之间有一定的依赖关系，所以穿衣都有一定的顺序。比如必须先穿袜子才能穿鞋，先穿内裤才能穿秋裤。假设我们现在有八件衣服要穿，它们之间的两两依赖关系我们已经很清楚了，那如何安排一个穿衣序列，能够满足所有的两两之间的依赖关系？这其实就是一个拓扑排序问题，从这个例子可以发现，拓扑排序的序列并不是唯一的。如下所示：

开篇问题和这个问题一样，可以抽象成一个拓扑排序问题。拓扑排序的原理非常简单，我们重点在于拓扑排序的实现上面。而算法是构建在具体的数据结构上的，那这个问题应该抽象成什么数据结构呢？

可以把源文件与源文件之间的依赖关系，抽象成一个有向图。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。如果 b 依赖于 a，即 a 先于 b 执行，则构建一条从 a 指向 b 的边。而且这个图不仅要是有向图，还要是有向无环图，也就是不能存在从 a->b->c->a 这样的循环依赖关系，否则拓扑排序就无法工作了。实际上，拓扑排序本身就是基于有向无环图的一个算法。数据结构的定义如下：

public class Graph {
  private int v; // 顶点的个数
  private LinkedList<Integer> adj[]; // 邻接表

  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) {
      adj[i] = new LinkedList<>();
    }
  }

  public void addEdge(int s, int t) { // s先于t，边s->t
    // 存储的并不是完整的二维数组，只存储了连接关系
    adj[s].add(t);
  }
}

拓扑排序有 Kahn 算法和 DFS 深度优先搜索算法两种实现方法。

Kahn 算法

Kahn 算法实际上使用的是贪心算法。从数据结构中发现，若一个顶点入度为0，则没有任何顶点必须先于这个顶点执行，那么这个顶点就可以执行了。

所以，先从图中找出一个入度为 0 的顶点，将其输出到拓扑排序的结果序列中（对应代码中就是把它打印出来），并且把这个顶点从图中删除（也就是把这个顶点可达的顶点的入度都减 1）。循环执行上述过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。这个过程对应的代码如下：

public void topoSortByKahn() {
  int[] inDegree = new int[v]; // 统计每个顶点的入度
  for (int i = 0; i < v; ++i) {
    for (int j = 0; j < adj[i].size(); ++j) {
      int w = adj[i].get(j); // i->w
      inDegree[w]++;
    }
  }
  LinkedList<Integer> queue = new LinkedList<>();
  // 统计一开始入度就是0的顶点，添加到队列queue中
  for (int i = 0; i < v; ++i) {
    if (inDegree[i] == 0) queue.add(i);
  }
  while (!queue.isEmpty()) {
    // 依次让入度为0的顶点出队，也就是把这个顶点从图中删除，然后这个顶点可达的顶点入度都减1
    int i = queue.remove();
    System.out.print("->" + i);
    for (int j = 0; j < adj[i].size(); ++j) {
      int k = adj[i].get(j);
      inDegree[k]--;
      // 若这个顶点的入度为0，则添加到队列中
      if (inDegree[k] == 0) queue.add(k);
    }
  }
}

DFS 深度优先搜索算法

之前讲的图上的深度优先搜索只是搜索一个顶点到另一个顶点的路径，而针对这个问题的深度优先遍历，需要遍历图中的所有顶点。对应的代码如下：

public void topoSortByDFS() {
  // 先构建逆邻接表，边s->t表示，s依赖于t，t先于s
  LinkedList<Integer> inverseAdj[] = new LinkedList[v];
  for (int i = 0; i < v; ++i) { // 申请空间
    inverseAdj[i] = new LinkedList<>();
  }
  for (int i = 0; i < v; ++i) { // 通过邻接表生成逆邻接表
    for (int j = 0; j < adj[i].size(); ++j) {
      int w = adj[i].get(j); // i->w
      inverseAdj[w].add(i); // w->i
    }
  }
  boolean[] visited = new boolean[v]; // 记录是否遍历过
  for (int i = 0; i < v; ++i) { // 深度优先遍历图
    if (visited[i] == false) {
      visited[i] = true;
      dfs(i, inverseAdj, visited);
    }
  }
}

private void dfs(int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
  for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
    int w = inverseAdj[vertex].get(i);
    if (visited[w] == true) continue;
    visited[w] = true;
    dfs(w, inverseAdj, visited);
  } // 先把vertex这个顶点可达的所有顶点都打印出来之后，再打印它自己
  System.out.print("->" + vertex);
}

这个算法包含两个关键部分。

第一部分是通过邻接表构造逆邻接表。邻接表中，边 s->t 表示 s 先于 t 执行；在逆邻接表中，边 s->t 表示 s 后于 t 执行。

第二部分是算法的核心，也就是递归处理每个顶点。对于顶点 vertex 来说，先输出它可达的所有顶点。也就是先把它依赖的所有的顶点输出了，然后再输出自己。

那么，Kahn 算法和 DFS 算法的时间复杂度分别是多少呢？

从 Kahn 代码看出，每个顶点被访问了一次，每个边也被访问了一次，所以，Kahn 算法的时间复杂度就是 O(V+E)（V 表示顶点个数，E 表示边的个数）。
DFS 算法中，每个顶点被访问两次，每条边都被访问一次，所以时间复杂度也是 O(V+E)。

注意，这里的图可能不是连通的，有可能是有好几个不连通的子图构成，所以，E 并不一定大于 V，两者的大小关系不确定。所以，在表示时间复杂度的时候，V、E 都要考虑在内。

总结引申

除了前面讲过的关于“图”的定义和存储、图的广度和深度优先搜索外，本节又学习了一个关于图的算法，拓扑排序。

拓扑排序广泛适用于这样的问题：凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决。

除此之外，拓扑排序还能检测图中环的存在。对于 Kahn 算法来说，如果最后输出出来的顶点个数，少于图中顶点个数，说明图中还有入度不是 0 的顶点，即图中存在环。

关于图中环的检测，递归小节讲过一个例子。由于存在脏数据，在查找最终推荐人时，会造成循环推荐。比如A推荐了B，B推荐了C，C推荐了A。那如何避免这种脏数据导致的无限递归呢？实际上，这就是环的检测问题。

首先，考虑简单的一种情况，每次都只是查找一个用户的最终推荐人。这时不需要动用复杂的拓扑排序算法，只需要记录已经访问过的用户 ID，当用户 ID 第二次被访问的时候，就说明存在环，也就说明存在脏数据。例如，查找A的最终联系人时，会依次给A、B、C打上已经访问过的标记；若继续查找C的最终联系人，则会查到A，此时就会发现A已经被访问过了。

HashSet<Integer> hashTable = new HashSet<>(); // 保存已经访问过的actorId
long findRootReferrerId(long actorId) {
  if (hashTable.contains(actorId)) { // 存在环
    return;
  }
  hashTable.add(actorId);
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  return findRootReferrerId(referrerId);
}

接着考虑复杂点的情况，已经知道了数据库中所有用户之间的推荐关系。检测有没有存在环的情况。这时需要用到拓扑排序算法了。把用户之间的推荐关系，从数据库中加载到内存中，然后构建成本节讲的这种有向图数据结构，再利用拓扑排序，就可以快速检测出是否存在环了。

课后思考

本节用图表示依赖关系时，如果 a 先于 b 执行，则画出从 a 到 b的有向边。若采用如果 a 先于 b执行，则画出从 b 到 a的有向边。那么今天讲的 Kahn 算法和 DFS 算法能正确工作么？
答：对于 DFS 算法能正常运行；对于 Kahn 算法，之前找的是入度为0的节点删除，这时只需要找出度为0的节点删除即可。
用BFS广度优先搜索算法，可以实现本节的算法么？
答：BFS也能实现，因为遍历只是实现拓扑排序的一个“辅助手段”，本质上是帮助找到优先执行的顶点。