查找两个有边界的国家之间的路径

Question

我有一个来自大陆的国家的JSON。每个国家都有一个数组，其中包含它的边界国家。给定两个来自同一大洲的国家，返回它的路线。例如:巴西和美国-> 1.科罗比亚，2.帕纳马，3.哥斯达黎加，4.尼卡拉瓜岛，5.宏都拉斯，6.危地马拉，7.梅西科。

我正在努力在一个数组上组织它，只为了做一个BFS (广度优先搜索)。到目前为止，我所拥有的是：

function traverse(main_key, obj) {

obj.forEach(function(key) {
if (visited[main_key] === undefined) {
    visited[main_key] = new Array()
}

visited[main_key].push(obj)

if (typeof(borders[key]) === 'array' && visited[main_key].indeOf(key) !== -1) {
  traverse(borders[key])
} 
  else {
      //do something with the actual value
      console.log(main_key, borders[key], key)
    }
  })      
};

traverse('BRA', borders['BRA'])

下面是JSON示例：https://restcountries.eu/rest/v2/region/americas

我想我的主要问题是我正在努力将这个JSON转换成一个GRAPH。

Answer 1

查看Dijkstra's algorithm，您可以假设在算法中作为节点的国家和边界国家的距离为1，而非边界国家没有边界。

编辑:这是一个使用您指定的数据的实现。将您从JSON样本(整个数组)中获得的数据作为图参数传递，源国家(例如'BRA')，目标国家(例如'USA')。我没有做很多测试，所以我不能保证这是没有bug的。

function dijkstra(graph, source, target) {
  var dist = {};
  var prev = {};
  var vertices = [];
  for (var i = 0; i < graph.length; i++) {
    var vertex = graph[i];
    dist[vertex.alpha3Code] = Infinity;
    prev[vertex.alpha3Code] = null;
    vertices.push(vertex);
  }
  dist[source] = 0;

  while (vertices.length > 0) {
    // Find the vertex having smallest dist.
    var u = vertices.reduce(function(p, current) {return !p || dist[current.alpha3Code] < dist[p.alpha3Code] ? current : p;}, null);
    const index = vertices.indexOf(u);
    vertices.splice(index, 1);
    if (u.borders && Array.isArray(u.borders)) {
      for (var i = 0; i < u.borders.length; i++) {
        var v = u.borders[i];
        const alt = dist[u.alpha3Code] + 1;
        if (alt < dist[v]) {
          dist[v] = alt;
          prev[v] = u;
        }
      }
    }
  }
  var result = [];
  while (target) {
    result.splice(0, 0, target);
    target = prev[target] ? prev[target].alpha3Code : null;
  }
  // Any empty array return means there is no path. For example one of the countries is an island.
  if (result.length === 1) {
    return [];
  }
  return result;
}