图的遍历之BFS

1、队列

队列是一种数据结构，只能从队尾加入元素，从队首弹出元素，特性就是先进入队列的元素先出队，简称FIFO（First In First Out）。

c++的stl里提供了队列容器queue，如下：

• 头文件：#include
• 变量：queue q;
• 入队：q.push(x); //插入x到队尾
• 出队：q.pop(); //删除队首的元素（没有获取）
• 访问：q.front(); //访问对首的元素
• 判空：q.empty();
• 个数：q.size();

2、广度优先搜索

从某个顶点v0出发，依次访问其相邻的每个点，然后逐层向外访问，直到没有可访问点（或找到解）为止。

上图从A点出发进行bfs遍历（蓝色字表示访问顺序）：

• 访问A点（出队），邻接点有B、F、G，入队后队列为BFG
• 访问B点（出队），邻接点有C、D，入队后队列为FGCD
• 访问F点（出队），邻接点无，队列为GCD
• 访问G点（出队），邻接点为D、H，入队后队列为CDH（D重复不再入队）
• 访问C点（出队），邻接点无，队列为DH
• 访问D点（出队），邻接点为E，入队后队列为HE
• 访问H点（出队），邻接点无，队列为E
• 访问E点（出队），邻接点无，队列为空
• 循环结束

bfs遍历序列为：ABFGCDHE

可以发现，整个遍历过程是分层进行的，先遍历距离为1的所有顶点，再距离为2的所有顶点，···，直到访问完毕。在距离为x的层未访问完成之前，不会访问距离为x+1的层。

层次结构如下图：

3、算法实现

伪代码：

bfs()
  起点入队
  while (队列不空)
    访问队首元素、出队
    for 队首元素相邻结点
      入队并标记

使用stl的queue容器：

void bfs(int v0) {
  queue<int> q;
  vis[v0] = true;
  q.push(v0);
  while(!q.empty()) {
    int tmp = q.front();
    cout<<tmp;
    q.pop();
    for(tmp的所有邻接点i) {
      if(vis[i]) continue;
      vis[i] = true;
      q.push(i);
    }
  }
}

4、bfs求最短路

无权图或等权图，可以用bfs求单源最短路。

原理：bfs遍历是以起点为中心，一层一层往外扩展，显然最先到达的点的层数就是最短距离。

算法实现：

• 定义d[N]数组，表示起点到每个点的最短距离
• 初始值d[sx] = 0
• 在bfs遍历到y时，d[y] = d[x]+1

void bfs() {
  queue<int> q;
  vis[sx] = true;
  q.push(sx);
  while(!q.empty()) {
    int x = q.front();
    q.pop();
    for(int i=0; i<g[x].size(); i++) {
      int y = g[x][i];
      if(vis[y]) continue;
      d[y] = d[x]+1;  //最短距离
      vis[y] = true;
      q.push(y);
    }
  }
}

5、最短路径

如果要求出路径（一般指路径上的节点集合），可在求遍历求最短距离过程中存储前趋点。

for(int i=0; i<g[x].size(); i++) {
      int y = g[x][i];
      if(vis[y]) continue;
      d[y] = d[x]+1;  
      pre[y] = x;  //前趋点, 初始点pre[sx] = sx
      vis[y] = true;
      q.push(y);
    }

理解：

• pre[y] = x指y是从x过来的，也即最短路径上x是y的父亲
• 参照树的父亲存储法，就会发现pre[N]会构成一棵以起点sx为根的树，即最短路树
• 最短路树上，从起点sx到任意一个点y的路径，就是原图中sx到y的最短路径

由pre[N]输出到某个点y的最短路径，可通过栈或递归函数，例如：

void show(int x) {
  if(x != pre[x])
    show(pre[x]);
  cout<<x<<" ";
}

6、迷宫最短路

迷宫一般是二维数组来表示，因此一个点(x1,y1)的可能连接点最多有周围的8个位置，即左上、上、右上、右、右下、下、左下、左，可通过偏移坐标得到，例如左上的偏移坐标是(-1, -1)。

一般可通过偏移数组，用循环来遍历某个点的八个连接点：

int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1,   1,  1,  0, -1, -1};
for(int i=0; i<8; i++) {
  int x2 = x + dx[i];
  int y2 = y + dy[i];
}

其它：

• 有时题目会要求只走上下左右四个方向
• 有时题目会规定其它走法，例如马步，如偏移(2, 1)
• 有时题目会增加障碍物，某些坐标不可走

有了移动方式之后，就可将迷宫看成一个图，每个点可移动到周围的点，因此可通过bfs来求最短距离。

同时，求最短路径也可用前趋数组来存储，只是数组元素需要用一个结构体来表示坐标。

pre[x2][y2] = (Node) {x, y};

扩展理解－dfs与bfs`

1、广搜的理解

你的眼镜掉了，你趴在地板上找，先摸一圈最近的地方，如果没有，再往远一点摸过去.....

2、空间复杂度

dfs占用的是栈的空间（因为递归），每次遍历需要占用等于路径深度的栈空间。

bfs占用的是队列的空间，每次遍历需要占用等于邻接点数目的队列空间。

从空间复杂度来说：

• 链状图：bfs好于dfs，用bfs的空间占用只有1个，而dfs就要占用链深度大小的空间。
• 星状图：dfs好于bfs，用bfs的空间占用邻接点数目大小，而dfs只有一层深度。

3、应用场景

bfs适合用于找一条最短路径（无权图），既一个最优解，也可以理解成一种贪心策略。

dfs使用找所有（最短）路径，既遍历所有的解空间，进行判定，也可以理解成枚举策略。