检验一数组里,是否有闭环:
[{from: 1,to: 2}, {from:2, to:3}] 返回false
[{from: 1,to: 2}, {from:2, to:3}, {from: 3, to:1}] 返回true
[{from: 1,to: 2}, {from:2, to:3}, {from: 3, to:4}, {from: 4, to:2}] 返回 true
这应该怎么个解法
###我觉得该问题的本质其实是“检测有向图中是否存在闭环”。
然而题目中的这些数组却都是边,我觉得比较简单的解法就是,先根据这些边构建出一个有向图,再去解决如何检测有向图中是否存在闭环的问题。
比如
var t = {}; // 用来保存节点,以节点的序号作为键名
var node = { next:[], searchStatus:''}; // 节点的结构包括 next:[]自己指向的阶段,searchStatus:String 搜索状态
var ls = [{from: 1,to: 2}, {from:2, to:3}, {from: 3, to:1}]; // 储存边的数组
for(let i = 0;i < ls.length;i++){
let b = ls[i]; // 边
if(!t[b.from]) {
// 如果边的起始点还未创建
// 则创建这个起始点
t[b.from] = { next:[], searchStatus:'' }
}
if(!t[b.to]) {
// 如果边的终点还未创建
// 则创建这个终点
t[b.to] = { next:[], searchStatus:'' }
}
// 则将边的指向加入到节点的next数组中
t[b.from].next.push(b.to);
}
// 到这里 图 算是构建完成
function dfs(keys){
if(keys.length === 0) return false; // 节点数为空,返回false
for(let k in keys){
// 遇到一个节点
// 如果这个节点的搜索状态是‘搜索中’
// 那么就说明存在闭环
if(t[keys[k]].searchStatus === '搜索中') {
return true;
}
// 如果之前并没有遇到这个节点
// 那么将这个节点状态修改为‘搜索中’
// 并将其指向的节点纳入搜索
// 如果其指向的节点的搜索结果存在true
// 则返回 true
if(t[keys[k]].searchStatus === ''){
t[keys[k]].searchStatus = '搜索中';
if(dfs(t[keys[k]].next)) return true;
}
// 如果碰到一个节点状态已经是搜索结束
// 那么不做处理
if(t[keys[k]].searchStatus === '搜索结束') continue
// 如果该节点指向的节点不存在闭环
// 则自己应该也不存在闭环
// 将自己的状态修改为搜索结束
t[keys[k]].searchStatus = '搜索结束'
}
// 最后返回这些节点中不存在闭环
return false
}
console.log(dfs(Object.keys(t)))
###- 做个已访问记录。只要出现重复就是有环。
- 快慢指针?想像成在操场跑步,如果没有环,肯定就结束了。如果有环,他们会相遇。
这个数组是连续的,还是打乱的,连续的一遍遍历就行,不连续的复杂点
//数组连续
function closed(arr){
if(arr.length <= 1)return false
for(let i = 0, l = arr.length; i < l; i++){
if(arr[i].to !== arr[i == l - 1 ? 0 : (i + 1)].from){
return false
}
}
return true
}
//数组不连续
function closed(arr){
if(arr.length <= 1)return false
let obj = arr.reduce((obj, item) => {
obj[item.from] = item
return obj
}, {})
for(let i = 0, l = arr.length, v; i < l; i++){
if(!obj[arr[i].from] || !obj[arr[i].to]){
return false
}
}
return true
}
###本质就是有向图找闭环。
(不要使用 0 节点编号)
const hasRing = arr => {
const G = [ [] ], V = [ 4 ]
arr.forEach(({ from, to }) => {
if (! G[from]) G[from] = []
G[0][from] = G[0][to] = G[from][to] = true
V[from] = V[to] = 1
})
const dfs = v => {
if (v && V[v] === 3) return true
if (G[v]) for (const i in G[v]) {
console.log(`${v} -> ${i}`)
if (v) V[i] ++
if (dfs(i)) return true
}
return false
}
return dfs(0)
}
PS: 怎么每次回答完问题就发现有人抢先了
有向图查闭环可以用并查集,可以线性时间复杂度解决。
类似的题目