我们知道，一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件。比如，A.cpp 依赖 B.cpp，那在编译的时候，编译器需要先编译 B.cpp，才能编译 A.cpp。编译器通过分析源文件或者程序员事先写好的编译配置文件（比如 Makefile 文件）来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序呢？
image.png
这个问题的解决思路与“图”这种数据结构的一个经典算法“拓扑排序算法”有关。我们先来看一个生活中的拓扑排序的例子。我们在穿衣服的时候都有一定的顺序，我们可以把这种顺序想成，衣服与衣服之间有一定的依赖关系。比如说，你必须先穿袜子才能穿鞋，先穿内裤才能穿秋裤。

假设我们现在有八件衣服要穿，它们之间的两两依赖关系我们已经很清楚了，那如何安排一个穿衣序列，能够满足所有的两两之间的依赖关系？这就是个拓扑排序问题。从这个例子中，你应该能想到，在很多时候，拓扑排序的序列并不是唯一的。如下图所示，存在多种满足这些局部先后关系的穿衣序列。
image.png
实际上，拓扑排序的原理非常简单，我们的重点应该放到拓扑排序的实现上面。针对这个问题，我们先来看下，如何将问题背景抽象成具体的数据结构？

算法实现

我们可以把源文件之间的依赖关系，抽象成一个有向图。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。如果 a 先于 b 执行，也就是说 b 依赖于 a，那么就在顶点 a 和顶点 b 之间，构建一条从 a 指向 b 的边。而且，这个图不仅要是有向图，还要是一个有向无环图，也就是不能存在像 a->b->c->a 这样的循环依赖关系。因为图中一旦出现环，拓扑排序就无法工作了。实际上，拓扑排序本身就是基于有向无环图（DAG）的一个算法。

  1. public class Graph {
  3.     private int v; // 顶点的个数
  4.     private LinkedList<Integer>[] adj; // 邻接表
  6.     public Graph(int v) {
  7.         this.v = v;
  8.         adj = new LinkedList[v];
  9.         for (int i = 0; i < v; ++i) {
  10.             adj[i] = new LinkedList<>();
  11.         }
  12.     }
  14.     public void addEdge(int s, int t) { // s先于t，边s->t
  15.         adj[s].add(t);
  16.     }
  17. }

现在，我们来看下，如何在这个有向无环图上，实现拓扑排序？实际上，拓扑排序有两种实现方法，它们分别是 Kahn 算法和 DFS 深度优先搜索算法。我们依次来看下它们都是怎么工作的。

1. Kahn 算法

Kahn 算法实际上用的是贪心算法思想，在定义数据结构的时候，如果 s 需要先于 t 执行，那就添加一条 s 指向 t 的边。所以，如果某个顶点入度为 0， 即没有任何顶点必须先于这个顶点执行，那这个顶点就可以执行了。

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

  1. /**
  2.  * Kahn算法，先加载入度为0的顶点，在加载依赖该顶点的顶点
  3.  */
  4. public void topoSortByKahn() {
  5.     // 计算每个顶点的入度，即顶点所依赖的其他顶点
  6.     int[] inDegree = new int[v];
  7.     for (int i = 0; i < v; i++) {
  8.         for (int j = 0; j < adj[i].size(); j++) {
  9.             int w = adj[i].get(j);
  10.             inDegree[w]++;
  11.         }
  12.     }
  13.     // 先取入度为0的进行计算，即不需要依赖其他顶点的顶点
  14.     LinkedList<Integer> queue = new LinkedList<>();
  15.     for (int i = 0; i < v; i++) {
  16.         if (inDegree[i] == 0) {
  17.             queue.add(i);
  18.         }
  19.     }
  20.     // 从入度为0的顶点中加载依赖该顶点的其他顶点
  21.     while (!queue.isEmpty()) {
  22.         int i = queue.remove();
  23.         System.out.print("->" + i);
  24.         for (int j = 0; j < adj[i].size(); j++) {
  25.             // 依赖该顶点的其他顶点入度减一
  26.             int k = adj[i].get(j);
  27.             inDegree[k]--;
  28.             // 如果出度以后为0，表示该顶点所依赖的顶点都加载完了，此时加载该顶点
  29.             if (inDegree[k] == 0) {
  30.                 queue.add(k);
  31.             }
  32.         }
  33.     }
  34. }

2. DFS 算法

实际上，拓扑排序也可以用深度优先搜索来实现。不过这里的名字要稍微改下，更加确切的说法应该是深度优先遍历，遍历图中的所有顶点，而非只是搜索一个顶点到另一个顶点的路径。代码实现如下：

  1. /**
  2.  * DFS深度优先搜索，遍历所有顶点，如果该顶点依赖其他顶点，则递归加载其他顶点
  3.  */
  4. public void topoSortByDFS() {
  5.     // 先构建逆邻接表，边s->t表示，s依赖于t，t先于s，逆邻接表表示顶点所依赖了哪些顶点
  6.     LinkedList<Integer>[] inverseAdj = new LinkedList[v];
  7.     for (int i = 0; i < v; i++) {
  8.         inverseAdj[i] = new LinkedList<>();
  9.     }
  10.     for (int i = 0; i < v; i++) {
  11.         for (int j = 0; j < adj[i].size(); j++) {
  12.             int w = adj[i].get(j);
  13.             inverseAdj[w].add(i);
  14.         }
  15.     }
  16.     boolean[] visited = new boolean[v];
  17.     // 深度优先遍历图
  18.     for (int i = 0; i < v; i++) {
  19.         if (!visited[i]) {
  20.             visited[i] = true;
  21.             dfs(i, inverseAdj, visited);
  22.         }
  23.     }
  24. }
  26. private static void dfs(int i, LinkedList<Integer>[] adj, boolean[] visited) {
  27.     for (int j = 0; j < adj[i].size(); j++) {
  28.         int w = adj[i].get(j);
  29.         if (!visited[w]) {
  30.             visited[w] = true;
  31.             dfs(w, adj, visited);
  32.         }
  33.     }
  34.     // 逆邻接表为空，表示该顶点不依赖其他顶点，直接输出
  35.     System.out.print("->" + i);
  36. }

这个算法包含两个关键部分。第一部分是通过邻接表构造逆邻接表。邻接表中，边 s->t 表示 s 先于 t 执行，也就是 t 要依赖 s。在逆邻接表中，边 s->t 表示 s 依赖于 t，s 后于 t 执行。为什么这么转化呢？这个跟我们这个算法的实现思想有关。在 DFS 算法中，我们优先找出没有后继依赖的节点，把它作为最后执行的节点，这样一定可以保证在 DAG 中的拓扑排序中它是安全的，因为所有它依赖的节点一定在它之前执行。即 DFS 算法采用先输出依赖自己的节点、再输出自己的策略来保证拓扑排序。

第二部分是这个算法的核心，也就是递归处理每个顶点。对于顶点 i 来说，我们先输出它可达的所有顶点，也就是说，先把它依赖的所有的顶点输出了，然后再输出自己。而数组 visited 用来标记某个节点是不是已经遍历过；只要是遍历过的节点，就不再重复遍历。

总结

下面来看下，这两个算法的时间复杂度分别是多少呢？从 Kahn 代码中可以看出来，每个顶点被访问了一次，每个边也都被访问了一次，所以，Kahn 算法的时间复杂度就是 O(V+E)（V 表示顶点个数，E 表示边的个数）。而在 DFS 算法中每个顶点被访问两次，每条边被访问一次，所以时间复杂度也是 O(V+E)。注意，由于这里的图可能不是连通的，有可能是有好几个不连通的子图构成，所以，E 并不一定大于 V，两者的大小关系不确定。所以，在表示时间复杂度的时候，V、E 都要考虑在内。

拓扑排序应用非常广泛，解决的问题的模型也非常一致。凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决。除此之外，拓扑排序还能检测图中环的存在。对于 Kahn 算法来说，我们通过贪心算法把所有能输出到拓扑序的节点都输出，如果最后输出的顶点个数少于图中顶点个数，且图中还有入度不是 0 的顶点，则说明图中存在环。而在 DFS 算法中，如果在 DFS 的过程中访问到一个已经被访问过且不是上一步之前被访问的节点，就说明环存在。