javascript - javascript中的递归函数使用笔迹库返回所选节点的父节点

Question

我正在使用笔迹学，这是一个提供由节点和边组成的图形对象的库。 我的结构类似于所附图片中的结构。

每条边都有一个与之关联的方向。 我想创建一个函数(可能是递归的)，它将返回所选节点的父节点。 例如。 parentsOfFunction(6) 应该返回

[
  [4,1],
  [5,
      [2,3],
  ]
]

每当一个节点有一条边的分支时，就会在数组中创建一个新的子元素。 我相信这是存储结果以便稍后迭代的最佳方式，但我很乐意更改结构，只要可以推断出结构即可。 目前我的函数只返回 [4,5]，它们是 6 的第一级父级。 console.log 值是正确的，但我不知道如何将其存储在变量中。 感谢任何帮助，TIA。

编辑: 我实际上已经为此制定了一个功能？这是执行上述操作的合适/有效方法吗？再次感谢。

Updated codesandbox

代码:

import Graph from "graphology";
const graph = new Graph({
  multi: false,
  allowSelfLoops: false,
  type: "directed"
});

graph.addNode("1");
graph.addNode("2");
graph.addNode("3");
graph.addNode("4");
graph.addNode("5");
graph.addNode("6");

graph.addEdge("1", "4", { name: "a" });
graph.addEdge("2", "5", { name: "b" });
graph.addEdge("3", "5", { name: "c" });
graph.addEdge("4", "6", { name: "d" });
graph.addEdge("5", "6", { name: "e" });

let parents = [];

function getNodes(node) {
  return graph.inboundNeighbors(node);
}

function recursive(startingNode) {
  let list = getNodes(startingNode);
  if (list.length < 0) {
    parents[0] = list;
  } else {
    for (let i = 0; i < list.length; i++) {
      parents[i] = [list[i], getNodes(list[i])];
    }
  }
}
recursive(6);
console.log(parents);

Answer 1

您的 recursive 函数实际上不是递归的，因此您的代码不起作用。它只产生两级深度输出，在示例测试中恰好看起来还不错(但不完全)。尝试其他测试用例。

此外，预期的输出是一种非常不寻常的数据结构，因为它混合了类型。这是一种您应该尽可能避免的反模式。它还省略了根，这使得递归逻辑编写起来有点笨拙。我使用了一个额外的内部函数来剥离根。

这是一种使用混合类型返回值和测试来确定我们有多少 parent 的方法。给定调用的逻辑如下:

• 如果这个节点没有父节点，它就是叶节点。直接返回它，没有数组包装器。
• 如果此节点有一个父节点，则应直接在其父子树旁边的数组中返回它。
• 如果这个节点有多个父节点，它应该在一个数组中返回，其父节点的子树在一个子数组中。

const buildTreeFromParents = (graph, start) => {
  const recurse = start => {
    const parents = graph.inboundNeighbors(start);

    if (parents.length === 0) {
      return start;
    }
    else if (parents.length === 1) {
      return [start, recurse(parents[0])];
    }

    return [start, parents.map(recurse)];
  };

  return graph.inboundNeighbors(start).map(recurse);
};

const graph = new graphology.Graph({
  multi: false,
  allowSelfLoops: false,
  type: "directed"
});
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addNode(4);
graph.addNode(5);
graph.addNode(6);
graph.addEdge(1, 4, {name: "a"});
graph.addEdge(2, 5, {name: "b"});
graph.addEdge(3, 5, {name: "c"});
graph.addEdge(4, 6, {name: "d"});
graph.addEdge(5, 6, {name: "e"});
console.log(buildTreeFromParents(graph, 6));

<script src="https://cdnjs.cloudflare.com/ajax/libs/graphology/0.21.0/graphology.umd.min.js"></script>

写函数时尽量避免使用全局变量，应该是纯自包含的，避免出现bug，混淆状态修改和依赖。

---

根据评论，下面是解决上述几个棘手问题的代码。它仍然是一个混合类型结构，但至少包含了根并且父嵌套更有意义，因为当只有一个父级时没有采用特殊条件。

const buildTreeFromParents = (graph, start) => {
  const parents = graph.inboundNeighbors(start);

  if (parents.length === 0) {
    return start;
  }

  return [start, parents.map(e => buildTreeFromParents(graph, e))];
};

const graph = new graphology.Graph({
  multi: false,
  allowSelfLoops: false,
  type: "directed"
});
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addNode(4);
graph.addNode(5);
graph.addNode(6);
graph.addEdge(1, 4, {name: "a"});
graph.addEdge(2, 5, {name: "b"});
graph.addEdge(3, 5, {name: "c"});
graph.addEdge(4, 6, {name: "d"});
graph.addEdge(5, 6, {name: "e"});
console.log(buildTreeFromParents(graph, 6));

<script src="https://cdnjs.cloudflare.com/ajax/libs/graphology/0.21.0/graphology.umd.min.js"></script>