编写一个函数，实现图的遍历（广度优先搜索、深度优先搜索）

推荐答案

// www.javascriptcn.com code example
// 图的邻接表表示
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

// 广度优先搜索 (BFS)
function bfs(graph, start) {
  const queue = [start];
  const visited = new Set();
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

// 深度优先搜索 (DFS)
function dfs(graph, start) {
  const stack = [start];
  const visited = new Set();
  visited.add(start);

  while (stack.length > 0) {
    const node = stack.pop();
    console.log(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
}

// 测试
console.log('BFS:');
bfs(graph, 'A'); // 输出: A B C D E F

console.log('DFS:');
dfs(graph, 'A'); // 输出: A C F E B D

本题详细解读

图的表示

在代码中，图是通过邻接表来表示的。邻接表是一种常见的图表示方法，它使用一个对象（或字典）来存储图中的每个节点及其相邻节点。例如，graph['A'] 返回节点 A 的所有相邻节点。

广度优先搜索 (BFS)

广度优先搜索是一种图的遍历算法，它从起始节点开始，逐层遍历图中的节点。BFS 使用队列来存储待访问的节点，确保先访问的节点先被处理。

1. 初始化：将起始节点加入队列，并标记为已访问。
2. 遍历：从队列中取出一个节点，访问它，并将其所有未访问的相邻节点加入队列。
3. 重复：重复上述步骤，直到队列为空。

深度优先搜索 (DFS)

深度优先搜索是另一种图的遍历算法，它从起始节点开始，沿着一条路径尽可能深地访问节点，直到无法继续为止，然后回溯并尝试其他路径。DFS 使用栈来存储待访问的节点。

1. 初始化：将起始节点加入栈，并标记为已访问。
2. 遍历：从栈中取出一个节点，访问它，并将其所有未访问的相邻节点加入栈。
3. 重复：重复上述步骤，直到栈为空。

代码分析

• BFS：使用队列实现，确保先访问的节点先被处理，适合用于寻找最短路径等问题。
• DFS：使用栈实现，适合用于寻找路径、拓扑排序等问题。

测试

在测试部分，我们分别调用 bfs 和 dfs 函数，从节点 A 开始遍历图，并输出遍历结果。