时间戳

首页 > 解决方案 > JS中的自定义排序/路径查找

javascript - JS中的自定义排序/路径查找

问题描述

我正在尝试制定一些排序/路径查找算法。作为起点，我总是有以下格式的开始 ID 和完成 ID（开始 + 最后一个节点的 ID）：

{"START_ID": "1z2x", "FINISH_ID":"cc2v"}

下一部分是我的对象（边）要排序/找到路径的数组。每个对象的构造方式如下：

{"ID_FROM": "1z2x", "ID_TO": "wdf3"}

如您所见，每个对象都有起始节点和结束节点。因为我总是知道整个路径的开始节点和完成节点，所以我想编写路径。

例子：

开始 + 结束节点：

{"START_ID": "123v", "FINISH_ID":"8s6h"}

带边的数组：

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}, {"ID_FROM":"plnx", "ID_TO":"7777"}]

从上面我想收到的路径是：

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"plnx", "ID_TO":"7777"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}]

此外，可以有多个对象指向同一条边（它们应该在以下索引中），例如：

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"plnx", "ID_TO":"7777"}]

其路径将是：

 [{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"13kj", "ID_TO":"plnx"},, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"plnx", "ID_TO":"7777"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}]

一些限制/信息： -> 开始和结束节点始终是已知的 -> 边数可以从 2 到 10 不等 -> 可以有多个对象指向具有相同的 ID_FROM 和 ID_TO <- 它们不是重复的，应该是在以下职位

如果有人可以帮助我，我将不胜感激。

最好的问候，并在此先感谢您！垫

编辑：

我想建立一种可以去 ID1 -> ID2 -> ID3 <- ID4 的方式。假设我仍然知道开始和结束（ID1 和 ID4）。

例子：

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"8542", "ID_TO":"13kj"}]

在 START_ID = 123v 和 FINISH_ID = 8542 的情况下，路径应如下所示：

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"13kj", "ID_TO":"plnx"},  {"ID_FROM":"8542", "ID_TO":"plnx"}]

标签： javascript

解决方案

使用简单的DFS算法，您可以找到一条路径（如果存在）（不一定是最短的）

function recursive_DFS(nodes, El, head, finish){
  if(head === finish){
    nodes.push(head)
    return nodes;
  }else{
    nodes.push(head)
    for(const next of (El[head] || [])){
      t = recursive_DFS(nodes, El, next, finish)
      if(t) return t;
    }
    nodes.pop(head)
  }
}

// just make sure to produce the output in the format you want
function nodes_to_edges(nodes){
  edges = []
  for(let i = 1; i < nodes.length; ++i){
    edges.push({ID_FROM: nodes[i-1], ID_TO: nodes[i]})
  }
  return edges;
}

function find_route(path, E){
  El = {}
  // make it easier to lookup afterwards
  for(const {ID_FROM, ID_TO} of E){
    if(!El[ID_FROM]) El[ID_FROM] = [ID_TO]
    else El[ID_FROM].push(ID_TO)
  }
  return nodes_to_edges(recursive_DFS([], El, path.START_ID, path.FINISH_ID));
}

测试：

console.log(find_route(
{"START_ID": "123v", "FINISH_ID":"8s6h"}, 
  [{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, 
  {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}, 
  {"ID_FROM":"plnx", "ID_TO":"7777"}]))

如果您对最佳性能感兴趣，您可能希望将递归 DFS 替换为迭代版本。如果您想确保找到最短路径，您可以使用BFS代替，但这需要先进先出而不是后进先出数据结构。

function annotate_paths(origin, El, head){
  for(const next of (El[head] || [])){
    if(!origin[next]){
      // keep track of where it comes from
      origin[next] = head;
      t = annotate_paths(origin, El, next)
    }
  }
}

// just make sure to produce the output in the format you want
function reconstruct(origin, node, START){
  edges = []
  prevNode = node;
  while(origin[node] !== START){
    const prevNode = node;
    node = origin[node];
    edges.push({ID_FROM: node, ID_TO: prevNode})
  }
  return edges.reverse();
}

function find_route(path, E){
  El = {}
  // make it easier to lookup afterwards
  for(const {ID_FROM, ID_TO} of E){
    if(!El[ID_FROM]) El[ID_FROM] = [ID_TO]
    else El[ID_FROM].push(ID_TO)
  }
  
  const {START_ID, FINISH_ID} = path;
  const START = {}
  origin1 = {}
  origin2 = {}
  origin1[START_ID] = START;
  origin2[FINISH_ID] = START;
  annotate_paths(origin1, El, START_ID)
  annotate_paths(origin2, El, FINISH_ID)

  for(const meetAt in origin1){
    if(origin2[meetAt]){
      path1 = reconstruct(origin1, meetAt, START) // Path from ID_FROM to meeting node
      path2 = reconstruct(origin2, meetAt, START) // Path from ID_TO to the meeting node
      return [...path1, ...path2.reverse()]
    }
  }
  return null;
}

// Original question
console.log(find_route(
  {"START_ID": "123v", "FINISH_ID":"8s6h"}, 
  [
    {"ID_FROM":"123v", "ID_TO":"985j"}, 
    {"ID_FROM":"13kj", "ID_TO":"plnx"}, 
    {"ID_FROM":"985j", "ID_TO":"13kj"}, 
    {"ID_FROM":"7777", "ID_TO":"8s6h"}, 
    {"ID_FROM":"plnx", "ID_TO":"7777"}
  ]))

// Updated question
console.log(find_route(
  {
    START_ID: '123v', 
    FINISH_ID: '8542'
  },
  [
    {"ID_FROM":"123v", "ID_TO":"985j"}, 
    {"ID_FROM":"13kj", "ID_TO":"plnx"}, 
    {"ID_FROM":"985j", "ID_TO":"13kj"}, 
    {"ID_FROM":"8542", "ID_TO":"13kj"}
  ]))

推荐阅读