[[396795]]

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

前言

今天為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)編號(hào)為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)，編號(hào)為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í)很簡單，對于下圖來說。

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

參考代碼

C++ 版本

vector<int> haveCircularDependency(int n, vector<vector<int>> &prerequisites) { 
    vector<vector<int>> g(n); //鄰接表存儲(chǔ)圖結(jié)構(gòu) 
    vector<int> indeg(n); //每個(gè)點(diǎn)的入度 
    vector<int> res; //存儲(chǔ)結(jié)果序列 
    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的點(diǎn)全部入隊(duì) 
    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); 
        //刪除邊時(shí)，將終點(diǎn)的入度-1。若入度為0，果斷入隊(duì) 
        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)] #鄰接表存儲(chǔ)圖結(jié)構(gòu) 
    indeg = [0 for i in range(n)] #每個(gè)點(diǎn)的入度 
    res = [] #存儲(chǔ)結(jié)果序列 
    q = deque() 
    #將依賴關(guān)系加入鄰接表中g(shù)，并各個(gè)點(diǎn)入度 
    for pre in prerequisites: 
        a, b = pre[0], pre[1] 
        g[a].append(b) 
        indeg[b] += 1 
    #一次性將入度為0的點(diǎn)全部入隊(duì) 
    for i in range(n): 
        if indeg[i] == 0: 
            q.append(i) 
    while q: 
        t = q.popleft() 
        res.append(t) 
        #刪除邊時(shí)，將終點(diǎn)的入度-1。若入度為0，果斷入隊(duì) 
        for j in g[t]: 
            indeg[j] -= 1 
            if indeg[j] == 0: 
                q.append(j) 
    if len(res) == n: 
        return res 
    else: 
        return []