#c

BFS与队列专题

从基础到竞赛的广度优先搜索技巧

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. 队列基础知识

1.1 队列的定义和特性

  • 队列(Queue)的定义：队列是一种特殊的线性表，只允许在表的一端进行插入，在另一端进行删除
    • 遵循先进先出(FIFO: First In First Out)原则
    • 插入操作称为入队(Enqueue)，删除操作称为出队(Dequeue)
  • 队列的特性：
    • 先进先出：最先入队的元素最先出队
    • 队头(Front)：允许删除的一端
    • 队尾(Rear)：允许插入的一端
    • 空队列：不包含任何元素的队列
    • 队列长度：队列中元素的个数
  • 队列的应用场景：
    • 广度优先搜索(BFS)
    • 操作系统中的任务调度
    • 打印机的打印任务队列
返回目录 信息学 BFS与队列专题 魅客科创中心

1.2 队列的基本操作

C++中的队列操作：

#include <queue>
using namespace std;

queue<int> q;  // 创建一个整型队列
q.push(10);    // 入队
q.push(20);
q.push(30);
cout << q.front(); // 输出队头元素: 10
q.pop();       // 出队
cout << q.front(); // 输出新的队头: 20
cout << q.size();  // 输出队列大小: 2
cout << q.empty(); // 判断是否为空: 0(false)

队列操作的时间复杂度：

  • 入队(push): ，出队(pop):
  • 获取队头元素(front):
  • 判断队列是否为空(empty):
  • 获取队列大小(size):

注意事项：

  • 在使用队列前，应确保队列已正确初始化
  • 从空队列中获取元素或出队会导致错误
  • 在C++中，pop()操作不会返回队头元素，需要先使用front()获取，再调用pop()
  • 队列没有迭代器，不能直接遍历队列中的所有元素
返回目录 信息学 BFS与队列专题 魅客科创中心

1.3 队列的实现方式

1. 数组实现队列：

class ArrayQueue {
private:
    int* arr;      // 存储队列元素的数组
    int capacity;  // 队列容量
    int front;     // 队头指针
    int rear;      // 队尾指针
    int size;      // 当前队列大小
    
public:
    ArrayQueue(int cap) {
        capacity = cap;
        arr = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == capacity;
    }
    
    void enqueue(int item) {
        if (isFull()) return;
        rear = (rear + 1) % capacity;
        arr[rear] = item;
        size++;
    }
    
    int dequeue() {
        if (isEmpty()) return -1;
        int item = arr[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }
    
    int getFront() {
        if (isEmpty()) return -1;
        return arr[front];
    }
};

2. 链表实现队列：

struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

class LinkedListQueue {
private:
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
    int size;     // 队列大小
    
public:
    LinkedListQueue() {
        front = rear = nullptr;
        size = 0;
    }
    
    bool isEmpty() {
        return front == nullptr;
    }
    
    void enqueue(int item) {
        Node* temp = new Node(item);
        if (isEmpty()) {
            front = rear = temp;
        } else {
            rear->next = temp;
            rear = temp;
        }
        size++;
    }
    
    int dequeue() {
        if (isEmpty()) return -1;
        Node* temp = front;
        int item = temp->data;
        front = front->next;
        if (front == nullptr) rear = nullptr;
        delete temp;
        size--;
        return item;
    }
    
    int getFront() {
        if (isEmpty()) return -1;
        return front->data;
    }
};
返回目录 信息学 BFS与队列专题 魅客科创中心

1.4 循环队列介绍

  • 循环队列的概念：

    • 循环队列是一种头尾相连的队列实现方式
    • 解决了普通数组实现队列时的"假溢出"问题
    • 通过取模运算实现数组空间的循环利用

  • 循环队列的实现：

class CircularQueue {
private:
    int* arr;
    int capacity;
    int front;
    int rear;
    int size;
    
public:
    CircularQueue(int cap) {
        capacity = cap;
        arr = new int[capacity];
        front = rear = -1;
        size = 0;
    }
    
    bool isEmpty() {
        return front == -1;
    }
    
    bool isFull() {
        return (rear + 1) % capacity == front;
    }
    
    void enqueue(int item) {
        if (isFull()) return;
        
        if (isEmpty())
            front = 0;
            
        rear = (rear + 1) % capacity;
        arr[rear] = item;
        size++;
    }
    
    int dequeue() {
        if (isEmpty()) return -1;
        
        int item = arr[front];
        
        if (front == rear) {
            // 队列中只有一个元素
            front = rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        
        size--;
        return item;
    }
    
    int getFront() {
        if (isEmpty()) return -1;
        return arr[front];
    }
};
  • 循环队列的优势：
    • 有效利用数组空间，避免"假溢出"
    • 入队和出队操作的时间复杂度均为O(1)
    • 适合需要频繁入队和出队的场景
返回目录 信息学 BFS与队列专题 魅客科创中心

2. BFS算法原理

2.1 BFS的基本概念

  • 广度优先搜索(Breadth-First Search, BFS)的定义：
    • BFS是一种图形搜索算法，从起始节点开始，逐层向外扩展
    • 先访问起始节点的所有邻居，然后再访问这些邻居的邻居
    • 使用队列来实现"先进先出"的访问顺序
  • BFS的核心思想：
    • 从起点出发，首先访问起点
    • 然后依次访问起点的所有邻接点
    • 再按照访问邻接点的顺序，依次访问邻接点的邻接点
    • 直到所有可达节点都被访问过
  • BFS的特点：
    • 按照"层次"访问节点
    • 保证找到的路径是最短路径（在无权图或权值相等的图中）
    • 空间复杂度较高，需要存储每一层的所有节点
    • 适合寻找最短路径、最少步数等问题
  • BFS的应用场景：
    • 无权图的最短路径
    • 层次遍历
    • 连通分量分析
    • 状态空间搜索
    • 网络爬虫
返回目录 信息学 BFS与队列专题 魅客科创中心

2.2 BFS的工作流程

BFS算法步骤：

  1. 创建一个队列，将起始节点放入队列中
  2. 标记起始节点为已访问
  3. 当队列不为空时，执行以下操作：
    • 取出队列头部节点
    • 处理当前节点
    • 将当前节点的所有未访问过的邻居加入队列
    • 标记这些邻居为已访问
  4. 重复步骤3，直到队列为空
返回目录 信息学 BFS与队列专题 魅客科创中心

2.2.1 BFS的工作流程

BFS图示：

      A
     / \
    B   C
   / \   \
  D   E   F

BFS遍历顺序：A → B → C → D → E → F

BFS执行过程示例：

  1. 初始状态：
    • 队列: [A]
    • 已访问: {A}
  1. 出队A，访问A的邻居B和C：
    • 队列: [B, C]
    • 已访问: {A, B, C}
  2. 出队B，访问B的邻居D和E：
    • 队列: [C, D, E]
    • 已访问: {A, B, C, D, E}
  3. 出队C，访问C的邻居F：
    • 队列: [D, E, F]
    • 已访问: {A, B, C, D, E, F}
  4. 依次出队D、E、F，它们没有未访问的邻居：
    • 队列: []
    • 已访问: {A, B, C, D, E, F}
  5. 队列为空，BFS结束
返回目录 信息学 BFS与队列专题 魅客科创中心

2.3 BFS vs DFS

BFS特点：

  • 使用队列实现
  • 逐层遍历
  • 保证找到最短路径
  • 空间复杂度较高
  • 适合寻找最短路径、最少步数

BFS适用场景：

  • 最短路径问题
  • 层次遍历
  • 连通性问题
  • 状态空间搜索（状态较少）
  • 网格图中的距离计算

DFS特点：

  • 使用栈或递归实现
  • 尽可能深地搜索
  • 不保证找到最短路径
  • 空间复杂度较低（递归调用栈）
  • 适合寻找所有路径、判断连通性

DFS适用场景：

  • 查找所有可能的路径
  • 拓扑排序
  • 连通性判断
  • 状态空间搜索（状态较多）
  • 回溯算法问题
返回目录 信息学 BFS与队列专题 魅客科创中心

2.3.1 BFS vs DFS

BFS vs DFS比较：

特性 BFS DFS
实现方式 队列 栈/递归
搜索策略 逐层扩展 尽可能深入
空间复杂度 O(b^d) O(d)
最短路径 保证 不保证
完整性 完备 不完备（可能陷入无限深度）
适用场景 最短路径、层次分析 所有路径、回溯问题
返回目录 信息学 BFS与队列专题 魅客科创中心

2.4 时间复杂度分析

  • BFS的时间复杂度：

    • 基本时间复杂度：
      • V是顶点数
      • E是边数
    • 在邻接矩阵表示的图中：²
    • 在邻接表表示的图中：

  • 空间复杂度分析：

    • 队列空间：
      • 是平均分支因子（每个节点的平均邻居数）
      • 是从起点到目标的最短距离
    • 访问标记数组：
    • 总空间复杂度：
  • 影响BFS性能的因素：

    1. 图的表示方式

      • 邻接矩阵：适合稠密图，空间²
      • 邻接表：适合稀疏图，空间

    2. 图的结构特征

      • 分支因子：影响队列大小
      • 图的连通性：影响访问节点数
      • 图的直径：影响搜索深度

    3. 优化方法

      • 双向BFS：从起点和终点同时搜索
      • 启发式搜索：使用估价函数指导搜索
      • 剪枝：减少无效搜索
      • 记忆化：存储中间结果
返回目录 信息学 BFS与队列专题 魅客科创中心

2.4.1常见应用场景的复杂度

  1. 迷宫最短路

    • 时间：，和是迷宫的长和宽
    • 空间：

  2. 二叉树层序遍历

    • 时间：，是节点数
    • 空间：，是树的最大宽度

  3. 无权图最短路

    • 时间：
    • 空间：
返回目录 信息学 BFS与队列专题 魅客科创中心

3. BFS实现详解

3.1 基本框架代码

BFS基本框架：

// 图的BFS模板
void bfs(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;
    
    // 起点入队并标记
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        // 处理当前节点
        process(curr);
        
        // 遍历邻居
        for (int next : graph[curr]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

带层次信息的BFS：

// 记录层次的BFS模板
void bfsWithLevel(vector<vector<int>>& graph, 
                  int start) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> level(n, -1);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    level[start] = 0;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        for (int next : graph[curr]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
                level[next] = level[curr] + 1;
            }
        }
    }
}
返回目录 信息学 BFS与队列专题 魅客科创中心

3.1 使用示例

// 创建图（邻接表表示）
vector<vector<int>> graph = {
    {1, 2},     // 0号顶点的邻居
    {0, 3, 4},  // 1号顶点的邻居
    {0, 5},     // 2号顶点的邻居
    {1},        // 3号顶点的邻居
    {1},        // 4号顶点的邻居
    {2}         // 5号顶点的邻居
};

// 从0号顶点开始BFS
bfs(graph, 0);
返回目录 信息学 BFS与队列专题 魅客科创中心

3.2 状态记录和访问标记

  • 访问标记的重要性：

    • 防止重复访问节点，避免死循环
    • 减少不必要的计算，提高效率
    • 记录已经探索过的状态

  • 常见的访问标记方式：

    1. 布尔数组：
      vector<bool> visited(n, false);
// 标记访问
visited[node] = true;
// 检查是否访问过
if (!visited[neighbor]) { /* ... */ }

  1. 集合：

    set<int> visited;
// 标记访问
visited.insert(node);
// 检查是否访问过
if (visited.find(neighbor) == visited.end()) { /* ... */ }

  2. 哈希表：

    unordered_set<int> visited;
// 标记访问
visited.insert(node);
// 检查是否访问过
if (!visited.count(neighbor)) { /* ... */ }
返回目录 信息学 BFS与队列专题 魅客科创中心

3.2.1 多维状态的访问标记

二维网格：

vector<vector<bool>> visited(rows, vector<bool>(cols, false));

// 标记访问
visited[x][y] = true;
// 检查是否访问过
if (!visited[nx][ny]) { /* ... */ }
  • 状态记录的技巧：
    • 使用位运算表示状态集合
    • 使用字符串表示复杂状态
    • 使用自定义结构体和哈希函数
    • 使用状态压缩技术减少内存使用
返回目录 信息学 BFS与队列专题 魅客科创中心

3.3 路径记录技巧

记录前驱节点：

vector<int> bfsWithPath(vector<vector<int>>& graph, 
                        int start, int end) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> parent(n, -1);  // 记录前驱节点
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        if (curr == end) break;  // 找到终点
        
        for (int next : graph[curr]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
                parent[next] = curr;  // 记录前驱
            }
        }
    }
    
    // 重建路径
    vector<int> path;
    if (parent[end] == -1) return path;  // 无路径
    
    for (int at = end; at != -1; at = parent[at]) {
        path.push_back(at);
    }
    reverse(path.begin(), path.end());
    return path;
}

记录完整状态路径：

struct State {
    int x, y;
    vector<pair<int, int>> path;  // 记录路径
    
    State(int _x, int _y) : x(_x), y(_y) {
        path.push_back({_x, _y});
    }
    
    State(int _x, int _y, const vector<pair<int, int>>& _path) 
        : x(_x), y(_y), path(_path) {
        path.push_back({_x, _y});
    }
};

vector<pair<int, int>> findPath(vector<vector<int>>& grid, 
                               pair<int, int> start, 
                               pair<int, int> end) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    queue<State> q;
    
    q.push(State(start.first, start.second));
    visited[start.first][start.second] = true;
    
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    
    while (!q.empty()) {
        State curr = q.front();
        q.pop();
        
        if (curr.x == end.first && curr.y == end.second) {
            return curr.path;  // 返回完整路径
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = curr.x + dx[i];
            int ny = curr.y + dy[i];
            
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && 
                grid[nx][ny] == 0 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push(State(nx, ny, curr.path));
            }
        }
    }
    
    return {};  // 无路径
}
返回目录 信息学 BFS与队列专题 魅客科创中心

3.4 常见优化方法

  • 双向BFS：
    • 同时从起点和终点开始搜索
    • 当两个搜索相遇时，找到最短路径
    • 可以显著减少搜索空间
int bidirectionalBFS(vector<vector<int>>& graph, int start, int end) {
    int n = graph.size();
    if (start == end) return 0;
    
    // 从起点和终点开始的两个队列
    queue<int> q1, q2;
    vector<int> dist1(n, -1), dist2(n, -1);
    
    q1.push(start);
    q2.push(end);
    dist1[start] = 0;
    dist2[end] = 0;
    
    while (!q1.empty() && !q2.empty()) {
        // 从较小的队列扩展
        if (q1.size() > q2.size()) {
            swap(q1, q2);
            swap(dist1, dist2);
        }
        
        int curr = q1.front();
        q1.pop();
        
        for (int next : graph[curr]) {
            if (dist1[next] == -1) {
                dist1[next] = dist1[curr] + 1;
                q1.push(next);
                
                // 检查是否与另一方向的搜索相遇
                if (dist2[next] != -1) {
                    return dist1[next] + dist2[next];
                }
            }
        }
    }
    
    return -1;  // 无路径
}
返回目录 信息学 BFS与队列专题 魅客科创中心

3.4 常见优化方法

  • A*搜索：
    • 使用启发式函数指导搜索方向
    • 优先扩展更有希望到达目标的节点
    • 常用于路径规划和游戏AI
struct Node {
    int id;
    int cost;      // 从起点到当前的实际代价
    int heuristic; // 从当前到终点的估计代价
    
    bool operator>(const Node& other) const {
        return cost + heuristic > other.cost + other.heuristic;
    }
};

int aStarSearch(vector<vector<pair<int, int>>>& graph, 
               int start, int end, 
               function<int(int, int)> h) {
    int n = graph.size();
    vector<int> cost(n, INT_MAX);
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    
    pq.push({start, 0, h(start, end)});
    cost[start] = 0;
    
    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();
        
        if (curr.id == end) return curr.cost;
        if (curr.cost > cost[curr.id]) continue;
        
        for (auto& [next, weight] : graph[curr.id]) {
            int newCost = curr.cost + weight;
            if (newCost < cost[next]) {
                cost[next] = newCost;
                pq.push({next, newCost, h(next, end)});
            }
        }
    }
    
    return -1;  // 无路径
}
返回目录 信息学 BFS与队列专题 魅客科创中心

3.4 常见优化方法

  • 剪枝技术：

    • 提前终止不可能的搜索路径
    • 使用问题特性减少搜索空间
    • 例如：在迷宫问题中，如果当前路径长度已经超过已知最短路径，可以直接剪枝

  • 记忆化搜索：

    • 存储已经计算过的状态结果
    • 避免重复计算
    • 特别适用于有重叠子问题的搜索
返回目录 信息学 BFS与队列专题 魅客科创中心

4. 典型应用场景

4.1 最短路径问题

无权图最短路径：

  • BFS可以找到无权图中从起点到其他所有点的最短路径
  • 第一次访问到的路径就是最短路径
// 计算从起点到所有点的最短距离
vector<int> bfsShortestPath(vector<vector<int>>& graph, 
                           int start) {
    int n = graph.size();
    vector<int> distance(n, -1);  // -1表示不可达
    queue<int> q;
    
    q.push(start);
    distance[start] = 0;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        for (int next : graph[curr]) {
            if (distance[next] == -1) {
                distance[next] = distance[curr] + 1;
                q.push(next);
            }
        }
    }
    
    return distance;
}

迷宫最短路径：

  • 在网格图中寻找从起点到终点的最短路径
  • 常用于游戏、机器人路径规划等场景
// 迷宫最短路径
int shortestPathInMaze(vector<vector<int>>& maze, 
                       pair<int, int> start, 
                       pair<int, int> end) {
    int rows = maze.size(), cols = maze[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    queue<pair<int, int>> q;
    
    q.push(start);
    dist[start.first][start.second] = 0;
    
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        if (x == end.first && y == end.second) {
            return dist[x][y];
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && 
                maze[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1;  // 无法到达终点
}
返回目录 信息学 BFS与队列专题 魅客科创中心

4.2 层次遍历

二叉树层序遍历：

  • 按照从上到下、从左到右的顺序访问树的节点
  • 是树结构中最常见的BFS应用
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> currentLevel;
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            
            currentLevel.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        result.push_back(currentLevel);
    }
    
    return result;
}

图的层次遍历：

  • 按照与起点的距离对节点进行分层
  • 可用于分析网络结构、社交关系等
// 图的层次遍历
vector<vector<int>> levelOrderTraversal(
    vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<vector<int>> levels;
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> currentLevel;
        
        for (int i = 0; i < levelSize; i++) {
            int curr = q.front();
            q.pop();
            
            currentLevel.push_back(curr);
            
            for (int next : graph[curr]) {
                if (!visited[next]) {
                    q.push(next);
                    visited[next] = true;
                }
            }
        }
        
        levels.push_back(currentLevel);
    }
    
    return levels;
}

应用示例：

  • 网页爬虫（按层次抓取链接）
  • 社交网络分析（朋友圈层次）
  • 依赖关系分析（构建依赖图）
返回目录 信息学 BFS与队列专题 魅客科创中心

4.3 连通性问题

  • 连通分量计算：

    • 找出图中所有相互连通的节点集合
    • 在无向图中，连通分量是最大的连通子图
    // 计算无向图的连通分量
int countConnectedComponents(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            count++;
            
            // BFS遍历连通分量
            queue<int> q;
            q.push(i);
            visited[i] = true;
            
            while (!q.empty()) {
                int curr = q.front();
                q.pop();
                
                for (int next : graph[curr]) {
                    if (!visited[next]) {
                        q.push(next);
                        visited[next] = true;
                    }
                }
            }
        }
    }
    
    return count;
}

  • 判断二分图：

    • 二分图是一种可以将顶点分成两个不相交集合的图，使得每条边的两个顶点分别属于这两个集合
    • 可以使用BFS进行染色法判断
    // 判断是否为二分图
bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n, -1);  // -1表示未染色，0和1表示两种颜色
    
    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;  // 已经染色的节点跳过
        
        queue<int> q;
        q.push(start);
        color[start] = 0;  // 初始颜色
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            
            for (int next : graph[curr]) {
                if (color[next] == -1) {
                    // 未染色，染成相反的颜色
                    color[next] = 1 - color[curr];
                    q.push(next);
                } else if (color[next] == color[curr]) {
                    // 相邻节点颜色相同，不是二分图
                    return false;
                }
            }
        }
    }
    
    return true;
}

  • 寻找割点和桥：

    • 割点：删除后会增加图的连通分量数的顶点
    • 桥：删除后会增加图的连通分量数的边
    • 通常使用DFS实现，但也可以用BFS配合其他算法

  • 应用场景：

    • 社交网络中的社区发现
    • 网络拓扑分析
    • 图像分割中的连通区域标记
    • 电路设计中的连通性检查
返回目录 信息学 BFS与队列专题 魅客科创中心

4.4 状态空间搜索

状态空间搜索概念：

  • 将问题抽象为状态和状态转移
  • 使用BFS在状态空间中寻找从初始状态到目标状态的最短路径
  • 适用于组合优化、谜题求解等问题

八数码问题：

struct PuzzleState {
    vector<vector<int>> board;
    int zeroRow, zeroCol;  // 空格位置
    int steps;             // 从初始状态到当前状态的步数
    string path;           // 记录移动路径
    
    // 生成状态的唯一标识
    string getKey() const {
        string key;
        for (const auto& row : board) {
            for (int val : row) {
                key += to_string(val) + ",";
            }
        }
        return key;
    }
};

int solvePuzzle(vector<vector<int>> initial, 
               vector<vector<int>> target) {
    // 方向数组：上、右、下、左
    int dr[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    string dirs = "URDL";  // 对应方向的字符表示
    
    PuzzleState start;
    start.board = initial;
    start.steps = 0;
    start.path = "";
    
    // 找到初始状态中的空格位置
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (initial[i][j] == 0) {
                start.zeroRow = i;
                start.zeroCol = j;
                break;
            }
        }
    }
    
    queue<PuzzleState> q;
    unordered_set<string> visited;
    
    q.push(start);
    visited.insert(start.getKey());
    
    while (!q.empty()) {
        PuzzleState curr = q.front();
        q.pop();
        
        // 检查是否达到目标状态
        if (curr.board == target) {
            return curr.steps;
        }
        
        // 尝试四个方向的移动
        for (int i = 0; i < 4; i++) {
            int newRow = curr.zeroRow + dr[i];
            int newCol = curr.zeroCol + dy[i];
            
            // 检查新位置是否有效
            if (newRow >= 0 && newRow < 3 && 
                newCol >= 0 && newCol < 3) {
                
                // 创建新状态
                PuzzleState next = curr;
                
                // 交换空格和相邻数字
                swap(next.board[curr.zeroRow][curr.zeroCol], 
                     next.board[newRow][newCol]);
                next.zeroRow = newRow;
                next.zeroCol = newCol;
                next.steps++;
                next.path += dirs[i];
                
                // 检查是否访问过该状态
                string key = next.getKey();
                if (visited.find(key) == visited.end()) {
                    visited.insert(key);
                    q.push(next);
                }
            }
        }
    }
    
    return -1;  // 无解
}

骑士巡游问题：

// 骑士在棋盘上从起点到终点的最少步数
int knightMinSteps(pair<int, int> start, 
                  pair<int, int> end, 
                  int n) {
    // 骑士的8种移动方式
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<pair<pair<int, int>, int>> q;  // 位置和步数
    
    q.push({start, 0});
    visited[start.first][start.second] = true;
    
    while (!q.empty()) {
        auto [pos, steps] = q.front();
        q.pop();
        
        if (pos == end) return steps;
        
        for (int i = 0; i < 8; i++) {
            int nx = pos.first + dx[i];
            int ny = pos.second + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && 
                !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({{nx, ny}, steps + 1});
            }
        }
    }
    
    return -1;  // 无法到达
}

状态空间搜索的应用：

  1. 谜题求解：

    • 八数码、华容道、魔方等
    • 将谜题状态表示为节点，合法移动表示为边

  2. 游戏AI：

    • 象棋、围棋等游戏中的最佳移动搜索
    • 使用启发式函数优化搜索效率

  3. 路径规划：

    • 机器人运动规划
    • 自动驾驶路径
返回目录 信息学 BFS与队列专题 魅客科创中心

5. 经典问题解析

5.1 迷宫问题

问题描述：

  • 在一个N×M的二维网格中，0表示可通行的格子，1表示障碍物
  • 从起点(sx, sy)出发，找到到达终点(ex, ey)的最短路径
  • 每次只能向上、下、左、右四个方向移动一步

解题思路：

  1. 使用BFS从起点开始搜索
  2. 维护一个距离数组记录从起点到每个格子的最短距离
  3. 使用队列存储待访问的格子
  4. 当访问到终点时，返回对应的距离

代码实现：

int shortestPath(vector<vector<int>>& maze, 
                pair<int, int> start, 
                pair<int, int> end) {
    int rows = maze.size();
    int cols = maze[0].size();
    
    // 方向数组：上、右、下、左
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    
    // 初始化距离数组
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    queue<pair<int, int>> q;
    
    // 起点入队
    q.push(start);
    dist[start.first][start.second] = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        // 到达终点
        if (x == end.first && y == end.second) {
            return dist[x][y];
        }
        
        // 尝试四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 检查是否有效且未访问
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && 
                maze[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1;  // 无法到达终点
}

进阶版本：

  • 记录完整路径
  • 处理多种地形（不同通行代价）
  • 处理多个起点或终点

记录路径的实现：

vector<pair<int, int>> getPath(vector<vector<int>>& maze, 
                              pair<int, int> start, 
                              pair<int, int> end) {
    int rows = maze.size();
    int cols = maze[0].size();
    
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    vector<vector<pair<int, int>>> parent(rows, 
        vector<pair<int, int>>(cols, {-1, -1}));
    
    queue<pair<int, int>> q;
    q.push(start);
    dist[start.first][start.second] = 0;
    
    bool found = false;
    while (!q.empty() && !found) {
        auto [x, y] = q.front();
        q.pop();
        
        if (x == end.first && y == end.second) {
            found = true;
            break;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && 
                maze[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                parent[nx][ny] = {x, y};
                q.push({nx, ny});
            }
        }
    }
    
    // 重建路径
    vector<pair<int, int>> path;
    if (!found) return path;
    
    pair<int, int> curr = end;
    while (curr != start) {
        path.push_back(curr);
        curr = parent[curr.first][curr.second];
    }
    path.push_back(start);
    
    reverse(path.begin(), path.end());
    return path;
}

应用场景：

  • 游戏中的寻路算法
  • 机器人路径规划
  • 迷宫生成与求解
  • 网格地图中的最短路径
返回目录 信息学 BFS与队列专题 魅客科创中心

5.2 单词接龙问题

  • 问题描述：

    • 给定两个单词（beginWord和endWord）和一个字典，找出从beginWord到endWord的最短转换序列
    • 每次转换只能改变一个字母，且转换后的单词必须在字典中
    • 如果不存在这样的转换序列，返回0

  • 示例：

    输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，返回长度5

  • 解题思路：

    1. 将问题建模为图搜索问题，每个单词是图中的一个节点
    2. 如果两个单词只相差一个字母，则它们之间有一条边
    3. 使用BFS寻找从beginWord到endWord的最短路径

  • 代码实现：

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    // 将wordList转换为unordered_set以便快速查找
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    
    // 检查endWord是否在字典中
    if (wordSet.find(endWord) == wordSet.end()) {
        return 0;
    }
    
    // BFS队列
    queue<string> q;
    q.push(beginWord);
    
    // 记录转换次数
    int level = 1;
    
    while (!q.empty()) {
        int size = q.size();
        
        // 处理当前层的所有单词
        for (int i = 0; i < size; i++) {
            string currWord = q.front();
            q.pop();
            
            // 尝试修改currWord的每个位置
            for (int j = 0; j < currWord.length(); j++) {
                char originalChar = currWord[j];
                
                // 尝试替换为a-z的每个字母
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == originalChar) continue;
                    
                    currWord[j] = c;
                    
                    // 如果找到endWord
                    if (currWord == endWord) {
                        return level + 1;
                    }
                    
                    // 如果新单词在字典中
                    if (wordSet.find(currWord) != wordSet.end()) {
                        q.push(currWord);
                        wordSet.erase(currWord);  // 避免重复访问
                    }
                }
                
                // 恢复原始字符
                currWord[j] = originalChar;
            }
        }
        
        level++;
    }
    
    return 0;  // 无法转换到endWord
}

  • 优化方法：

    1. 双向BFS：同时从beginWord和endWord开始搜索，当两个搜索相遇时找到最短路径
    2. 预处理邻居：提前计算每个单词的所有可能邻居，避免在BFS中重复计算
    3. 使用通配符：使用形如"*ot"的通配符模式来快速找到所有相邻单词

  • 相关变种：

    • 输出所有最短转换序列
    • 允许添加或删除字母
    • 限制特定字母的转换规则
返回目录 信息学 BFS与队列专题 魅客科创中心

5.3 拓扑排序

问题描述：

  • 给定一个有向无环图(DAG)，找到所有顶点的线性排序，使得对于图中的每条有向边(u, v)，顶点u在排序中都出现在顶点v之前
  • 拓扑排序常用于表示依赖关系，如任务调度、课程安排等

BFS实现（Kahn算法）：

  1. 计算每个顶点的入度
  2. 将所有入度为0的顶点加入队列
  3. 当队列不为空时：
    • 取出队首顶点，将其加入结果
    • 减少其所有邻居的入度
    • 将新的入度为0的顶点加入队列
  4. 如果结果中的顶点数等于图中的顶点数，则存在拓扑排序；否则，图中存在环

代码实现：

vector<int> topologicalSort(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> inDegree(n, 0);
    
    // 计算入度
    for (int u = 0; u < n; u++) {
        for (int v : graph[u]) {
            inDegree[v]++;
        }
    }
    
    // 将入度为0的顶点加入队列
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        
        // 减少邻居的入度
        for (int v : graph[u]) {
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 检查是否存在环
    if (result.size() != n) {
        return {};  // 存在环，无拓扑排序
    }
    
    return result;
}

应用场景：

  1. 课程安排：

    • 某些课程有先修课程要求
    • 拓扑排序可以确定合理的学习顺序

  2. 任务调度：

    • 项目中的任务之间存在依赖关系
    • 拓扑排序可以确定任务的执行顺序

  3. 构建系统：

    • 软件包之间的依赖关系
    • 确定编译顺序

  4. 数据处理流水线：

    • 数据处理步骤之间的依赖关系
    • 确定处理顺序

课程表问题示例：

bool canFinish(int numCourses, 
              vector<vector<int>>& prerequisites) {
    // 构建图（邻接表）
    vector<vector<int>> graph(numCourses);
    vector<int> inDegree(numCourses, 0);
    
    for (auto& pre : prerequisites) {
        int course = pre[0];
        int prereq = pre[1];
        graph[prereq].push_back(course);
        inDegree[course]++;
    }
    
    // 拓扑排序
    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    int count = 0;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        count++;
        
        for (int next : graph[curr]) {
            if (--inDegree[next] == 0) {
                q.push(next);
            }
        }
    }
    
    return count == numCourses;
}

注意事项：

  • 拓扑排序的结果可能不唯一
  • 只有有向无环图(DAG)才有拓扑排序
  • 可以使用BFS或DFS实现拓扑排序
  • BFS实现更容易检测环的存在
返回目录 信息学 BFS与队列专题 魅客科创中心

6. 练习题推荐

6.1 入门级练习题

  • HDU 1241. Oil Deposits

    • 题目描述：给定一个二维网格，'@'表示油田，'*'表示空地。如果两个油田相邻（包括对角线方向），则认为它们是同一个油田。计算油田的数量。
    • 难度：简单
    • 解题思路：使用BFS遍历每个油田格子，将连接的油田标记为已访问，计算需要进行BFS的次数。
    • 代码框架：
      int countOilDeposits(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int rows = grid.size(), cols = grid[0].size();
    int count = 0;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '@') {
                count++;
                bfs(grid, i, j);
            }
        }
    }
    
    return count;
}

  • POJ 3278. Catch That Cow

    • 题目描述：农夫约翰在坐标N处，他的牛在坐标K处。约翰每分钟可以走到x-1、x+1或2x位置。求约翰最少需要多少分钟才能到达他的牛的位置。
    • 难度：中等
    • 解题思路：使用BFS模拟约翰的移动过程，记录到达每个位置的最短时间。
    • 关键点：需要处理位置范围和避免重复访问。

  • CSES 1193. Labyrinth

    • 题目描述：给定一个迷宫，'.'表示可通行的格子，'#'表示墙壁，'A'表示起点，'B'表示终点。求从起点到终点的最短路径。
    • 难度：简单
    • 解题思路：从起始点开始BFS，记录路径，找到终点后回溯路径。
返回目录 信息学 BFS与队列专题 魅客科创中心

6.2 中级练习题

  • POJ 3984. 迷宫问题

    • 题目描述：给定一个5×5的迷宫，0表示通路，1表示墙壁。求从左上角到右下角的最短路径，并输出具体路径。
    • 难度：中等
    • 进阶思路：
      1. 使用双向BFS优化搜索效率
      2. 记录完整路径信息
      3. 处理多个终点的情况

  • CSES 1192. Counting Rooms

    • 题目描述：给定一个由'.'和'#'组成的网格，'.'表示空房间，'#'表示墙。求连通的房间数量。
    • 难度：中等
    • 解题思路：使用BFS遍历每个房间，标记已访问的房间。
    • 变种：
      • 计算最大房间面积
      • 找出所有房间的形状
      • 处理带门的房间

  • CSP-J 2022. 种植水稻

    • 题目描述：在一个网格田地中种植水稻，相邻的水稻会形成一片农田。求最少需要种植多少处才能使所有可耕地连通。
    • 难度：中等
    • 特点：
      • 需要考虑最优种植位置
      • 处理多个连通分量
      • 可以使用并查集优化
返回目录 信息学 BFS与队列专题 魅客科创中心

6.3 高级练习题

  • USACO Gold. Cow Navigation

    • 题目描述：在一个有障碍物的网格中，一头牛需要从起点到达终点。牛每次可以向北、东、南、西四个方向移动，但不知道自己的朝向。求最少需要多少次移动指令。
    • 难度：困难
    • 解题思路：
      1. 状态需要包含位置和朝向
      2. 使用BFS搜索最短指令序列
      3. 处理朝向不确定的情况

  • POJ 1324. Holedox Moving

    • 题目描述：在一个有障碍物的网格中，有一条长度为k的蛇需要从起点移动到终点。蛇的头可以向四个方向移动，身体会跟随头部移动。求最少需要多少步。
    • 难度：困难
    • 特点：
      • 需要记录蛇的完整状态
      • 使用状态压缩表示蛇的位置
      • 处理复杂的碰撞检测

  • CSES 1707. Graph Girth

    • 题目描述：给定一个无向图，求图中最短环的长度（girth）。
    • 难度：困难
    • 解题思路：
      1. 对每个节点进行BFS，寻找回到自身的最短路径
      2. 使用剪枝优化搜索效率
      3. 处理无环图的特殊情况
返回目录 信息学 BFS与队列专题 魅客科创中心

6.4 实践建议

  1. 循序渐进：

    • 从简单题目开始，逐步增加难度
    • 先掌握基本模板，再尝试优化方法
    • 注意总结每类问题的特点和解题模式

  2. 优化技巧：

    • 使用双向BFS减少搜索空间
    • 使用A*算法优化搜索方向
    • 使用状态压缩处理复杂状态
    • 预处理数据减少重复计算

  3. 代码实现：

    • 使用清晰的变量命名
    • 模块化函数便于维护
    • 注意边界条件处理
    • 考虑代码的可扩展性

  4. 常见陷阱：

    • 忘记标记已访问节点
    • 队列使用不当导致内存溢出
    • 方向数组定义错误
    • 没有处理特殊情况

  5. 提高建议：

    • 多总结不同类型的BFS应用
    • 练习不同的优化方法
    • 注意空间和时间的权衡
    • 尝试结合其他算法优化解法
返回目录 信息学 BFS与队列专题 魅客科创中心

7. 总结与提高

7.1 核心要点回顾

  1. BFS的本质：

    • 按层次扩展的搜索策略
    • 保证找到最短路径
    • 适合处理最短/最少步数问题

  2. 实现关键点：

    • 队列作为核心数据结构
    • 访问标记避免重复
    • 层次信息的维护
    • 路径的记录和重建

  3. 优化方法：

    • 双向BFS
    • A*搜索
    • 状态压缩
    • 预处理优化

  4. 常见应用场景：

    • 最短路径问题
    • 层次遍历
    • 连通性分析
    • 状态空间搜索
返回目录 信息学 BFS与队列专题 魅客科创中心

7.2 进阶方向

  1. 算法优化：

    • 研究启发式函数的设计
    • 探索更多的剪枝策略
    • 学习并行BFS的实现
    • 掌握记忆化搜索技巧

  2. 实际应用：

    • 游戏AI开发
    • 网络爬虫设计
    • 社交网络分析
    • 智能路径规划

  3. 结合其他算法：

    • BFS + 动态规划
    • BFS + 贪心算法
    • BFS + 并查集
    • BFS + 二分查找

  4. 性能调优：

    • 内存管理优化
    • 缓存友好的实现
    • 并发处理
    • 分布式BFS
返回目录 信息学 BFS与队列专题 魅客科创中心

7.3 学习建议

  1. 基础巩固：

    • 深入理解BFS的原理
    • 熟练掌握基本模板
    • 多做不同类型的题目
    • 注重代码质量

  2. 实践应用：

    • 实现实际项目
    • 参与开源项目
    • 尝试不同场景
    • 总结最佳实践

  3. 持续学习：

    • 关注算法前沿
    • 学习新的优化方法
    • 研究实际应用案例
    • 与他人交流分享

  4. 注意事项：

    • 平衡时间和空间复杂度
    • 考虑实际场景约束
    • 重视代码可维护性
    • 注意边界情况处理
返回目录 信息学 BFS与队列专题 魅客科创中心

这个讲义使用了Awesome Marp主题的蓝色风格。 内容针对竞赛选手设计，注重基础概念和实际应用。