BFS

int bfs(const vector<vector<int>>& g, int st, int ed)
{
    vector<int> d(n, -1);
    vector<int> pre(n, -1); // 若需要保存路径
    queue<int> q;
    d[st] = 0;
    q.push(st);
    int ans = 0;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(int son: g[cur])
        {
            if(d[son] != -1) continue;
            d[son] = d[cur] + 1;
            pre[son] = cur;
            if(son == ed)
            {
                ans = 1;
                break;
            }
            q.push(son);
        }
    }
    if(!ans) return ans;
    // 输出最短路
    stack<int> sta;
    int u = ed;
    while(u != -1)
    {
        sta.push(u);
        u = pre[u];
    }
    while(!sta.empty())
    {
        sta.pop();
    }
    return -1;
}

双向 BFS 求 st 到 ed 的最短路径

// 双向 BFS
int bibfs(const vector<vector<int>>& g, int st, int ed)
{
    vector<int> d(n, 0); // 0 代表未访问, +-号代表颜色(起点色，终点色)
    queue<int> q;
    d[st] = 1;
    d[ed] = -1;
    q.push(st);
    q.push(ed);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(int son: g[cur])
        {
            if(d[son] == 0) // 未访问过
            {
                d[son] = (d[cur] > 0 ? d[cur] + 1 : d[cur] - 1);
                q.push(son);
            }
            else
            {
                if((d[cur] ^ d[son]) < 0) // 异号，颜色不同
                    return abs(d[cur]) + abs(d[son]);
            }
        }
    }
    return -1;
}

$2 经常配合使用的方法

2.1 无权图最短路径(BFS 基本模型)

1311. 获取你好友已观看的视频

建图
边权为 1

909. 蛇梯棋

建图
边权为 1
定义队列中的状态结构体

2039. 网络空闲的时刻

建图
边权为 1

2.2 复杂状态表示和状态转移

定义状态结构体，以及用合适的数据结构维护状态

365. 水壶问题

力扣365-水壶问题,BFS,裴蜀定理

317. 离建筑物最近的距离

边权为 1
多源BFS
染色

队列中的 Point

struct Point
{
    int i, j;
    int c; // 颜色
    int d; // 与 c 的源的距离
    Point(int i, int j, int c, int d):i(i),j(j),c(c),d(d){}
};

各个位置的状态

struct State
{
    vector<int> d; // d[c] := 到颜色为 c 的建筑物的距离, -1 表示未触达
    int cnt; // 已经触达的建筑数目
    int sum; // 已经触达的建筑的距离和
    State(int cnt=0)
    {
        sum = 0;
        this -> cnt = 0;
        d.assign(cnt, -1);
    }
};

1197. 进击的骑士

队列中的 State

struct State
{
    int x;
    int y;
    int d;
    State(int x, int y, int d):x(x),y(y),d(d){}
};

维护已经访问过的状态
- unordered_set<State>
- vector<vector<bool>>
力扣1197-进击的骑士

1210. 穿过迷宫的最少移动次数

队列中的 State

struct State
{
    int x, y; // 蛇尾位置
    int ori; // 蛇的方向，0: 横, 1: 竖
    int d;
    State(int x, int y, bool ori, int d):x(x),y(y),ori(ori),d(d){}
};

1293. 网格中的最短路径

边权为 1

队列中的 State

struct State
{
    int i, j;
    int k; // 剩余的删除次数
    int d;
    State(int i, int j, int k, int d):i(i),j(j),k(k),d(d){}
};

visited 需要对 i, j, k 均做记录

2.3 状态压缩

864. 获取所有钥匙的最短路径

【搜索难题】力扣864-获取所有钥匙的最短路径

1284. 转化为全零矩阵的最少反转次数

将01矩阵(棋盘状态)压缩为整数

队列中的状态

struct State
{
    int s; // 状态压缩后的棋盘状态
    int d;
    State(int s, int d):s(s),d(d){}
};

哈希集合维护已经访问过的棋盘状态

2.4 双端队列(01边权模型)

deque 相关设计模式：工作秘取模式

在生产者-消费者模型中，有一个队列统一管理任务，多个 Worker 从一个队列中取任务执行、执行完再去队列取任务。

在工作密取模式中，每个 Worker 自带一个 deque，里面有该 Worder 待执行的任务，如果一个 Worker 的 deque 里的任务执行完了，它会找到其它未完成人物的 Worker，然后秘密地将该 Worker 的 deque 的尾部弹出，加入到自己的 deque 中。这是用到双端队列的一种设计模式。