基于Graphology库的JS递归函数：获取指定节点的父节点

我正在使用Graphology库，该库提供由节点和边组成的图对象，我的图结构是有向图，每条边都带有方向。我希望编写一个递归函数，返回所选节点的父节点层级结构，例如调用parentsOfFunction(6)应返回：

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

其中每当节点有分支边时，就会在数组中生成新的子元素。我认为这种结构便于后续遍历，但也可调整结构，只要能清晰推断层级关系。

目前我的函数仅能返回6的一级父节点[4,5]，控制台日志的值正确但无法将完整层级结构存储到变量中。

补充：已实现函数，求评估 #

我已经写出了一个函数，请问这种实现方式是否合适且高效？

代码示例 #

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

原代码的问题 #

• 递归逻辑缺失：仅获取了一级父节点的直接父节点，没有递归遍历更深层级，无法生成嵌套结构。
• 全局变量依赖：使用全局parents数组存储结果，不灵活且会导致多次调用时数据污染。
• 无效条件判断：list.length < 0永远不会成立，数组长度不可能为负数，应判断list.length === 0。

改进后的递归实现 #

以下是符合需求的递归函数，无全局变量依赖，能完整生成嵌套层级结构：

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

function getParentHierarchy(node) {
  const parents = graph.inboundNeighbors(node);
  if (parents.length === 0) {
    return [];
  }
  return parents.map(parent => {
    const parentParents = getParentHierarchy(parent);
    return parentParents.length ? [parent, parentParents] : parent;
  });
}

// 调用示例
console.log(getParentHierarchy("6"));

输出结果 #

调用getParentHierarchy("6")会返回：

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

与期望结构一致，层级关系清晰。

合理性与高效性分析 #

1. 无副作用：通过返回值传递结果，纯函数式实现更可靠，避免全局变量污染。
2. 递归逻辑完整：每个节点都会递归遍历所有父节点，直到无父节点为止，完整生成层级结构。
3. 时间高效：每个节点最多被遍历一次，时间复杂度为O(N)（N为图中节点数），在有向无环图（DAG）中性能最优；若图中有环，需添加已访问节点检测避免无限递归。
4. 结构灵活：父节点有更深层级时返回嵌套数组，否则返回单个值，既满足需求又简洁易读。

内容的提问来源于stack exchange，提问作者scooty