拓扑排序

拓扑排序的原理很简单，就是将一组数据之间存在局部依赖的数据按一定顺序执行，保证所有事件都能顺利执行，例如我们穿衣服的时候肯定是先穿内裤再传裤子，而不能反过来。
拓扑结构的实现是基于图来实现的，所有我们需要将问题抽象成为一张图，每个事件是一个顶点，图直接的依赖关系就是边，如b依赖于a,则话一条由a指向b的边。
我们把图定义如下：

class Graph{
    private int v; //vertex number
    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<Integer>();
        }
    }

    public void addEdge(int s, int t){
        adj[s].add(t);
    }
}

有可图的定义之后我们来看两种实现方式：
Kahn算法：
Kahn算法的思想就是贪心算法，如果s先与t执行，那就添加一条s指向t的边。如果某个顶点入度为0就表示没有任何顶点先于这个顶点执行，那么这个顶点就是可执行顶点。
我们执行的时候，先从图中找一个入度为0的顶点输出，然后将该顶点从图中删除，这是所有这个顶点指向的顶点的入度都减一，然后再找下一个入度为0的顶点做同样的操作，知道所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序

public void topoSortByKahn() {
        //calculate all vetex's degree
        int[] inDegree = new int[v];
        for (int i = 0; i < inDegree.length; i++) {
            inDegree[i] = 0;
        }
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                int v = adj[i].get(j);
                inDegree[v]++;
            }
        }
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < v; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int v = queue.remove();
            System.out.print(v + "->");
            for (int i = 0; i < adj[v].size(); i++) {
                inDegree[adj[v].get(i)]--;
                if (inDegree[adj[v].get(i)] == 0) {
                    queue.add(adj[v].get(i));
                }
            }
        }
    }

深度优先搜索算法实现：
通过某个节点找到它依赖的节点，然后再找到它依赖的节点依赖的节点，依次类推知道找到一个节点不依赖任何节点。这样当某个节点依赖的所有节点都输出之后再输出该节点。

public void topoSortByDFS() {
        LinkedList<Integer>[] inverse = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            inverse[i] = new LinkedList<Integer>();
        }
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                inverse[adj[i].get(j)].add(i);
            }
        }

        boolean[] visited = new boolean[v];
        for (int i = 0; i < v; i++) {
            visited[i] = false;
        }
        for (int i = 0; i < v; i++) {
            if (visited[i] == false) {
                visited[i] = true;
                dfs(i, visited, inverse);
            }
        }
    }