Meadowfield

Meadowfield 村不是很大。 它由 11 个地点和 14 条道路组成。 它可以用roads数组来描述：

  1. const roads = [
  2.   "Alice's House-Bob's House",   "Alice's House-Cabin",
  3.   "Alice's House-Post Office",   "Bob's House-Town Hall",
  4.   "Daria's House-Ernie's House", "Daria's House-Town Hall",
  5.   "Ernie's House-Grete's House", "Grete's House-Farm",
  6.   "Grete's House-Shop",          "Marketplace-Farm",
  7.   "Marketplace-Post Office",     "Marketplace-Shop",
  8.   "Marketplace-Town Hall",       "Shop-Town Hall"
  9. ];

Meadowfield - 图1

村里的道路网络形成了一个图。 图是节点（村里的地点）与他们之间的边（道路）的集合。 这张图将成为我们的机器人在其中移动的世界。

字符串数组并不易于处理。 我们感兴趣的是，我们可以从特定地点到达的目的地。 让我们将道路列表转换为一个数据结构，对于每个地点，都会告诉我们从那里可以到达哪些地点。

  1. function buildGraph(edges) {
  2.   let graph = Object.create(null);
  3.   function addEdge(from, to) {
  4.     if (graph[from] == null) {
  5.       graph[from] = [to];
  6.     } else {
  7.       graph[from].push(to);
  8.     }
  9.   }
  10.   for (let [from, to] of edges.map(r => r.split("-"))) {
  11.     addEdge(from, to);
  12.     addEdge(to, from);
  13.   }
  14.   return graph;
  15. }
  17. const roadGraph = buildGraph(roads);

给定边的数组，buildGraph创建一个映射对象，该对象为每个节点存储连通节点的数组。

它使用split方法，将形式为"Start-End"的道路字符串，转换为两元素数组，包含起点和终点作为单个字符串。