[Algo] Install Dependencies 安装依赖 - SegmentFault
给定软件之间安装的依赖关系,用一个二维数组表示,第一维表示依赖的序号,第二维表示依赖关系,比如要先装
本题和Course Schedule的解法一样,不会拓扑排序的可以参考那篇文章。区别在于我们拓扑排序后的访问顺序,本来我们是用一个Queue来进行BFS,这里为了让依赖少的先安装,我们将Queue换成PriorityQueue,并以依赖数排序。用优先队列遍历图,很像是Cost based search 或者greedy,a star这种算法。注意,由于可能出现两个软件有同样依赖数的情况,比如两个软件剩余依赖都是0的时候,应该先装哪个呢?这个就要和面试官讨论了,可以在软件的数据结构中加入timestamp或者总依赖数等变量,供我们在ProrityQueue中作为第二个、第三个条件来比较。
给定软件之间安装的依赖关系,用一个二维数组表示,第一维表示依赖的序号,第二维表示依赖关系,比如要先装
deps[0][0]
,才能装deps[0][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>();
}
}
Read full article from [Algo] Install Dependencies 安装依赖 - SegmentFault