一篇学会检测循环依赖

本文转载自微信公众号「一个搬砖的篇学胖子」，作者一个搬砖的检环依胖子。转载本文请联系一个搬砖的测循胖子公众号。

前言

今天为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]等。

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

拓扑排序算法过程：

选择图中一个入度为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<int> haveCircularDependency(int n, vector<vector<int>> &prerequisites) {      vector<vector<int>> g(n); //邻接表存储图结构     vector<int> indeg(n); //每个点的入度     vector<int> 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<int> 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 []