BFS

# 应用场景

找到的路径一定是最短的，但空间复杂度可能大于 DFS

# 代码框架

//起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
 queue<Node> q; // 核心数据结构
 set<Node> visited; // 避免走回头路   
 q.push(start); // 将起点加入队列
 visited.insert(start);  int step = 0; // 记录扩散的步数 
 while (q not empty) {
   int sz = q.size();`    
​    /* 将当前队列中的所有节点向四周扩散 */ 
   for (int i = 0; i < sz; i++) {    	
   Node cur = q.front();           
   q.pop();           
 /* 划重点：这里判断是否到达终点 */ 
   if (cur is target)        return step;   

  /* 将 cur 的相邻节点加入队列 */ 
   for (Node x : cur.adj()) {
     if (x not in visited) {      
         q.push(x);  
         visited.insert(x);     
     }   
   }    

​   /* 划重点：更新步数在这里 */
 step++;  
 }
}