使用 JavaScript 的 Map() 方法解决广度优先和深度优先搜索问题

JavaScript 1年前 35

JavaScript 的map()方法是一个包含键值对的对象。对象的键和值通过冒号 (:) 连接，而 map 是通过箭头符号（=>）连接。

以下是 JavaScript 中的对象：

{ a: [ 1, 2, 3 ], b: 2, c: 3 }

以下是 JavaScript 中的 map：

{ 'a' => [ 1, 2, 3 ], 'b' => 2, 'c' => 3 }

map() 方法是解决如：图、最短距离、最佳路线等算法和数据结构行之有效的方法。许多运输公司都使用这个方法来创建应用，我们将在这篇教程中练习类似的事情。

为了方便倾向使用视觉资料来学习的读者，我在每个章节之后都添加了视频资料。

本文目标

本教程的目的是教会你使用map()方法解决广度优先和深度优先搜索的算法问题。

通过学习，你将掌握map()方法的基础知识，同时也将从另一个角度来观察类似图这样的算法和数据结构问题，以及广度优先搜索（BFS）和深度优先搜索（DFS）。

前提条件

本教程假设你了解基本的 JavaScript 概念，例如字符串、数组、对象和集合。阅读过有关算法和数据结构的信息也会有所帮助。

让我们开始吧！

问题

尼日利亚有 36 个州，游客可以通过公路、空中和水运（路线 routes）从一个州移动到另一个州。我们要做的是以下编程：

用图展示每个州和其他州之间的连接。
检查两个州之间是否有连接。

我们从尼日利亚的 36 个州中挑选了 11 个州来进行创建：

ENUGU, ABIA, SOKOTO, NIGER, LAGOS, OGUN, BAYELSA, AKWAIBOM, ANAMBRA, IMO, EBONYI

路线如下：

ENUGU to LAGOS
ENUGU to NIGER
NIGER to SOKOTO
NIGER to ANAMBRA
SOKOTO to ANAMBRA
OGUN to LAGOS
OGUN to ABIA
OGUN to EBONYI
OGUN to BAYELSA
EBONYI to ABIA

我们来使用这些数据解决问题！

如何解决问题

上一章节我们讲解了问题，现在我们来解决问题，在这篇教程中我将使用 Replit。

Replit 是一个配置完全的 IDE，方便你可以快速地编写和检查程序。

如何创建 Map

我们首先要解决的问题是如何展现每一个州和其他州之间的连接。

我们先定义这 11 个州和路线，输入以下代码：


const states = 'ENUGU ABIA SOKOTO NIGER LAGOS OGUN BAYELSA AKWAIBOM ANAMBRA IMO EBONYI'.split(' ');

const routes = [  ['ENUGU', 'LAGOS'],
  ['ENUGU', 'NIGER'],
  ['NIGER', 'SOKOTO'],
  ['NIGER', 'ANAMBRA'],
  ['SOKOTO', 'ANAMBRA'],
  ['OGUN', 'LAGOS'],
  ['OGUN', 'ABIA'],
  ['OGUN', 'EBONYI'],
  ['OGUN', 'BAYELSA'],
  ['EBONYI', 'ABIA'],
];

创建一个新的 map() 也可以称作图，并命名为 connections:

const connections = new Map();

接着输入以下代码：

states.forEach((state) => {
  connections.set(state, []);
});

这段代码迭代所有 states。每次迭代，都将当前 state 作为connections图中的键，并设置初始值为空数组（[]）。

如果你在控制台打印 connections，会得到以下结果：

Map(11) {
  'ENUGU' => [],
  'ABIA' => [],
  'SOKOTO' => [],
  'NIGER' => [],
  'LAGOS' => [],
  'OGUN' => [],
  'BAYELSA' => [],
  'AKWAIBOM' => [],
  'ANAMBRA' => [],
  'IMO' => [],
  'EBONYI' => []
}

目前为止，上述图对应的图像如下：

使用 JavaScript 的 Map() 方法解决广度优先和深度优先搜索问题

当前州的图像展示

输入以下代码：

routes.forEach(route => {
  const departure = [...route][0];
  const destination = [...route][1];
  
  connections.get(departure).push(destination);
  connections.get(destination).push(departure);
});

上述代码将州添加到空数组，作为前一步键对应的值。代码循环迭代路线（routes）数组，并提取出每一个路线。

departure（出发）州为每一个路线数组的第一个值，而 destination（目的地）州为每一个路线数组的第二个值。

然后将目的地州添加到出发州对应的值数组，最后将出发州添加到目的地州的值数组中。

在控制台打印connections，会得到以下结果：

Map(11) {
  'ENUGU' => [ 'LAGOS', 'NIGER' ],
  'ABIA' => [ 'OGUN', 'EBONYI' ],
  'SOKOTO' => [ 'NIGER', 'ANAMBRA' ],
  'NIGER' => [ 'ENUGU', 'SOKOTO', 'ANAMBRA' ],
  'LAGOS' => [ 'ENUGU', 'OGUN' ],
  'OGUN' => [ 'LAGOS', 'ABIA', 'EBONYI', 'BAYELSA' ],
  'BAYELSA' => [ 'OGUN' ],
  'AKWAIBOM' => [],
  'ANAMBRA' => [ 'NIGER', 'SOKOTO' ],
  'IMO' => [],
  'EBONYI' => [ 'OGUN', 'ABIA' ]
}

这种类型的图是无向的。在无向图中，你可以从节点（node）移动到边（edge），然后从边移回节点。在我们的例子中，节点是出发州，而边是目的地州。

以下图像对此做了展示：

使用 JavaScript 的 Map() 方法解决广度优先和深度优先搜索问题

无向图展示路线

黑色箭头指向目的地州，而白色箭头指向出发州。

若需要创建有向图，可以编写以下代码：

routes.forEach(route => {
  connections.get([...route][0]).push([...route][1]);
});

输出如下：

Map(11) {
  'ENUGU' => [ 'LAGOS', 'NIGER' ],
  'ABIA' => [],
  'SOKOTO' => [ 'ANAMBRA' ],
  'NIGER' => [ 'SOKOTO', 'ANAMBRA' ],
  'LAGOS' => [],
  'OGUN' => [ 'LAGOS', 'ABIA', 'EBONYI', 'BAYELSA' ],
  'BAYELSA' => [],
  'AKWAIBOM' => [],
  'ANAMBRA' => [],
  'IMO' => [],
  'EBONYI' => [ 'ABIA' ]
}

以下是图像展示：

使用 JavaScript 的 Map() 方法解决广度优先和深度优先搜索问题

有向图展示路线

如果你觉得难以理解，仔细观察两段代码的输出结果和路线，你会发现代码变简单了许多。

我们已经能够展示这些州是如何以编程方式连接的。看看到目前为止的代码是什么样的：


const states = 'ENUGU ABIA SOKOTO NIGER LAGOS OGUN BAYELSA AKWAIBOM ANAMBRA IMO EBONYI'.split(' ');

const routes = [
  ['ENUGU', 'LAGOS'],
  ['ENUGU', 'NIGER'],
  ['NIGER', 'SOKOTO'],
  ['NIGER', 'ANAMBRA'],
  ['SOKOTO', 'ANAMBRA'],
  ['OGUN', 'LAGOS'],
  ['OGUN', 'ABIA'],
  ['OGUN', 'EBONYI'],
  ['OGUN', 'BAYELSA'],
  ['EBONYI', 'ABIA'],
];

const connections = new Map();

states.forEach((state) => {
  connections.set(state, []);
});

console.log(connections)

routes.forEach(route => {
  const departure = [...route][0];
  const destination = [...route][1];
  
  connections.get(departure).push(destination);
  connections.get(destination).push(departure);
});

console.log(connections)

接下来我们解决下一个问题（检查是否可以连接两个州）。我们将用两种办法来解决，首先使用广度优先搜索算法，然后使用深度优先搜索算法。

如何使用广度优先搜索（BFS）

BFS 是一种用于检查树或者图的算法，通过探索一个父（节点）的所有直系子（边）之后再探索孙节点，以这样的方式一直持续到树或者图的底部。

例如，在我们的例子中，我们想检查 ENUGU 和 ABIA 之间有没有连接。

BFS 会从检查 Enugu 的直线路线（LAGOS 和 NIGER）开始。因为 ABIA 并非直接和 ENUGU 联系的，算法会接着检查和 LAGOS 相连的州。

接着，算法会检查和 NIGER 相连的州，这个过程会一直持续到算法找到 ABIA 或者走到头。程序就会终止。

BFS 使用队列数据结构。也就是说，项目会在数组的一端被添加，然后在另一端被删除。在我们的例子中，队列会保存所有还未被访问的州，我们会在编程中看到详细行为：

我们从创建一个命名为 bfs函数开始编写 BFS：

function bfs(departureState, destinationState) {

}

该函数接受两个参数：departureState和 destinationState。

在函数内部，定义一个 queue ，并将 departureState 添加进去：

  const queue = [departureState];

我们将 departureState添加至queue数组，是因为它保存了所有尚未被访问的节点。（译者注：除了起始点以外，广度优先搜索的无向图中所有节点都是自己顶点-边关系的顶点以及其他顶点-边关系中的边，这里 queue 数组记录的是所有尚未作为顶点被访问的节点，而后文的visited集合记录的是所有作为边已被访问的节点）。

接下来，定义一个空[Set()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/Set)，并命名为visited:

  const visited = new Set();

visited变量正如其名，将记录所有访问过的州。

现在我们可以从departureState开始我们的导航搜索，输入以下代码：

while (queue.length > 0) {
    
}

循环将在queue非空时一直运行，也就是说只要还有州，就不会停下来。

在访问开始之前，将departureState从queue中删除，以防止无限循环。使用以下代码：

    const state = queue.shift();

由于队列执行先进先出原则，所以queue数组第一个或者顶部的 state会优先被移除，并从尾部或者底部插入新的项目。

检索与节点（state）相连的边（destinations）：

    const destinations = connections.get(state);

现在我们可以访问当前节点（state）的所有子边（destinations），让我们检查一下，它们是否为destinationState：

使用以下代码，循环迭代destinations：

for (const destination of destinations) {
    
}

在每一次循环都检查destination是否为destinationState，如果结果是true, 在控制台打印消息：

      if (destination === destinationState) {
          console.log("Found => " + destination);
      }

然后，如果destination尚不是visited的元素，将 destination添加到visited和queue数组中，

      if (!visited.has(destination)) {
        visited.add(destination);
        queue.push(destination);
      }

所有州都添加到visited数组后，程序终止。因为就没有州可以被添加到queue。

bfs函数如下：

function bfs(departureState, destinationState) {
  const queue = [departureState];
  const visited = new Set();

  while (queue.length > 0) {
    const state = queue.shift();
    const destinations = connections.get(state);

    for (const destination of destinations) {
      if (destination === destinationState) {
          console.log("Found => " + destination);
      }

      if (!visited.has(destination)) {
        visited.add(destination);
        queue.push(destination);
      }
    }
  }
}

检查两个州之间是否有连接，比方说 ENUGU 和 SOKOTO，调用bfs函数：

bfs("ENUGU", "SOKOTO")

以下是输出：

Map(11) {
  'ENUGU' => [],
  'ABIA' => [],
  'SOKOTO' => [],
  'NIGER' => [],
  'LAGOS' => [],
  'OGUN' => [],
  'BAYELSA' => [],
  'AKWAIBOM' => [],
  'ANAMBRA' => [],
  'IMO' => [],
  'EBONYI' => []
}
Map(11) {
  'ENUGU' => [ 'LAGOS', 'NIGER' ],
  'ABIA' => [ 'OGUN', 'EBONYI' ],
  'SOKOTO' => [ 'NIGER', 'ANAMBRA' ],
  'NIGER' => [ 'ENUGU', 'SOKOTO', 'ANAMBRA' ],
  'LAGOS' => [ 'ENUGU', 'OGUN' ],
  'OGUN' => [ 'LAGOS', 'ABIA', 'EBONYI', 'BAYELSA' ],
  'BAYELSA' => [ 'OGUN' ],
  'AKWAIBOM' => [],
  'ANAMBRA' => [ 'NIGER', 'SOKOTO' ],
  'IMO' => [],
  'EBONYI' => [ 'OGUN', 'ABIA' ]
}
Found => SOKOTO
Found => SOKOTO

假设你不是很理解现在的内容，我建议你在不同节点暂停代码，来观察程序流。

如何使用深度优先搜索

DFS 算法一次只取一个节点的一个子节点。它继续向下搜索该节点的一个子节点，直到走到死胡同，然后再回溯并尝试另一个子节点。

在我们的例子中，假设我们需要检查 ENUGU 和 ABIA 之间是否有连接。

DFS 会从 Enugu 开始，并检查第一个与之相连的州（LAGOS）。因为 LAGOS 不是 ABIA，搜索会继续检查 LAGOS 紧密连接的下一个州。搜索会一直持续到找到 ABIA 或者走到死胡同。然后回溯并尝试另一个节点。

DFS 使用栈来记录访问过的项目（在我们的例子中就是州）。当栈为空的时候，搜索终止。我们将使用递归来编写 DFS 算法，让我们开始吧！

首先创建一个名为dfs的函数，该函数将接受三个参数（departureState、 destinationState和 visited）：


function dfs(departureState, destinationState, visited = new Set()) {
    
}

visited集合将保存所有访问过的州，以防止无限循环。所以第一件事是在dfs函数，将departureState添加到visited数组。输入以下代码：

  visited.add(departureState);

接着，由departureState得出destinations：

  const destinations = connections.get(departureState);

在获取departureState的destinations之后，我们要就此迭代循环，如下：

  for (let destination of destinations) {
      
  }

在循环中，检查当前destination是否为destinationState，如果是true，在控制台打印代码：

    if (destination === destinationState) {
      console.log("Found => " + destination);
    }

接着，如果destination还未被访问，再次调用dfs（递归）——但此时，使用destination作为departureState的实参：

    if (!visited.has(destination)) {
      dfs(destination, destinationState, visited)
    }

destinationState保持不变，visited（访问过的）Set() 不再为空数组。此时，位于循环中，但并不在 visited 集合中的 destination 将被存储到栈。

dfs函数如下：


function dfs(departureState, destinationState, visited = new Set()) {
  
  visited.add(departureState);
  
  const destinations = connections.get(departureState);

  for (let destination of destinations) {
    if (destination === destinationState) {
      console.log("Found => " + destination);
    }

    if (!visited.has(destination)) {
      dfs(destination, destinationState, visited)
    }
  }
}

检查两个州之间是否连接，如 ENUGU 和 SOKOTO，调用dfs函数：

dfs("ENUGU", "SOKOTO")

输出如下：

Map(11) {
  'ENUGU' => [],
  'ABIA' => [],
  'SOKOTO' => [],
  'NIGER' => [],
  'LAGOS' => [],
  'OGUN' => [],
  'BAYELSA' => [],
  'AKWAIBOM' => [],
  'ANAMBRA' => [],
  'IMO' => [],
  'EBONYI' => []
}
Map(11) {
  'ENUGU' => [ 'LAGOS', 'NIGER' ],
  'ABIA' => [ 'OGUN', 'EBONYI' ],
  'SOKOTO' => [ 'NIGER', 'ANAMBRA' ],
  'NIGER' => [ 'ENUGU', 'SOKOTO', 'ANAMBRA' ],
  'LAGOS' => [ 'ENUGU', 'OGUN' ],
  'OGUN' => [ 'LAGOS', 'ABIA', 'EBONYI', 'BAYELSA' ],
  'BAYELSA' => [ 'OGUN' ],
  'AKWAIBOM' => [],
  'ANAMBRA' => [ 'NIGER', 'SOKOTO' ],
  'IMO' => [],
  'EBONYI' => [ 'OGUN', 'ABIA' ]
}
Found => SOKOTO
Found => SOKOTO