今天就跟大家聊聊有關(guān)檢測(cè)循環(huán)怎么用，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

創(chuàng)新互聯(lián)是一家專注于網(wǎng)站設(shè)計(jì)制作、網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),甘井子網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:甘井子等地區(qū)。甘井子做網(wǎng)站價(jià)格咨詢:13518219792

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

• 循環(huán)依賴檢測(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，他們互相之間有依賴關(guān)系。請(qǐng)寫(xiě)一個(gè)程序解析依賴，給出一個(gè)可行的編譯順序。(2021.03  字節(jié)跳動(dòng)-系統(tǒng)部-后端)[3]

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

解決這類問(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)之間有依賴關(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ù)渑判蛩惴ㄟ^(guò)程：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 選擇圖中一個(gè)入度為0的點(diǎn)，記錄下來(lái)

3. 在圖中刪除該點(diǎn)和所有以它為起點(diǎn)的邊

4. 重復(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)依賴呢?

例如依賴關(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()     #將依賴關(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 []

看完上述內(nèi)容，你們對(duì)檢測(cè)循環(huán)怎么用有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。

分享標(biāo)題：如何解決spring檢測(cè)循環(huán)依賴
網(wǎng)站鏈接：http://aaarwkj.com/article46/pesjhg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、品牌網(wǎng)站制作、App開(kāi)發(fā)、域名注冊(cè)、網(wǎng)站設(shè)計(jì)公司、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)