Install Dependencies

给定软件之间安装的依赖关系，用一个二维数组表示，第一维表示依赖的序号，第二维表示依赖关系，比如要先装deps[0][0]，才能装deps[0][1]。安装时，要尽可能先安装依赖个数少的软件。求安装顺序。

拓扑排序

复杂度

时间 O(1) 空间 O(1)

思路

本题和Course Schedule的解法一样，不会拓扑排序的可以参考那篇文章。区别在于我们拓扑排序后的访问顺序，本来我们是用一个Queue来进行BFS，这里为了让依赖少的先安装，我们将Queue换成PriorityQueue，并以依赖数排序。用优先队列遍历图，很像是Cost based search 或者greedy，a star这种算法。注意，由于可能出现两个软件有同样依赖数的情况，比如两个软件剩余依赖都是0的时候，应该先装哪个呢？这个就要和面试官讨论了，可以在软件的数据结构中加入timestamp或者总依赖数等变量，供我们在ProrityQueue中作为第二个、第三个条件来比较。

代码

public class InstallDependencies {    public static void main(String[] args){        String[][] deps = {{"gcc", "gdb"},{"gcc", "visualstudio"},{"windows", "gcc"}        , {"windows", "sublime"}, {"libc", "gcc"}, {"libc2", "gcc"}, {"unix", "cat"}        , {"windows", "libc"}, {"windows", "libc2"}, {"linux", "cat"}, {"windows", "cat"}        , {"solaris", "cat"}, {"macos","cat"}};        InstallDependencies id = new InstallDependencies();        id.install(deps, 7);    }        public void install(String[][] deps, int n){        HashMap<String, Software> map = new HashMap<String,Software>();        // 根据依赖关系建图        for(String[] dep : deps){Software src = map.get(dep[0]);Software dst = map.get(dep[1]);if(src == null){    src = new Software(dep[0]);}if(dst == null){    dst = new Software(dep[1]);}src.targets.add(dst);dst.deps = dst.deps + 1;map.put(dep[0], src);map.put(dep[1], dst);        }        // 用一个优先队列来遍历我们的图        PriorityQueue<Software> pq = new PriorityQueue<Software>(11 ,new Comparator<Software>(){public int compare(Software s1, Software s2){    return s1.deps - s2.deps;}        });        for(String name : map.keySet()){if(map.get(name).deps == 0){    pq.offer(map.get(name));}        }        while(!pq.isEmpty()){Software curr = pq.poll();System.out.println(curr.name);for(Software dst : curr.targets){    dst.deps = dst.deps - 1;    if(dst.deps == 0){        pq.offer(dst);    }}        }    }}class Software{    String name;    int deps;    ArrayList<Software> targets;    public Software(String name){        this.deps = 0;        this.name = name;        this.targets = new ArrayList<Software>();    }}