javascript - 在数组的Map中不使用图查找循环依赖

Question

我有一个像下面这样的对象:

var myMap = {
    v1: ['v2', 'v4', 'v5'],
    v2: ['x', 'v4', 'y'],
    v3: ['v2', 'v4', 'v5'],
    v4: ['e', 'v1', 'v5'],
    v5: ['v2', 'v4', 'v3'],
};

我必须在不将其转换为图形的情况下找到循环的实体图。

Like 输出如下:

var myDep = {
    v1: {isCyclic: true, cyclicDependents: ['v4']},
    v2: {isCyclic: false, cyclicDependents: []},
    v3: {isCyclic: true, cyclicDependents: ['v5']},
    v4: {isCyclic: true, cyclicDependents: ['v1', 'v5']},
    v5: {isCyclic: true, cyclicDependents: ['v4', 'v3']},
};

我尝试了以下内容:

var graph = {
  v1: ["v2", "v4", "v5"],
  v2: ["x", "v4", "y"],
  v3: ["v2", "v4", "v5"],
  v4: ["e", "v1", "v5"],
  v5: ["v2", "v4", "v3"]
};

var myDep = {
  v1: { isCyclic: false, cyclicDependents: [] },
  v2: { isCyclic: false, cyclicDependents: [] },
  v3: { isCyclic: false, cyclicDependents: [] },
  v4: { isCyclic: false, cyclicDependents: [] },
  v5: { isCyclic: false, cyclicDependents: [] }
};

myDep = Object.keys(graph).reduce((a, b) => {
  graph[b] &&
graph[b].forEach(d => {
  if (graph[d] && ~graph[d].indexOf(b)) {
    a[b].isCyclic = true;
    a[b].cyclicDependents.push(d);
  }
});
  return a;
}, myDep);

console.log(myDep);

有没有其他方法可以提高性能。我认为以迭代方式使用 JSON.stringify 和 try catch block 可能也是一种方法。但我不确定它的性能会更高/更低。

Answer 1

您可以采用一个函数来检查循环性质并存储访问过的节点以防止永远循环。

结果是一个具有起始键及其循环节点的对象。想要的格式留给读者作为练习。

function isCyclic(node, target, [...visited] = []) {
    if (node === target) return true;
    if (visited.includes(node) || !myMap[node]) return false;
    visited.push(node);
    return myMap[node].some(n => isCyclic(n, target, visited));
}

var myMap = { v1: ['v2', 'v4', 'v5'], v2: ['x', 'v4', 'y'], v3: ['v2', 'v4', 'v5'], v4: ['e', 'v1', 'v5'], v5: ['v2', 'v4', 'v3'] },
    result = {};
   
Object.entries(myMap).forEach(([k, v]) => result[k] = v.filter(n => isCyclic(n, k)));

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }