目录
前言：
算法解析
Kahn算法
DFS算法
总结：
参考资料
前言：
如何确定代码源文件的编译依赖关系？
我们知道，一个完整的项目往往会包含很多代码源文件 。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件 。比如，A.cpp 依赖 B.cpp，那在编译的时候，编译器需要先编译 B.cpp，才能编译 A.cpp 。
编译器通过分析源文件或者程序员事先写好的编译配置文件（比如文件），来获取这种局部的依赖关系 。那编译器又该如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序呢？
算法解析
这个问题的解决思路与“图”这种数据结构的一个经典算法“拓扑排序算法”有关 。那什么是拓扑排序呢？这个概念很好理解，我们先来看一个生活中的拓扑排序的例子 。
我们在穿衣服的时候都有一定的顺序，我们可以把这种顺序想成，衣服与衣服之间有一定的依赖关系 。比如说，你必须先穿袜子才能穿鞋，先穿内裤才能穿秋裤 。假设我们现在有八件衣服要穿，它们之间的两两依赖关系我们已经很清楚了，那如何安排一个穿衣序列，能够满足所有的两两之间的依赖关系？
拓扑排序的原理非常简单，我们的重点应该放到拓扑排序的实现上面 。
算法是构建在具体的数据结构之上的 。针对这个问题，我们先来看下，如何将问题背景抽象成具体的数据结构？
我们可以把源文件与源文件之间的依赖关系，抽象成一个有向图 。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边 。
如果 a 先于 b 执行，也就是说 b 依赖于 a，那么就在顶点 a 和顶点 b 之间，构建一条从 a 指向 b 的边 。而且，这个图不仅要是有向图，还要是一个有向无环图，也就是不能存在像 a->b->c->a 这样的循环依赖关系 。因为图中一旦出现环，拓扑排序就无法工作了 。实际上，拓扑排序本身就是基于有向无环图的一个算法 。
具体代码如下：
public class Graph {private int v; // 顶点的个数private LinkedList adj[]; // 邻接表public Graph(int v) {this.v = v;adj = new LinkedList[v];for (int i=0; i();}}public void addEdge(int s, int t) { // s先于t，边s->tadj[s].add(t);}}
拓扑排序有两种实现方法，都不难理解 。它们分别是 Kahn 算法和 DFS 深度优先搜索算法 。我们依次来看下它们都是怎么工作的 。
Kahn算法
Kahn 算法实际上用的是贪心算法思想，思路非常简单、好懂 。
定义数据结构的时候，如果 s 需要先于 t 执行，那就添加一条 s 指向 t 的边 。所以，如果某个顶点入度为 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->winDegree[w]++;}}LinkedList queue = new LinkedList<>();for (int i = 0; i < v; ++i) {if (inDegree[i] == 0) queue.add(i);}while (!queue.isEmpty()) {int i = queue.remove();System.out.print("->" + i);for (int j = 0; j