JS对象图节点路径查找：从给定数组获取巴黎到柏林的所有路径

要找出从Paris到Berlin的所有可行路径，这本质是有向图的遍历问题——你的路线数组就是图的边集合，每个城市是节点，每条路线是一条有向边。我们可以用**深度优先搜索（DFS）**来递归探索所有可能的路径，具体实现如下：

步骤1：准备数据与构建邻接表 #

首先把原始路线数据转换成邻接表结构，这样能快速查询每个城市的所有可达后续城市，大幅提升遍历效率：

// 你的原始路线数据
const routes = [
  { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
  { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
  { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' }
];

// 构建邻接表：key为出发城市，value为可达城市数组
const adjacencyList = routes.reduce((acc, route) => {
  if (!acc[route.V1]) acc[route.V1] = [];
  acc[route.V1].push(route.V2);
  return acc;
}, {});

步骤2：实现DFS路径查找函数 #

通过递归的DFS遍历，从起点出发探索所有分支，当到达终点时记录完整路径：

function findAllPaths(startCity, endCity, adjList) {
  const result = [];

  // 递归DFS核心函数
  function dfs(current, path) {
    const updatedPath = [...path, current];

    // 到达终点，保存路径
    if (current === endCity) {
      result.push(updatedPath);
      return;
    }

    // 当前城市无后续路线，终止递归
    if (!adjList[current]) return;

    // 遍历所有可达的下一个城市
    adjList[current].forEach(nextCity => {
      // 注：你的数据无循环路线，无需判断重复访问；若存在循环，需添加visited集合过滤已访问城市
      dfs(nextCity, updatedPath);
    });
  }

  // 从起点开始遍历
  dfs(startCity, []);
  return result;
}

步骤3：调用函数获取结果 #

执行函数后就能得到你需要的所有路径：

const parisToBerlinPaths = findAllPaths('Paris', 'Berlin', adjacencyList);
console.log(parisToBerlinPaths);

输出结果完全匹配你的需求：

[
  ["Paris", "Amsterdam", "Berlin"],
  ["Paris", "Bruxelles", "Amsterdam", "Berlin"],
  ["Paris", "Bruxelles", "Berlin"]
]

额外说明：处理循环路线 #

如果你的数据中存在循环（比如Paris → London → Paris），需要在DFS中加入visited集合避免无限递归，修改后的DFS函数如下：

function dfs(current, path, visited) {
  const updatedPath = [...path, current];
  const updatedVisited = new Set(visited);
  updatedVisited.add(current);

  if (current === endCity) {
    result.push(updatedPath);
    return;
  }

  if (!adjList[current]) return;

  adjList[current].forEach(nextCity => {
    if (!updatedVisited.has(nextCity)) {
      dfs(nextCity, updatedPath, updatedVisited);
    }
  });
}

// 调用时初始传入空集合
dfs(startCity, [], new Set());

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