算法--拓扑排序

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

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->w
            inDegree[w]++;
        }
    }
    LinkedList<Integer> 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 < adj[i].size(); ++j) {
            int k = adj[i].get(j);
            inDegree[k]--;
            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);
}

这个算法包含两个关键部分。第一部分是通过邻接表构造逆邻接表。第二部分是这个算法的核心，也就是递归处理每个顶点。