iOS-无序图环的寻找和FBRetainCycleDetecto

        之前在面试的时候有遇到过问无序图找环的问题, 当时觉得有点闷逼, 毕竟不是科班出身, 也没有静下心去看一些算法的知识. 最近在看Facebook的FBRetainCycleDetector的SDK的时候,看到运用DFS的算法找循环引用,回想到之前找环的问题,原理一致,然后今天就自己写了一个找环的demo

下图是一张包含几个环的无序图:

无序图

先将每个顶点封装成为一个对象:

BLEdgeModel

然后根据无序图封装每一个顶点,如下代码:

封装无序图的顶点

接下来就是来寻找图中顶点所产生的环, 代码如下: 

寻找无序图中的环

按照我上面无序图来说,无序图的最深深度是如下图:

无序图顶点深度

大致的思路就是:

以顶点1为起始顶点, 通过深度寻找法,找到最后一个顶点6,然后一步一步往回寻找环(当然这是以我给的例子作为代表, 如果起始顶点和封装的相连顶点列表中顶点的顺序不一致的话,过程会不一样,不过最终找到的环是一样的), 代码步骤的思路我已经写在demo里面了

以下是demo地址: (包含FBRetainCycleDetector的最简单的demo)

https://github.com/IBIgLiang/iOS-RetainCycleStudy

下次再介绍FBRetainCycleDetector的源代码!!!