本文转载自微信公众号《搬砖的胖子》，作者是搬砖的胖子。转载本文请联系搬砖胖子公众号。前言今天在CodeTop中加入的话题是检测循环依赖。来看看几个面谈循环依赖检测的原文。例如，[['A','B'],['B','C'],['C','D'],['B','D']]=>false,[['A','B'],['B','C'],['C','A']]=>true(2021.4ByteDance-Happiness-Backend)[2]手撕代码：小王写了一个makefile，里面有n个编译项，编号为0~n-1，它们相互依赖。请写一个解决依赖关系的程序，并给出一个可行的编译顺序。(2021.03字节跳动-系统部-后端)[3]有面试官要求判断是否存在循环依赖；一些人要求给出一个可行的命令。解决这类问题的利器就是——拓扑排序。只要知道BFS，就会分层遍历二叉树。可以很快掌握拓扑排序的写法。标题描述有n个编译项，编号从0到n-1。给定一个表示已编译项之间依赖关系的二维数组。如[0,1]表示1依赖0，如果存在循环依赖则返回空；如果没有依赖，则返回一个可行的编译序列。题目分析如果给定一个依赖关系为[[0,2],[1,2],[2,3],[2,4]]，如图所示，可以看出不存在循环依赖它们之间。一个可行的编译序列是[0,1,2,3,4]，或者[1,0,2,4,3]，等等。拓扑排序可以找到这样的序列。可见，这个序列结果可能不是唯一的。拓扑排序算法过程：在图中选取一个入度为0的点，记录下来。删除图中的点和从它开始的所有边。重复1和2，直到图为空或者不存在入度为0的点。以下图为例，看看拓扑排序算法的过程。res用于存储结果序列。图片入度为0的点有两个，我们选择一个。例如选择点0，记录到res；删除点0和从它开始的边。然后选择点1，同样记录；删除点1和从它开始的边。入度为0的点现在只有点2，记录一下；删除点2和从它开始的边。一样的方法。选择点3，记录下来；删除点3和从它开始的边。选择点4，记录下来；删除点4和从它开始的边。如果图为空，则算法结束。最后res存储的是拓扑排序的结果，即题中的可行编译顺序。如果图中存在循环依赖怎么办？比如依赖为[[0,1],[1,2],[2,1]，如图。根据拓扑排序算法，找到入度为0的点0，保存，然后删除。那么入度为0的点就没有了，算法结束！我们发现res.size()==n可以用来判断图中是否有环。其中，n为点数。这就是拓扑排序算法。代码实现应该很容易理解~我们使用BFS实现拓扑排序，入度为0的点入队。下面我提供了代码的C++和Python版本。建议您记住它。有必要记住一些模板代码。如果觉得拓扑排序还可以，试试做Leetcode210。课程附表II~PS：没有接触过图的同学可能不理解参考代码中的g存储图结构。其实很简单，如下图。g=[[2]#表示0->2[2]#表示1->2[3,4]#表示2->3,2->4[]#表示没有从3[]开始的边]#表示从4开始没有边引用代码。C++版本vector
