广度优先搜索（BFS）

广度优先搜索（Breadth-First-Search），我们平常都简称 BFS。直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

image.png

深度优先搜索（DFS）

深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。

假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

走迷宫的例子很容易能看懂，我们现在再来看下，如何在图中应用深度优先搜索，来找某个顶点到另一个顶点的路径。

你可以看下面这幅图。搜索的起始顶点是 s，终止顶点是 t，我们希望在图中寻找一条从顶点 s 到顶点 t 的路径。如果映射到迷宫那个例子，s 就是你起始所在的位置，t 就是出口。我用深度递归算法，把整个搜索的路径标记出来了。这里面实线箭头表示遍历，虚线箭头表示回退。从图中我们可以看出，深度优先搜索找出来的路径，并不是顶点 s 到顶点 t 的最短路径。

image.png

代码demo

其中存储的图数据如下图所示

image.png

    /**
     * 使用邻接表存储图
     * 使用Map表示相邻顶点列表
    */
    class Graph{
      constructor(isDirected = false) {
        // 图是否有向（默认无向）
        this.isDirected = isDirected;
        // 使用数组存储所有顶点
        this.vertices = [];
        // 使用顶点名作为键，相邻顶点作为值
        this.adjList = new Map();
      }
      // 添加顶点
      addVertex(v){
        if(!this.vertices.includes(v)){
          this.vertices.push(v);
          // 顶点v的相邻顶点使用Set存储
          this.adjList.set(v, new Set());
        }
      }
      // 添加边，参数为连接边的两个顶点
      addEdge(v, w){
        if(!this.vertices.includes(v)){
          this.addVertex(v);
        }
        if(!this.vertices.includes(w)){
          this.addVertex(w);
        }
        this.adjList.get(v).add(w);
        // 如果是无向图，则再添加一条w到v的边
        if(!this.isDirected){
          this.adjList.get(w).add(v);
        }
      }
      // 返回顶点列表
      getVertices(){
        return this.vertices;
      }
      // 返回邻接表
      getAdjList(){
        this.adjList;
      }
      // 广度优先搜索（Breadth-First-Search），求出顶点s到顶点t的最短路径
      bfs(s, t){
        if(s === t){
          return;
        }
        // visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问
        let visited = {s:true};
        // queue 是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点
        let queue = [s];
        // prev 用来记录搜索路径
        let prev = {};

        while(queue.length !== 0){
          // 出队，取队列第1个顶点
          const v = queue.shift();
          if(v === t){
            console.log('找到了', prev)
            break;
          }
          // 取顶点v的相邻顶点
          const list = this.adjList.get(v)
          for(let i of list){
            if(visited[i] !== true){
              visited[i] = true;
              // 入队
              queue.push(i);
              prev[i] = v;
            }
          }
        }

        this.print(s, t, prev);
      }

      // 深度优先搜索（Depth-First-Search）,深度优先搜索找出来的路径，并不是顶点 s 到顶点 t 的最短路径。
      dfs(s, t){
        if(s === t){
          return;
        }
        // visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问
        let visited = {s:true};
        // stack 是一个栈，用来存储深度优先遍历的顶点
        let stack = [s];
        // prev 用来记录搜索路径
        let prev = {};

        while(stack.length !== 0){
          // 出栈
          const v = stack.pop();
          if(v === t){
            console.log('找到了', prev)
            break;
          }
          const list = this.adjList.get(v);
          for(let i of list){
            if(visited[i] !== true){
              visited[i] = true;
              // 入栈
              stack.push(i);
              prev[i] = v;
            }
          }
        }

        this.print(s, t, prev);
      }

      print(s, t, prev){
        let q = t;
        let arr = [];
        while(true){
          arr.push(q);
          q = prev[q];
          if(q === s){
            arr.push(q);
            // 打印路径
            console.log(arr.reverse())
            break;
          }
        }
      }
    }

    const graph = new Graph();

    const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
    for(let i of myVertices){
      graph.addVertex(i);
    }
    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');
    graph.addEdge('A', 'D');
    graph.addEdge('C', 'D');
    graph.addEdge('C', 'G');
    graph.addEdge('D', 'H');
    graph.addEdge('D', 'G');
    graph.addEdge('B', 'E');
    graph.addEdge('B', 'F');
    graph.addEdge('E', 'I');

    console.log(graph)

    graph.dfs('A', 'H');