一篇学会检测循环依赖

本文转载自微信公众号「一个搬砖的胖子」，作者一个搬砖的胖子。转载本文请联系一个搬砖的胖子公众号。

前言

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

分享名称：一篇学会检测循环依赖
文章转载：http://www.shufengxianlan.com/qtweb/news44/375694.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容