有向图拓扑排序文件依赖下的编译顺序该如何确定？

有2种常用方式

1.kahn算法

2.基于深度优先的逆后序

都需要有向图中无环，否则依赖关系的顺序可能产生问题

若有文件 a.c b.c c.c d.c 他们之间的依赖关系是

a文件被b文件依赖，b文件被c文件依赖，b文件被d文件依赖
那么哪个文件被先编译？ 被依赖的最多的那个文件（a或d）应该被先编译。 如何得到正确的编译顺序？

a.c -> b.c -> c.c

d.c ->

1.kahn

//拓扑排序
//无环有向图 是 拓扑排序的前提

//拓扑排序后，顶点所依赖的前驱节点必定都先出现再他前面（这种序列叫做 拓扑序列）
//只要满足上述条件的排序输出，都是拓扑序列（所以一个图往往会有多个拓扑序）（这种排序过程叫做 拓扑排序）
//
//拓扑排序再生活中的应用，比如任务的依赖关系，被依赖的基层任务应该先完成，比如穿几件衣服，一定是先把穿在里面的衣服穿了以后，再穿外面的外套
public class TopologicalKahn {
    Digraph dg;
    List<Integer> order;                //顶点的拓扑顺序
    int[] inDegree;

    public TopologicalKahn(Digraph dg) {
        this.dg = dg;
        //Kahn 算法，获取拓扑排序
        //1.统计所有顶点入度
        //2.将入度为0的作为起点，加入到queue
        //3.从queue中取出顶点，直到队列为空，将该顶点所指向的顶点入度-1，如果入度=0，则加入队列，循环第三步

        //存在环时：输出的顶点数量少于有向图中的顶点数量，或到最后结束循环时，还存在有入度不为0的顶点

        order = new LinkedList<>();

        //1.
        inDegree = new int[dg.v()];
        for (int u = 0; u < dg.v(); u++) {
            for (int w : dg.adj(u)) {
                inDegree[w]++;
            }
        }

        //2.队列中按 成为0入度 的顺序加入顶点
        Queue<Integer> queue = new LinkedList<>();
        for (int u = 0; u < dg.v(); u++)
            if (inDegree[u] == 0)
                queue.add(u);

        //3.
        while (!queue.isEmpty()) {
            int u = queue.remove();
            order.add(u);
            for (int w : dg.adj(u)) {
                inDegree[w]--;
                if (inDegree[w] == 0)   //若入度不为0，说明还有其他指向该点的边
                    queue.add(w);
            }
        }

        //4.若最终输出的入度为0的顶点个数小于 原来有向图中顶点个数，说明存在环
        if(order.size() < dg.v())
            order = null;

        this.dg = null;
    }

    public boolean isDAG() {                //是有向无环图吗？
        return null != order;
    }

    public Iterable<Integer> getOrder() {
        return order;
    }

    public static void main(String[] args) {
        List<String> books = new LinkedList<>();
        books.add("a.c");
        books.add("b.c");
        books.add("c.c");
        books.add("d.c");
        SymblowDigraph sd = new SymblowDigraph(books);
        sd.addEdge("a.c", "b.c");
        sd.addEdge("b.c", "c.c");
        sd.addEdge("d.c", "b.c");


        //编译时 a文件被b文件依赖，b文件被c文件依赖，b文件被d文件依赖
        //那么哪个文件被先编译？ 被依赖的最多的那个文件（a或d）应该被先编译。 如何得到正确的编译顺序？
        // a.c -> b.c -> c.c
        // d.c ->

        Digraph dg = sd.getGraph();
        TopologicalKahn top = new TopologicalKahn(dg);
        if (top.isDAG()) {
            System.out.println("拓扑序列. 文件优先编译顺序（被依赖深度高的先被编译）");
            for (int i : top.getOrder()) {
                System.out.println(" " + sd.getSymblow(i));
            }
        }
    }
}

输出

拓扑序列. 文件优先编译顺序（被依赖深度高的先被编译）
 a.c
 d.c
 b.c
 c.c

2.深度优先+逆后序

//拓扑排序
//无环有向图 是 拓扑排序的前提

//拓扑排序后，顶点所依赖的前驱节点必定都先出现再他前面（这种序列叫做 拓扑序列）
//只要满足上述条件的排序输出，都是拓扑序列（所以一个图往往会有多个拓扑序）（这种排序过程叫做 拓扑排序）
//
//拓扑排序再生活中的应用，比如任务的依赖关系，被依赖的基层任务应该先完成，比如穿几件衣服，一定是先把穿在里面的衣服穿了以后，再穿外面的外套
public class Topological {
    Digraph dg;
    DirectedCycle dc;
    DFOrder dfo;
    Iterable<Integer> order;                //顶点的拓扑顺序

    public Topological(Digraph dg) {
        this.dg = dg;
        dc = new DirectedCycle(dg);
        if (!dc.hasCycle()) {               //若存在环，则不计算拓扑排序
            dfo = new DFOrder(dg);
            order = dfo.reversePost();      //拓扑排序会用到深度优先
        }
        this.dg = null;
    }

    public boolean isDAG() {                //是有向无环图吗？
        return null != order;
    }

    public Iterable<Integer> getOrder() {
        return order;
    }

    public static void main(String[] args) {
        List<String> books = new LinkedList<>();
        books.add("小鱼");
        books.add("泥巴");
        books.add("赵家六");
        books.add("虾子");
        books.add("大鱼");
        books.add("牧羊犬");
        books.add("饲料");
        books.add("廉价劳动力");
        SymblowDigraph sd = new SymblowDigraph(books);
        sd.addEdge("泥巴", "虾子");
        sd.addEdge("虾子", "小鱼");
        sd.addEdge("饲料", "小鱼");
        sd.addEdge("小鱼", "大鱼");
        sd.addEdge("小鱼", "廉价劳动力");
        sd.addEdge("小鱼", "牧羊犬");
        sd.addEdge("大鱼", "牧羊犬");
        sd.addEdge("廉价劳动力", "牧羊犬");
        sd.addEdge("大鱼", "赵家六");
        sd.addEdge("牧羊犬", "赵家六");
        sd.addEdge("廉价劳动力", "赵家六");
        //泥巴被虾子吃，虾子被小鱼吃，饲料被小鱼吃，小鱼被大鱼吃，小鱼被牧羊犬吃，小鱼被廉价劳动力吃，大鱼被牧羊犬吃，大鱼被赵家六吃，廉价劳动力被牧羊犬吃，牧羊犬被赵家六吃，廉价劳动力被赵家六吃
        //那么整个食物链的低端（被依赖）到顶端的关系是？

        Digraph dg = sd.getGraph();
        Topological top = new Topological(dg);
        if (top.isDAG()) {
            System.out.println("拓扑序列. 被依赖的靠近顶行(并行被依赖的话，前后顺序不重要)");
            for (int i : top.getOrder()) {
                System.out.println(" " + sd.getSymblow(i));
            }
        }
    }
}

产生逆后序

//基于深度优先的顶点排序
public class DFOrder {
    Digraph dg;
    boolean[] marked;
    Queue<Integer> pre;             //前序
    Queue<Integer> post;            //后序
    Stack<Integer> reversePost;     //逆后序

    public DFOrder(Digraph dg) {
        this.dg = dg;
        marked = new boolean[dg.v()];
        pre = new ArrayDeque<>();
        post = new ArrayDeque<>();
        reversePost = new Stack<>();
        for (int u = 0; u < dg.v(); u++) {
            if (!marked[u]) {
                dfs(u);
            }
        }
        this.dg = null;
    }

    private void dfs(int u) {
        pre.add(u);
        marked[u] = true;
        for (int v : dg.adj(u)) {
            if (!marked[v])
                dfs(v);
        }
        post.add(u);
        reversePost.add(u);
    }

    public Iterable<Integer> pre() {
        return pre;
    }

    public Iterable<Integer> post() {
        return post;
    }

    public Iterable<Integer> reversePost() {
        List<Integer> rpList = new ArrayList<>();
        while(reversePost.size() > 0){
            rpList.add(reversePost.pop());
        }
        return rpList;
    }

    public static void main(String[] args) {
    }
}

输出：

拓扑序列. 被依赖的靠近顶行(并行被依赖的话，前后顺序不重要)
 饲料
 泥巴
 虾子
 小鱼
 大鱼
 廉价劳动力
 牧羊犬
 赵家六

依赖

有向图 拓扑排序 文件依赖下的编译顺序该如何确定？

有向图拓扑排序文件依赖下的编译顺序该如何确定？