循环依赖检测算法 #38
Description
背景
平时写代码有时候会出现循环依赖的情况，这个时候就会考虑，假如自己实现，如何监测循环依赖，下面则是把这个问题算法化。
问题
问题描述
给定二维字符数组，每个元素也是包含两个字符的数组，比如 ['A', 'B']，表示 A 依赖 B，判断是否存在循环依赖，比如：
[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] => false
[['A', 'B'], ['B', 'C'], ['C', 'A']] => true
[['A', 'B'], ['B', 'A'], ['C', 'D'], ['D', 'C']] => true
[['A', 'B'], ['C', 'D'], ['B', 'A'], ['D', 'C']] => true
[['A', 'B'], ['C', 'A'], ['B', 'D'], ['B', 'C']] => true
[['A', 'A']] => true
实现一个函数，可以监测给定二位数组是否循环依赖。
/**
* 循环依赖监测算法
* @param arr
*/
function checkCircularDependency(arr) {
// TODO
}注意：一个模块可能依赖多个模块，也可能被多个模块所依赖，并且入口模块可能不唯一。
解决方案
方法一
图的表示方法：邻接矩阵表示法和邻接表表示法，上面的问题可以看做是检测有向图上是否存在环，具体参考：https://www.jianshu.com/p/c95a7913e193
方法二 剪支法
图的表示和遍历相对复杂，有没有其他方法判断是否存在循环依赖呢？
- 第 1 步：滤掉所有仅出现在依赖侧或被依赖侧的依赖关系；
- 第 2 步：不断执行第 1 步，直到不存在仅出现在依赖侧或被依赖侧的依赖关系；
- 第 3 步：判断数组是否为空，为空则不存在循环依赖，否则肯定有循环依赖；
[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] =>ABCB -> BCDD
其中 D 只出现在被依赖侧，所以把后面两个依赖关系去了，AB -> BC；
重复执行，变成 A -> B，继续，最后变为空数组，所以没有循环依赖
[['A', 'B'], ['B', 'C'], ['C', 'A']] => ABC -> BCA => true
[['A', 'B'], ['B', 'A'], ['C', 'D'], ['D', 'C']] => ABCD -> BADC => true
[['A', 'B'], ['C', 'D'], ['B', 'A'], ['D', 'C']] => ACBD -> BDAC => true
[['A', 'B'], ['C', 'A'], ['B', 'D'], ['B', 'C']]
=> ACBB -> BADC => ACB -> BAC => true
[['A', 'A']] => A -> A => true
/**
* 循环依赖监测算法
* @param arr
*/
function checkCircularDependency(arr) {
const len = arr.length
if (len <= 0) {
return false
}
const prev = {}, next = {}
arr.forEach((item, i) => {
let [p, n] = item
prev[p] = prev[p] ? (prev[p] + 1) : 1
next[n] = next[n] ? (next[n] + 1) : 1
});
let tmp = arr
while (tmp.length > 0) {
let cut = {}
tmp.forEach((item, i) => {
let [p, n] = item
if (!next[p] || !prev[n]) {
cut[i] = true
if (prev[p] && prev[p] > 1) {
prev[p] --
} else {
delete prev[p]
}
if (next[n] && next[n] > 1) {
next[n] --
} else {
delete next[n]
}
}
});
if (Object.keys(cut) <= 0) {
break
}
tmp = tmp.filter((item, i) => !cut[i])
}
return tmp.length > 0
}