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

Question

我JSON 与来自大陆的国家。每个国家都有一个包含其边界国家的数组。给定来自同一大陆的 2 个国家/地区，return 这是路线。例如。：巴西和美国 -> 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 转换为图表。

Answer 1

结帐 Dijkstra's algorithm 在这里您可以假设作为算法节点的国家和接壤国家的距离为 1，而 non-bordering 国家没有边界。

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

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

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

Find path between 2 countries with borders

javascript

algorithm

breadth-first-search