和 力扣207.课程表 相似
- 循环依赖检测。如,[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] => false,[['A', 'B'], ['B', 'C'], ['C', 'A']] => true(2021.4 字节跳动-幸福里-后端)
- 手撕代码:小王写了一个makefile,其中有n个编译项编号为0~n-1,他们互相之间有依赖关系。请写一个程序解析依赖,给出一个可行的编译顺序。(2021.03 字节跳动-系统部-后端)
解决这类问题的利器就是——拓扑排序。
拓扑排序算法过程:
-
选择图中一个入度为0的点,记录下来
-
在图中删除该点和所有以它为起点的边
-
重复1和2,直到图为空或没有入度为0的点。
若给定一个依赖关系是[[0,2],[1,2],[2,3],[2,4]],如图所示。
选择入度为0的节点,比如选择点0
,记录至res;删除点0
及以它为起点的边。
然后选择点1
,同样记录下来;删除点1
及以它为起点的边。
入度为0的点现在只有点2,把它记录下来;删除点2
及以它为起点的边。
同理。选择点3
,记录下来;删除点3
及以它为起点的边。
选择点4
,记录下来;删除点4
及以它为起点的边。
如果是循环依赖,可以使用res.size() == n
来判断图中是否有环。其中,n为点的个数。
public List<Integer> haveCircularDependency(int n, int[][] prerequisites){
int[] inArray=new int[n];
List<List<Integer>> list=new LinkedList<>();
List<Integer> res=new LinkedList<>();
Queue<Integer> queue=new LinkedList<>();
for(int i=0;i<n;i++){
list.add(new LinkedList<>());
}
for(int i=0;i<prerequisites.length;i++){
int in=prerequisites[i][0];
int out=prerequisites[i][1];
inArray[out]++;
list.get(in).add(out);
}
for(int i=0;i<n;i++){
if(inArray[i]==0){
queue.add(i);
}
}
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i++){
int num=queue.poll();
res.add(num);
List<Integer> temp=list.get(num);
for(int k:temp){
if(--inArray[k]==0){
queue.add(k);
}
}
}
}
if(res.size()==n){
return res;
}
else {
return null;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)