广度优先搜索（Breadth-First Search，BFS）和深度优先搜索（Depth-First Search，DFS）是两种常见的图遍历算法，用于在图或树等数据结构中搜索或遍历节点

一：定义

1：广度优先搜索：从起始节点开始，首先遍历该节点的所有相邻节点，然后再逐层地遍历下一层相邻节点。使用一个队列来维护待遍历的节点，从队列的头部取出节点并访问，然后将其未访问的相邻节点加入队列尾部，直到队列为空

2：深度优先搜索：从起始节点开始，沿着一条路径一直深入直到无法再继续深入为止，然后回溯到前一个节点，继续探索下一条路径，直到遍历完所有可能的路径或找到目标节点。用一个栈（或递归调用栈）来保存待遍历的节点，每次取出栈顶节点进行访问，将其未访问的相邻节点压入栈中，直到栈为空

二：特点

1：广度优先搜索

A：从起始节点开始，逐层遍历图中的节点，先访问离起始节点最近的节点。

B：使用队列来存储待遍历的节点，保证按照节点的访问顺序进行遍历。

C：用于寻找最短路径，因为在BFS中，首先找到的路径就是最短路径。

D：由于需要存储每个节点的相邻节点，空间复杂度较高。

2：深度优先搜索

A：从起始节点开始，沿着一条路径尽可能深入，直到无法继续深入为止，然后回溯到前一个节点，继续探索其他路径。

B：使用栈（或递归调用栈）来存储待遍历的节点，保证深度优先的顺序。

C：通常用于搜索问题，如图的连通性检测、回溯算法等。

D：由于只需存储当前路径上的节点，空间复杂度较低。

三：总结

1：广度优先搜索以层级逐步扩展搜索范围，而深度优先搜索则沿着一条路径尽可能深入搜索

四：代码

1：BFS

function BFS(graph, start) {
  let visited = new Set();
  let queue = [];
  
  queue.push(start);
  visited.add(start);
  
  while (queue.length > 0) {
    let node = queue.shift();
    process(node);
    
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
        visited.add(neighbor);
      }
    }
  }
}

2：DFS

function DFS(graph, node, visited) {
  if (visited.has(node)) {
    return;
  }
  
  visited.add(node);
  process(node);
  
  for (let neighbor of graph[node]) {
    DFS(graph, neighbor, visited);
  }
}