????????之前在面試的時(shí)候有遇到過問無序圖找環(huán)的問題, 當(dāng)時(shí)覺得有點(diǎn)悶逼, 畢竟不是科班出身, 也沒有靜下心去看一些算法的知識(shí). 最近在看Facebook的FBRetainCycleDetector的SDK的時(shí)候,看到運(yùn)用DFS的算法找循環(huán)引用,回想到之前找環(huán)的問題,原理一致,然后今天就自己寫了一個(gè)找環(huán)的demo
下圖是一張包含幾個(gè)環(huán)的無序圖:
無序圖
先將每個(gè)頂點(diǎn)封裝成為一個(gè)對(duì)象:
BLEdgeModel
然后根據(jù)無序圖封裝每一個(gè)頂點(diǎn),如下代碼:
封裝無序圖的頂點(diǎn)
接下來就是來尋找圖中頂點(diǎn)所產(chǎn)生的環(huán), 代碼如下:?
尋找無序圖中的環(huán)
按照我上面無序圖來說,無序圖的最深深度是如下圖:
無序圖頂點(diǎn)深度
大致的思路就是:
以頂點(diǎn)1為起始頂點(diǎn), 通過深度尋找法,找到最后一個(gè)頂點(diǎn)6,然后一步一步往回尋找環(huán)(當(dāng)然這是以我給的例子作為代表, 如果起始頂點(diǎn)和封裝的相連頂點(diǎn)列表中頂點(diǎn)的順序不一致的話,過程會(huì)不一樣,不過最終找到的環(huán)是一樣的), 代碼步驟的思路我已經(jīng)寫在demo里面了
以下是demo地址: (包含F(xiàn)BRetainCycleDetector的最簡單的demo)
https://github.com/IBIgLiang/iOS-RetainCycleStudy
下次再介紹FBRetainCycleDetector的源代碼!!!
