一篇學(xué)會(huì)檢測(cè)循環(huán)依賴(lài)
本文轉(zhuǎn)載自微信公眾號(hào)「一個(gè)搬磚的胖子」，作者一個(gè)搬磚的胖子。轉(zhuǎn)載本文請(qǐng)聯(lián)系一個(gè)搬磚的胖子公眾號(hào)。
前言
今天為CodeTop補(bǔ)充的題目是檢測(cè)循環(huán)依賴(lài)。
來(lái)看一下幾篇面經(jīng)的原文敘述
- 循環(huán)依賴(lài)檢測(cè)。如，[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] => false，[['A', 'B'], ['B', 'C'], ['C', 'A']] => true(2021.4 字節(jié)跳動(dòng)-幸福里-后端)[2]
- 手撕代碼：小王寫(xiě)了一個(gè)makefile，其中有n個(gè)編譯項(xiàng)編號(hào)為0~n-1，他們互相之間有依賴(lài)關(guān)系。請(qǐng)寫(xiě)一個(gè)程序解析依賴(lài)，給出一個(gè)可行的編譯順序。(2021.03 字節(jié)跳動(dòng)-系統(tǒng)部-后端)[3]
有的面試官要求判斷是否有循環(huán)依賴(lài);有的則要求給出一個(gè)可行的順序。
解決這類(lèi)問(wèn)題的利器就是——拓?fù)渑判颉?/p>
只要你會(huì)BFS，會(huì)層次遍歷二叉樹(shù)。
你很快就能掌握拓?fù)渑判虻膶?xiě)法。
題目描述
現(xiàn)有n個(gè)編譯項(xiàng)，編號(hào)為0 ~ n-1。給定一個(gè)二維數(shù)組，表示編譯項(xiàng)之間有依賴(lài)關(guān)系。如[0, 1]表示1依賴(lài)于0。
若存在循環(huán)依賴(lài)則返回空;不存在依賴(lài)則返回可行的編譯順序。
題目分析
若給定一個(gè)依賴(lài)關(guān)系是[[0,2],[1,2],[2,3],[2,4]]，如圖所示
可以看出，它們之間不存在循環(huán)依賴(lài)。
可行的編譯序列是[0,1,2,3,4]，也可以是[1,0,2,4,3]等。
拓?fù)渑判蚩梢郧筮@樣的一個(gè)序列?？梢钥闯?，這個(gè)序列結(jié)果可能不唯一。
拓?fù)渑判蛩惴ㄟ^(guò)程：
- 選擇圖中一個(gè)入度為0的點(diǎn)，記錄下來(lái)
- 在圖中刪除該點(diǎn)和所有以它為起點(diǎn)的邊
- 重復(fù)1和2，直到圖為空或沒(méi)有入度為0的點(diǎn)。
用下圖舉個(gè)例子，看看拓?fù)渑判蛩惴ǖ倪^(guò)程。res用于存儲(chǔ)結(jié)果序列。
圖片入度為0的點(diǎn)有兩個(gè)，我們?nèi)芜x一個(gè)。比如選擇點(diǎn)0，記錄至res;刪除點(diǎn)0及以它為起點(diǎn)的邊。
然后選擇點(diǎn)1，同樣記錄下來(lái);刪除點(diǎn)1及以它為起點(diǎn)的邊。
入度為0的點(diǎn)現(xiàn)在只有點(diǎn)2，把它記錄下來(lái);刪除點(diǎn)2及以它為起點(diǎn)的邊。
同理。選擇點(diǎn)3，記錄下來(lái);刪除點(diǎn)3及以它為起點(diǎn)的邊。
選擇點(diǎn)4，記錄下來(lái);刪除點(diǎn)4及以它為起點(diǎn)的邊。
圖為空，算法結(jié)束。
最終，res存儲(chǔ)的就是拓?fù)渑判虻慕Y(jié)果，即題目中的可行編譯順序。
如果圖中存在循環(huán)依賴(lài)呢?
例如依賴(lài)關(guān)系是[[0,1],[1,2],[2,1]，如圖所示。
按照拓?fù)渑判虻乃惴?，找到入度?的點(diǎn)0存下來(lái)，然后刪除。
然后就沒(méi)有入度為0的點(diǎn)了，算法結(jié)束!
我們發(fā)現(xiàn)，可以使用res.size() == n 來(lái)判斷圖中是否有環(huán)。其中，n為點(diǎn)的個(gè)數(shù)。
這就是拓?fù)渑判蛩惴ā?/p>
代碼實(shí)現(xiàn)應(yīng)該就很好理解了~我們借助BFS來(lái)實(shí)現(xiàn)拓?fù)渑判?，?duì)列中存儲(chǔ)入度為0的點(diǎn)。
下面我提供C++和Python兩個(gè)版本的代碼。推薦大家背下來(lái)，背一些模板代碼是很有必要的。
如果你感覺(jué)拓?fù)渑判驔](méi)問(wèn)題了，去嘗試做Leetcode210. 課程表 II吧~
PS：之前沒(méi)接觸過(guò)圖的同學(xué)，可能不太理解參考代碼中存儲(chǔ)圖結(jié)構(gòu)的g。其實(shí)很簡(jiǎn)單，對(duì)于下圖來(lái)說(shuō)。
- g = [[2] #表示0->2
- [2] #表示1->2
- [3, 4] #表示2->3,2->4
- [] #表示沒(méi)有以3為起點(diǎn)的邊
- []] #表示沒(méi)有以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()
- #將依賴(lài)關(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 []
