BFS是否仅能搜索最短路径？结合LeetCode题探讨

对应题目为二进制矩阵中的最短路径，题目规则如下：

• 给定元素为0/1的n×n二进制矩阵grid，返回从左上角单元格(0,0)到右下角单元格(n-1,n-1)的最短路径
• 路径需满足两个要求：① 路径访问的所有单元格值均为0；② 路径中所有相邻单元格为8方向连通（即单元格互不重复，且共享边或夹角）

该问题的常规解法是基于队列实现BFS，参考代码如下：

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if (grid[0][0] == 1) return -1;
    int res = 0, n = grid.size(), m = grid[0].size();
    vector<vector<int>> visited(n, vector<int>(m, 0));
    visited[0][0] = 1;
    queue<vector<int>> q;
    q.push({ 0, 0 });
    vector<vector<int>> dirs{ {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
    while (!q.empty()) {
        ++res;
        for (int i = q.size(); i > 0; --i) {
            auto t = q.front(); q.pop();
            if (t[0] == n - 1 && t[1] == n - 1) return res;
            for (auto dir : dirs) {
                int x = t[0] + dir[0], y = t[1] + dir[1];
                if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 1 || visited[x][y]) continue;
                visited[x][y] = 1; 
                q.push({ x, y });
            }
        }
    }
    return -1;
}

BFS并非仅能求解最短路径问题。
大家通常把BFS和无权图最短路径绑定，本质是因为最短路径场景下用了「全局访问标记+层序遍历」的优化：第一次遍历到某个节点时，对应的路径长度一定是所有可达路径里最短的，因此标记节点已访问、避免后续重复入队，碰到终点时可以直接返回结果，时间复杂度能控制在O(nm)级别，效率很高。但全局访问标记是针对最短路径场景的优化手段，不是BFS算法本身的强制约束。

如果目标是查找所有可达路径，BFS完全可以胜任，你写的fun2就是可行的实现：

vector<vector<vector<int>>> fun2(vector<vector<int>> grid, int x, int y)
{
    vector<vector<vector<int>>> res;
    if (grid[x][y] == 1) return res;
    int n = grid.size(), m = grid[0].size();
    queue<vector<vector<int>>> q;
    q.push({ { x, y } });
    vector<vector<int>> dirs{ {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
    while (!q.empty()) {
        for (int i = q.size(); i > 0; --i) {
            auto t = q.front(); q.pop();
            unordered_set<string> st;
            for (auto &it : t) st.insert(to_string(it[0]) + ',' + to_string(it[1]));
            int xx = t.back()[0], yy = t.back()[1];
            if (grid[xx][yy] == 2) res.push_back(t);
            for (auto dir : dirs) {
                int x = xx + dir[0], y = yy + dir[1];
                if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 1 || st.count(to_string(x) + ',' + to_string(y))) continue;
                auto tem = t;
                tem.push_back({ x, y });
                q.push(tem);
            }
        }
    }
    return res;
}

这个实现放弃了全局visited数组，转而给队列中存储的每一条独立路径单独维护已访问节点集合（代码中用unordered_set存储当前路径的所有坐标，避免单条路径内出现重复节点），每次扩展路径时只要新节点满足边界、值的要求，且不在当前路径的已访问集合中，就生成新的完整路径入队，队列为空时就能拿到所有符合要求的可达路径。

两种BFS实现的核心差异只是适用场景不同：

• 求最短路径的BFS：靠全局标记剪枝，每个节点仅入队一次，效率高，但无法记录所有路径
• 求所有路径的BFS：不做全局剪枝，节点会在不同路径中重复入队，时间、空间复杂度随矩阵规模指数级上升，和递归DFS枚举所有路径的复杂度一致，仅遍历顺序为按路径长度层序推进而已。

注意你写的fun2中判断终点的条件是grid[xx][yy] == 2，属于自定义终点标记，如果要适配原题的右下角终点需求，把判断条件改为xx == n-1 && yy == m-1即可，整体逻辑没有问题。

内容的提问来源于stack exchange，提问作者user6703592