某厂面试题(判断循环依赖)

admin2024-04-03  0

// 依赖数据
const testData = [
  {
    name: "a",
    node_modules: [
      {
        name: "b",
      },
    ],
  },
  {
    name: "b",
    node_modules: [
      {
        name: "c",
      },
    ],
  },
  {
    name: "c",
    node_modules: [
      {
        name: "a",
      },
    ],
  },
];


const testData2 = [
  {
    name: "a",
    node_modules: [
      {
        name: "b",
      },
    ],
  },
  {
    name: "b",
    node_modules: [
      {
        name: "c",
      },
    ],
  },
];
// 检测是否存在循环依赖?
function isCircleDep(arr) {}

isCircleDep(testData); // true
isCircleDep(testData2); // false

代码实现

function isCircleDep(arr) {
  /** 遍历一次,记录所有依赖关系,value使用Set,避免重复依赖 */
  const map = {};

  arr.forEach(o => {
    if (map.hasOwnProperty([o.name])) {
      map[o.name] = map[o.name].add(...o.node_modules.map(k => k.name))
    } else { 
      map[o.name] = new Set(...o.node_modules.map(k => k.name));
    }
  });
  // 记录已经找过的依赖包
  let record = [];

  function seed(key) {
    let isDep = false;
    /** 已经存在,就是存在了依赖循环 */
    if (record.includes(key)) return true;
    record.push(key);
    // map的每一个key的值中深度查找有没有key
    for(let nm of map[key]) {
      /** 没有依赖树,直接结束 */
      if (!map[nm]) continue;
      isDep = seed(nm);
      if (isDep) {
        break;
      }
    }
    return isDep;
  }

  let isDep = false;

  for(let key of Object.keys(map)) {
    // 当前深度遍历完成--清空记录数据
    record = [];
    /** 没有依赖树,直接结束 */
    if (!map[key]) continue;
    isDep = seed(key);
    if (isDep) {
      break;
    }
  }

  return isDep;
}

欢迎感兴趣的猿友们一起探讨其他解法

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!