日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
一篇學(xué)會(huì)檢測循環(huán)依賴

本文轉(zhuǎn)載自微信公眾號「一個(gè)搬磚的胖子」，作者一個(gè)搬磚的胖子。轉(zhuǎn)載本文請聯(lián)系一個(gè)搬磚的胖子公眾號。

前言

今天為CodeTop補(bǔ)充的題目是檢測循環(huán)依賴。

來看一下幾篇面經(jīng)的原文敘述

  • 循環(huán)依賴檢測。如，[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] => false，[['A', 'B'], ['B', 'C'], ['C', 'A']] => true(2021.4 字節(jié)跳動(dòng)-幸福里-后端)[2]
  • 手撕代碼：小王寫了一個(gè)makefile，其中有n個(gè)編譯項(xiàng)編號為0~n-1，他們互相之間有依賴關(guān)系。請寫一個(gè)程序解析依賴，給出一個(gè)可行的編譯順序。(2021.03 字節(jié)跳動(dòng)-系統(tǒng)部-后端)[3]

有的面試官要求判斷是否有循環(huán)依賴;有的則要求給出一個(gè)可行的順序。

解決這類問題的利器就是——拓?fù)渑判颉?/p>

只要你會(huì)BFS，會(huì)層次遍歷二叉樹。

你很快就能掌握拓?fù)渑判虻膶懛ā?/p>

題目描述

現(xiàn)有n個(gè)編譯項(xiàng)，編號為0 ~ n-1。給定一個(gè)二維數(shù)組，表示編譯項(xiàng)之間有依賴關(guān)系。如[0, 1]表示1依賴于0。

若存在循環(huán)依賴則返回空;不存在依賴則返回可行的編譯順序。

題目分析

若給定一個(gè)依賴關(guān)系是[[0,2],[1,2],[2,3],[2,4]]，如圖所示

可以看出，它們之間不存在循環(huán)依賴。

可行的編譯序列是[0,1,2,3,4]，也可以是[1,0,2,4,3]等。

拓?fù)渑判蚩梢郧筮@樣的一個(gè)序列。可以看出，這個(gè)序列結(jié)果可能不唯一。

拓?fù)渑判蛩惴ㄟ^程：

  1. 選擇圖中一個(gè)入度為0的點(diǎn)，記錄下來
  2. 在圖中刪除該點(diǎn)和所有以它為起點(diǎn)的邊
  3. 重復(fù)1和2，直到圖為空或沒有入度為0的點(diǎn)。

用下圖舉個(gè)例子，看看拓?fù)渑判蛩惴ǖ倪^程。res用于存儲(chǔ)結(jié)果序列。

圖片入度為0的點(diǎn)有兩個(gè)，我們?nèi)芜x一個(gè)。比如選擇點(diǎn)0，記錄至res;刪除點(diǎn)0及以它為起點(diǎn)的邊。

然后選擇點(diǎn)1，同樣記錄下來;刪除點(diǎn)1及以它為起點(diǎn)的邊。

入度為0的點(diǎn)現(xiàn)在只有點(diǎn)2，把它記錄下來;刪除點(diǎn)2及以它為起點(diǎn)的邊。

同理。選擇點(diǎn)3，記錄下來;刪除點(diǎn)3及以它為起點(diǎn)的邊。

選擇點(diǎn)4，記錄下來;刪除點(diǎn)4及以它為起點(diǎn)的邊。

圖為空，算法結(jié)束。

最終，res存儲(chǔ)的就是拓?fù)渑判虻慕Y(jié)果，即題目中的可行編譯順序。

如果圖中存在循環(huán)依賴呢?

例如依賴關(guān)系是[[0,1],[1,2],[2,1]，如圖所示。

按照拓?fù)渑判虻乃惴ǎ业饺攵葹?的點(diǎn)0存下來，然后刪除。

然后就沒有入度為0的點(diǎn)了，算法結(jié)束!

我們發(fā)現(xiàn)，可以使用res.size() == n 來判斷圖中是否有環(huán)。其中，n為點(diǎn)的個(gè)數(shù)。

這就是拓?fù)渑判蛩惴ā?/p>

代碼實(shí)現(xiàn)應(yīng)該就很好理解了~我們借助BFS來實(shí)現(xiàn)拓?fù)渑判?，?duì)列中存儲(chǔ)入度為0的點(diǎn)。

下面我提供C++和Python兩個(gè)版本的代碼。推薦大家背下來，背一些模板代碼是很有必要的。

如果你感覺拓?fù)渑判驔]問題了，去嘗試做Leetcode210. 課程表 II吧~

PS：之前沒接觸過圖的同學(xué)，可能不太理解參考代碼中存儲(chǔ)圖結(jié)構(gòu)的g。其實(shí)很簡單，對于下圖來說。

 
 
 
 
    
  
  
  
  
  1. g = [[2]     #表示0->2 
    2.   
  
  
  
  2.      [2]     #表示1->2 
    3.   
  
  
  
  3.      [3, 4]  #表示2->3,2->4 
    4.   
  
  
  
  4.      []      #表示沒有以3為起點(diǎn)的邊 
    5.   
  
  
  
  5.      []]     #表示沒有以4為起點(diǎn)的邊 
    6.

參考代碼

C++ 版本

 
 
 
 
    
  
  
  
  
  1. vector haveCircularDependency(int n, vector> &prerequisites) { 
    2.   
  
  
  
  2.     vector> g(n); //鄰接表存儲(chǔ)圖結(jié)構(gòu) 
    3.   
  
  
  
  3.     vector indeg(n); //每個(gè)點(diǎn)的入度 
    4.   
  
  
  
  4.     vector res; //存儲(chǔ)結(jié)果序列 
    5.   
  
  
  
  5.     for(int i = 0; i < prerequisites.size(); i ++) { 
    6.   
  
  
  
  6.         int a = prerequisites[i][0], b = prerequisites[i][1];  
    7.   
  
  
  
  7.         g[a].push_back(b); 
    8.   
  
  
  
  8.         indeg[b] ++; 
    9.   
  
  
  
  9.     } 
    10.   
  
  
  
  10.     queue q; 
    11.   
  
  
  
  11.     //一次性將入度為0的點(diǎn)全部入隊(duì) 
    12.   
  
  
  
  12.     for(int i = 0; i < n; i ++) { 
    13.   
  
  
  
  13.         if(indeg[i] == 0) q.push(i); 
    14.   
  
  
  
  14.     } 
    15.   
  
  
  
  15.     while(q.size()) { 
    16.   
  
  
  
  16.         int t = q.front(); 
    17.   
  
  
  
  17.         q.pop(); 
    18.   
  
  
  
  18.         res.push_back(t); 
    19.   
  
  
  
  19.         //刪除邊時(shí)，將終點(diǎn)的入度-1。若入度為0，果斷入隊(duì) 
    20.   
  
  
  
  20.         for(int i = 0; i < g[t].size(); i ++) { 
    21.   
  
  
  
  21.             int j = g[t][i]; 
    22.   
  
  
  
  22.             indeg[j] --; 
    23.   
  
  
  
  23.             if(indeg[j] == 0) { 
    24.   
  
  
  
  24.                 q.push(j); 
    25.   
  
  
  
  25.             } 
    26.   
  
  
  
  26.         } 
    27.   
  
  
  
  27.     } 
    28.   
  
  
  
  28.     if(res.size() == n) return res; 
    29.   
  
  
  
  29.     else return {}; 
    30.   
  
  
  
  30. } 
    31.

Python 版本

 
 
 
 
    
  
  
  
  
  1. def haveCircularDependency(self, n: int, prerequisites): 
    2.   
  
  
  
  2.     g = [[]for i in range(n)] #鄰接表存儲(chǔ)圖結(jié)構(gòu) 
    3.   
  
  
  
  3.     indeg = [0 for i in range(n)] #每個(gè)點(diǎn)的入度 
    4.   
  
  
  
  4.     res = [] #存儲(chǔ)結(jié)果序列 
    5.   
  
  
  
  5.     q = deque() 
    6.   
  
  
  
  6.     #將依賴關(guān)系加入鄰接表中g(shù)，并各個(gè)點(diǎn)入度 
    7.   
  
  
  
  7.     for pre in prerequisites: 
    8.   
  
  
  
  8.         a, b = pre[0], pre[1] 
    9.   
  
  
  
  9.         g[a].append(b) 
    10.   
  
  
  
  10.         indeg[b] += 1 
    11.   
  
  
  
  11.     #一次性將入度為0的點(diǎn)全部入隊(duì) 
    12.   
  
  
  
  12.     for i in range(n): 
    13.   
  
  
  
  13.         if indeg[i] == 0: 
    14.   
  
  
  
  14.             q.append(i) 
    15.   
  
  
  
  15.     while q: 
    16.   
  
  
  
  16.         t = q.popleft() 
    17.   
  
  
  
  17.         res.append(t) 
    18.   
  
  
  
  18.         #刪除邊時(shí)，將終點(diǎn)的入度-1。若入度為0，果斷入隊(duì) 
    19.   
  
  
  
  19.         for j in g[t]: 
    20.   
  
  
  
  20.             indeg[j] -= 1 
    21.   
  
  
  
  21.             if indeg[j] == 0: 
    22.   
  
  
  
  22.                 q.append(j) 
    23.   
  
  
  
  23.     if len(res) == n: 
    24.   
  
  
  
  24.         return res 
    25.   
  
  
  
  25.     else: 
    26.   
  
  
  
  26.         return [] 
    27.

名稱欄目：一篇學(xué)會(huì)檢測循環(huán)依賴
鏈接分享：http://www.dlmjj.cn/article/coddpsp.html