這裡給大家分享我在網上總結出來的一些知識，希望對大家有所幫助

一、背景

在前端JSON.stringfy是我們常用的一個方法，可以將一個對象序列化。 例如將如下對象序列化

const person = { name: 'kalory', age:18}

JSON.stringfy(person)
// 結果
'{"name":"kalory","age":18}'

將一個數組序列化

const arr = [1,2,3,4,5]
// 結果
'[1,2,3,4,5]'

const persons = [{ name: 'kalory', age:18},{ name: 'jack', age:48}]
// 結果
'[{"name":"kalory","age":18},{"name":"jack","age":48}]'

我們發現上面對象是可以使用JSON.stringfy序列化的。

• 但是如果一個對象存在迴圈引用，序列化會報錯，如下 person對象的owner屬性指向了自己，存在迴圈引用

const person = { name: 'kalory', age:18}
person.onwer = person

我們對上面這個對象進行JSON.stringfy,結果如下，會報錯：

我們發現他說不能轉化一個“圈結構體為JSON”,是因為這個對象的owner屬性指向了自己。在轉化的時候會變成死迴圈。

• 那麼我們如果判斷一個對象有沒有環呢？

二、實現

2.1 思路

我們判斷一個對象有沒有迴圈引用，我們其實並不需要在乎對象的key是什麼，只需要判斷對象的value。如果value是引用數據類型的時候，有沒有指向對象的某一值。

所以我們可以先使用Object.values()拿到對象所有values,然後定義一個cache變數用來存儲values中的引用數據類型，然後遍歷values。

如果cache中存在，那麼說明這個對象有環 return true，如果不存在並且是引用數據類型，那麼我們就加入cache。當values遍歷完都沒有reutrn那麼說明沒有環return false

2.2 遞歸實現

function existCircular(obj) {
  let cache = new Set(); 
  function helper(obj) {
    let values = Object.values(obj);
    for (let i = 0; i < values.length; i++) {
      if (cache.has(values[i])) {
        return true;
      }
      
      // 不是引用數據類型，直接跳過
      if(typeof values[i] !== 'object' || values[i] === null) continue
      cache.add(values[i]);
      
      let flag = helper(values[i]);
      // 如果 flag 是 false, 那麼繼續遍歷，如果是 true,說明已經存在環了， 直接 return true
      if (flag) {
        return true;
      }
    }
    return false;
  }

  return helper(obj);
}

// 測試
const person = { name: 'kalory', age:18}
person.onwer = person

existCircular(person) // true

2.3 BFS實現

const existCircularBFS = (obj) => {
  let cache = new Set();
  let values = [obj];

  while(values.length) {
    const item =  values.shift()
    if (cache.has(item)) {
        return true;
    }
    // 基本數據類型跳過
    if(typeof item !== 'object' || item === null) continue
    cache.add(item);
    // 主要這裡 Object.values 拿到的是一個數組，我們需要展開push到values
    // 如果直接 push Object.values(item) 會造成死循話
    values.push(...Object.values(item))
  }
  
  return false;
}

本文轉載於:

https://juejin.cn/post/7343867039022071859

如果對您有所幫助，歡迎您點個關註，我會定時更新技術文檔，大家一起討論學習，一起進步。