JavaScript 类DFS数组遍历 实现搜索后回溯根节点的路径生成问题

需求规则 #

• 遍历所有可行路径，不可重复访问已走过的边
• 采用DFS+回溯逻辑，每次搜索完成后回到父节点重新搜索
• 路径匹配要求：前一个节点的末尾元素等于下一个节点的首元素
• 所有路径必须以0开头，无后续可搜索节点时终止遍历

输入输出示例 #

输入 #

const input = [  
  [0, 1],
  [0, 2],
  [1, 5],
  [2, 6],
  [2, 12],
  [5, 29],
  [6, 29],
  [9, 30],
  [12, 18],
  [18, 29],
  [29, 9],
  [29, 12],
  [29, 18]
];

预期输出 #

const output =  [
  [0,1,5,29,9,30],
  [0,1,5,29,12,18,29,18],
  [0,1,5,29,12,18,29,9,30],
  [0,1,5,29,18,29,9,30],
  [0,1,5,29,18,29,12,18],
  [0,2,6,29,9,30],
  [0,2,6,29,12,18,29,9,30],
  [0,2,6,29,12,18,29,18],
  [0,2,6,29,18,29,9,30],
  [0,2,6,29,18,29,12,18],
  [0,2,12,18,29,9,30],
  [0,2,12,18,29,12],
  [0,2,12,18,29,18]
]

可行实现代码 #

function getPaths(input) {
  const result = [];
  // DFS回溯函数：当前路径、已访问的边索引集合
  const dfs = (currentPath, visitedEdges) => {
    const lastVal = currentPath.at(-1);
    // 筛选所有未访问、且首元素匹配当前路径末尾的边
    const nextEdges = input.map((edge, idx) => ({edge, idx}))
      .filter(({edge, idx}) => !visitedEdges.has(idx) && edge[0] === lastVal);
    // 无后续边时当前路径为完整路径，存入结果
    if (nextEdges.length === 0) {
      result.push([...currentPath]);
      return;
    }
    // 遍历所有可行的下一条边
    for (const {edge, idx} of nextEdges) {
      // 标记边已访问
      visitedEdges.add(idx);
      // 拼接路径：仅追加边的末尾元素，避免重复值
      currentPath.push(edge[1]);
      // 递归搜索
      dfs(currentPath, visitedEdges);
      // 回溯：撤销路径和访问标记，不影响其他分支
      currentPath.pop();
      visitedEdges.delete(idx);
    }
  }
  // 初始化所有以0开头的边作为起始点
  const startEdges = input.map((edge, idx) => ({edge, idx}))
    .filter(({edge}) => edge[0] === 0);
  for (const {edge, idx} of startEdges) {
    dfs([...edge], new Set([idx]));
  }
  return result;
}

// 测试调用
console.log(getPaths(input)) // 输出与预期完全匹配

实现说明 #

• 用Set存储已访问的边索引，避免相同内容的边被误判，回溯时自动清除当前分支标记不会污染其他搜索路径
• 路径拼接仅追加边的第二个元素，避免重复存储相邻相同值
• 所有状态都在递归调用内部维护，不会出现全局变量冲突导致的栈溢出问题
• 仅当无后续可行边时才存入结果，完全符合终止遍历的要求

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