今天就跟大家聊聊有关检测循环怎么用，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

创新互联是一家专注于网站设计制作、网站设计与策划设计,甘井子网站建设哪家好?创新互联做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:甘井子等地区。甘井子做网站价格咨询:13518219792

今天为CodeTop补充的题目是检测循环依赖。

• 循环依赖检测。如，[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] => false，[['A',  'B'], ['B', 'C'], ['C', 'A']] => true(2021.4 字节跳动-幸福里-后端)[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]等。

拓扑排序可以求这样的一个序列。可以看出，这个序列结果可能不唯一。

拓扑排序算法过程：

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 选择图中一个入度为0的点，记录下来

3. 在图中删除该点和所有以它为起点的边

4. 重复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 haveCircularDependency(int n, vector> &prerequisites) {     vector> g(n); //邻接表存储图结构     vector indeg(n); //每个点的入度     vector res; //存储结果序列     for(int i = 0; i < prerequisites.size(); i ++) {         int a = prerequisites[i][0], b = prerequisites[i][1];          g[a].push_back(b);         indeg[b] ++;     }     queue q;     //一次性将入度为0的点全部入队     for(int i = 0; i < n; i ++) {         if(indeg[i] == 0) q.push(i);     }     while(q.size()) {         int t = q.front();         q.pop();         res.push_back(t);         //删除边时，将终点的入度-1。若入度为0，果断入队         for(int i = 0; i < g[t].size(); i ++) {             int j = g[t][i];             indeg[j] --;             if(indeg[j] == 0) {                 q.push(j);             }         }     }     if(res.size() == n) return res;     else return {}; }

Python 版本

def haveCircularDependency(self, n: int, prerequisites):     g = [[]for i in range(n)] #邻接表存储图结构     indeg = [0 for i in range(n)] #每个点的入度     res = [] #存储结果序列     q = deque()     #将依赖关系加入邻接表中g，并各个点入度     for pre in prerequisites:         a, b = pre[0], pre[1]         g[a].append(b)         indeg[b] += 1     #一次性将入度为0的点全部入队     for i in range(n):         if indeg[i] == 0:             q.append(i)     while q:         t = q.popleft()         res.append(t)         #删除边时，将终点的入度-1。若入度为0，果断入队         for j in g[t]:             indeg[j] -= 1             if indeg[j] == 0:                 q.append(j)     if len(res) == n:         return res     else:         return []

看完上述内容，你们对检测循环怎么用有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。

分享名称：如何解决spring检测循环依赖
标题网址：http://azwzsj.com/article/pesjhg.html