Node.js中如何递归处理关联节点？求A到Z路径实现脚本

要找出节点A到Z的所有路径，用**深度优先搜索(DFS)**就很合适，这是图遍历里找全路径的常用方法。下面是Node.js的完整实现，涵盖从数据库数据转换到路径查找的全流程：

1. 先把数据库数据转成邻接表 #

假设你的数据库存储的是边集合（每条记录是{ from: 起始节点, to: 关联节点 }），先把它转换成邻接表结构，方便后续遍历：

// 模拟从数据库查询到的边数据（两张关联图的合并结果）
const dbEdges = [
  { from: 'A', to: 'B' },
  { from: 'A', to: 'C' },
  { from: 'B', to: 'D' },
  { from: 'B', to: 'E' },
  { from: 'C', to: 'F' },
  { from: 'D', to: 'Z' },
  { from: 'E', to: 'Z' },
  { from: 'F', to: 'Z' },
  // 可添加含环的测试数据：比如 { from: 'D', to: 'B' }
];

// 转换为邻接表的工具函数
const buildGraph = (edges) => {
  const graph = {};
  edges.forEach(edge => {
    if (!graph[edge.from]) graph[edge.from] = [];
    graph[edge.from].push(edge.to);
    // 如果是无向关联（A关联B则B也关联A），解开下面注释：
    // if (!graph[edge.to]) graph[edge.to] = [];
    // graph[edge.to].push(edge.from);
  });
  return graph;
};

// 生成最终可用的图结构
const graph = buildGraph(dbEdges);

2. 实现DFS查找所有路径 #

用递归式DFS遍历，通过visited集合避免循环，同时记录当前路径：

const findAllPaths = (graph, start, end) => {
  const result = [];

  // 递归DFS核心逻辑
  const dfs = (currentNode, currentPath, visited) => {
    // 更新已访问集合和当前路径
    const newVisited = new Set(visited);
    newVisited.add(currentNode);
    const newPath = [...currentPath, currentNode];

    // 到达目标节点，保存路径
    if (currentNode === end) {
      result.push(newPath);
      return;
    }

    // 当前节点无邻接节点，直接回溯
    if (!graph[currentNode]) return;

    // 遍历所有邻接节点，未访问过则继续递归
    graph[currentNode].forEach(neighbor => {
      if (!newVisited.has(neighbor)) {
        dfs(neighbor, newPath, newVisited);
      }
    });
  };

  // 启动DFS遍历
  dfs(start, [], new Set());
  return result;
};

3. 调用并输出结果 #

const startNode = 'A';
const endNode = 'Z';
const paths = findAllPaths(graph, startNode, endNode);

console.log(`从${startNode}到${endNode}的所有路径：`);
paths.forEach((path, index) => {
  console.log(`路径${index + 1}: ${path.join(' -> ')}`);
});

关键说明 #

• 无向图适配：如果你的节点关联是双向的，在构建邻接表时添加反向边即可（代码中已注释）。
• 环的处理：通过visited集合记录已访问节点，避免陷入无限循环。
• 数据库适配：如果用MongoDB/MySQL等数据库，只需把dbEdges替换成实际查询结果即可，比如MongoDB用await db.collection('edges').find().toArray()，SQL则用查询返回的结果集。

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