之前在面试的时候有遇到过问无序图找环的问题, 当时觉得有点闷逼, 毕竟不是科班出身, 也没有静下心去看一些算法的知识. 最近在看Facebook的FBRetainCycleDetector的SDK的时候,看到运用DFS的算法找循环引用,回想到之前找环的问题,原理一致,然后今天就自己写了一个找环的demo
下图是一张包含几个环的无序图:
无序图
先将每个顶点封装成为一个对象:
BLEdgeModel
然后根据无序图封装每一个顶点,如下代码:
封装无序图的顶点
接下来就是来寻找图中顶点所产生的环, 代码如下:
寻找无序图中的环
按照我上面无序图来说,无序图的最深深度是如下图:
无序图顶点深度
大致的思路就是:
以顶点1为起始顶点, 通过深度寻找法,找到最后一个顶点6,然后一步一步往回寻找环(当然这是以我给的例子作为代表, 如果起始顶点和封装的相连顶点列表中顶点的顺序不一致的话,过程会不一样,不过最终找到的环是一样的), 代码步骤的思路我已经写在demo里面了
以下是demo地址: (包含FBRetainCycleDetector的最简单的demo)
https://github.com/IBIgLiang/iOS-RetainCycleStudy
下次再介绍FBRetainCycleDetector的源代码!!!
