背景

宽度优先搜索BFS侧重搜索的广度，类似于石头扔到水中，泛起一圈一圈的涟漪。 从近到远，一圈一圈扩散的效果。

模板

1. 源点进队。
2. 队列不为空，拿出队首元素。
3. 对队首元素进行扩展，未被访问过的结点进队。

图遍历模板

给定一个n个结点，m条边的图。判断图是否连通

const int N = 100005;
queue<int> q;
bool v[N];
vector<int> adj[N]; // adj[i]: i号结点的邻接表

void bfs(s) {
    q.push(s);   // 源点进队
    v[s] = true;
    
    while (!q.empty()) {  // 当队列不为空时
        int cur = q.front(); q.pop(); // 拿出队首元素
        for (auto nxt : adj[cur]) {   // 对队首元素扩展
            if (!v[nxt]) {
                q.push(nxt);
                v[nxt] = true;
            }
        }
    }
}

结合这份模板代码，我们可以实现：

1. 判断图的连通性。看v是否全被修改为true。
2. 求连通分量个数。从每个未被访问过的点，搜索进去，修改v标记。能从几个点进去，连通分量就是几。

无权图最短路

BFS从近到远扩展，对于无权图来说，能够保证队列中每个点的距离单调递增。每个点第一次被访问到时，就是最短路。 我们看看核心代码变化：

对于普通图

const int N = 100005;
queue<int> q;
int dist[N];        // v数组修改为dist数组，求距离
vector<int> adj[N];

void bfs(s) {
    q.push(s);
    dist[s] = 0;    // 源点距离为0
    
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (auto nxt : adj[cur]) {
            if (dist[nxt] == -1) {         // 用dist==-1判断该点没有被访问过
                q.push(nxt);
                dist[nxt] = dist[cur] + 1; // 距离更新成当前点+1即可
            }
        }
    }
}

int main(void) {
    memset(dist, -1, sizeof dist); // 将距离初始化为-1
}

对于棋盘图

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

我们可以定义这两两个数组，表示出四个可扩展的方向（上下左右）。 具体可以往哪些方向扩展，看题目说明。 比如题目说来了匹马，那么它有八个方向可以跳。 注意扩展时，不要超出棋盘边界就好。