4

我有一个如下对象：

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

我必须找到循环实体的映射而不将其转换为图形。

类似的输出将如下所示：

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 块可能也是一种方法。但我不确定它的性能会更高/更低。

4

1 回答 1

4

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

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

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; }

于 2019-05-16T19:56:04.630 回答