算法：数组算法闭环

Question

检验一数组里，是否有闭环：
[{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

这应该怎么个解法

Answer 1

我觉得该问题的本质其实是“检测有向图中是否存在闭环”。

然而题目中的这些数组却都是边，我觉得比较简单的解法就是，先根据这些边构建出一个有向图，再去解决如何检测有向图中是否存在闭环的问题。

比如

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)))

Answer 2

1. 做个已访问记录。只要出现重复就是有环。
2. 快慢指针？想像成在操场跑步，如果没有环，肯定就结束了。如果有环，他们会相遇。

Answer 3

这个数组是连续的，还是打乱的，连续的一遍遍历就行，不连续的复杂点

//数组连续
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
}

Answer 4

本质就是有向图找闭环。
（不要使用 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: 怎么每次回答完问题就发现有人抢先了

Answer 5

有向图查闭环可以用并查集，可以线性时间复杂度解决。

类似的题目

冗余连接
冗余连接II