javascript - 在 JS 对象图中查找节点之间的路径

Question

我怎样才能得到这个结果：

[
  {Paris,Amsterdam,Berlin},
  {Paris,Bruxelles,Amsterdam,Berlin},
  {Paris,Bruxelles,Berlin}
]

从这个数组：

[
  { 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' } 
]

我想从这个数组映射数据，以获得从一个城市到另一个城市的路径的所有可能性，例如从“巴黎”到“柏林”。

标签： javascriptjavascript-objectsgraph-theory

Answer 1

输入图 是一个DAG，如下所示：

  +-----------------------+
  |                       |
  |                       v
Paris -> Bruxelles -> Amsterdam -> Berlin
             |                       ^
             |                       |
             +-----------------------+

我们可以构建一个对象，其源字符串映射到其可能目的地的数组，这比输入对象更方便使用，然后在图上运行DFS并产生每个结果路径。

function *findPaths(graph, src, dst, path=[]) {
  if (src === dst) {
    yield path.concat(dst);
  }
  else if (graph[src]) {
    path.push(src);
    
    for (const neighbor of graph[src]) {
      yield *findPaths(graph, neighbor, dst, path, visited);
    }
    
    path.pop(src);
  }
};

const graphify = routes => {
  const graph = {};
  
  for (const node of routes) {
    if (!graph[node.V1]) {
      graph[node.V1] = [];
    }
    
    graph[node.V1].push(node.V2)
  }
  
  return graph;
};

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' } 
];

console.log(...findPaths(graphify(routes), "Paris", "Berlin"));

如果您预计图中有循环，请添加 aSet以跟踪访问过的节点，以避免在遍历期间重新访问它们：

function *findPaths(graph, src, dst, path=[], visited=(new Set())) {
  if (src === dst) {
    yield path.concat(dst);
  }
  else if (graph[src] && !visited.has(src)) {
    visited.add(src);
    path.push(src);
    
    for (const neighbor of graph[src]) {
      yield *findPaths(graph, neighbor, dst, path, visited);
    }
    
    visited.delete(src);
    path.pop(src);
  }
};

const graphify = routes => {
  const graph = {};
  
  for (const node of routes) {
    if (!graph[node.V1]) {
      graph[node.V1] = [];
    }
    
    graph[node.V1].push(node.V2)
  }
  
  return graph;
};

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: 'Paris', D: '6:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Paris', D: '9:20' } 
];

console.log(...findPaths(graphify(routes), "Paris", "Berlin"));

如果您想考虑行程时间（边权重），请使用Dijkstra 算法。实现更加复杂，因为我们需要一个优先级队列（最小/斐波那契堆）来有效地提取最短的暂定距离。