BFS的使用场景：

    • 遍历（树）
    • 寻找最短路径（图）

    模板：

    1. /**
    2.  * Return the length of the shortest path between root and target node.
    3.  */
    4. int BFS(Node root, Node target) {
    5.     Queue<Node> queue;  // store all nodes which are waiting to be processed
    6.     int step = 0;       // number of steps neeeded from root to current node
    7.     // initialize
    8.     add root to queue;
    9.     // BFS
    10.     while (queue is not empty) {
    11.         step = step + 1;
    12.         // iterate the nodes which are already in the queue
    13.         int size = queue.size();
    14.         for (int i = 0; i < size; ++i) {
    15.             Node cur = the first node in queue;
    16.             return step if cur is target;
    17.             for (Node next : the neighbors of cur) {
    18.                 add next to queue;
    19.             }
    20.             remove the first node from queue;
    21.         }
    22.     }
    23.     return -1;          // there is no path from root to target
    24. }
    1. 如代码所示，在每一轮中，队列中的结点是等待处理的结点。
    2. 在每个更外一层的 while 循环之后，我们距离根结点更远一步。变量 step 指示从根结点到我们正在访问的当前结点的距离。
      1. /**
      2. * Return the length of the shortest path between root and target node.
      3. */
      4. int BFS(Node root, Node target) {
      5.  Queue<Node> queue;  // store all nodes which are waiting to be processed
      6.  Set<Node> used;     // store all the used nodes
      7.  int step = 0;       // number of steps neeeded from root to current node
      8.  // initialize
      9.  add root to queue;
      10.  add root to used;
      11.  // BFS
      12.  while (queue is not empty) {
      13.      step = step + 1;
      14.      // iterate the nodes which are already in the queue
      15.      int size = queue.size();
      16.      for (int i = 0; i < size; ++i) {
      17.          Node cur = the first node in queue;
      18.          return step if cur is target;
      19.          for (Node next : the neighbors of cur) {
      20.              if (next is not in used) {
      21.                  add next to queue;
      22.                  add next to used;
      23.              }
      24.          }
      25.          remove the first node from queue;
      26.      }
      27.  }
      28.  return -1;          // there is no path from root to target
      29. }

      有两种情况你不需要使用哈希集：

      1. 你完全确定没有循环，例如，在树遍历中；
      2. 你确实希望多次将结点添加到队列中。