C++ 实现广度优先搜索

广度优先搜索（BFS）基础概念

什么是广度优先搜索

广度优先搜索（Breadth - First Search，简称 BFS）是一种图形数据结构的遍历算法。它从给定的起始顶点开始，首先访问起始顶点，然后依次访问与起始顶点相邻的所有顶点，接着再访问这些相邻顶点的相邻顶点，以此类推，像一层一层地向外扩展，直到找到目标顶点或者遍历完整个图。

BFS 的搜索过程就好比在一个池塘中投入一颗石子，水波会以石子落水点为中心，一圈一圈地向外扩散。每一圈代表搜索的一个层次，BFS 总是先探索完当前层次的所有节点，再进入下一个层次。

BFS 的应用场景

1. 最短路径问题：在无权图中，BFS 可以用来找到从一个顶点到另一个顶点的最短路径。因为 BFS 是按照层次遍历的，第一个找到的目标顶点的路径就是最短路径。例如，在一个迷宫中寻找从起点到终点的最短路线，迷宫可以建模为一个图，每个格子是一个顶点，相邻格子之间有边相连。
2. 网络拓扑分析：在计算机网络中，BFS 可用于发现网络中所有可达的节点，或者计算网络中两个节点之间的跳数。比如在一个局域网中，想要知道从一台主机到另一台主机最少经过多少个路由器，就可以使用 BFS 算法。
3. 游戏开发：在一些棋类游戏或解谜游戏中，BFS 可以用于搜索最优的走法。例如，在扫雷游戏中，当玩家点击一个方块时，游戏需要以这个方块为起点，用 BFS 来确定哪些方块是安全可点击的，哪些是可能有雷的。

BFS 的实现原理

队列在 BFS 中的作用

BFS 的实现通常依赖于队列（Queue）这种数据结构。队列是一种先进先出（First - In - First - Out，FIFO）的数据结构。在 BFS 过程中，我们将待访问的顶点放入队列中。当队列为空时，表示所有可达顶点都已访问完毕。

具体来说，算法开始时，将起始顶点放入队列。然后，从队列中取出一个顶点，访问它，并将其所有未访问过的相邻顶点加入队列。这个过程不断重复，直到队列为空。

例如，假设有一个简单的图，顶点 A 有相邻顶点 B 和 C。当我们以 A 为起始顶点进行 BFS 时，先将 A 放入队列。然后取出 A 并访问它，接着把 B 和 C 放入队列。之后，从队列中取出 B（因为队列是 FIFO），访问 B 并将 B 的相邻顶点（如果有的话）放入队列，再取出 C 进行类似操作。

访问标记数组

为了避免重复访问同一个顶点，我们需要使用一个访问标记数组。这个数组的大小与图中顶点的数量相同，每个元素对应一个顶点。初始时，所有元素都标记为未访问。当一个顶点被访问时，就将其对应的数组元素标记为已访问。

例如，对于一个有 5 个顶点的图，我们可以定义一个长度为 5 的布尔数组 visited[5]，初始值都为 false。当访问顶点 2 时，将 visited[2] 设置为 true。这样，在后续的搜索过程中，如果遇到顶点 2，通过检查 visited[2] 是否为 true，就知道该顶点已经被访问过，不需要再次访问，从而避免陷入无限循环。

使用 C++ 实现 BFS

图的表示

在 C++ 中，有多种方式来表示图，常见的有邻接矩阵和邻接表。

1. 邻接矩阵：邻接矩阵是一个二维数组 adjMatrix[n][n]，其中 n 是图中顶点的数量。如果顶点 i 和顶点 j 之间有边相连，那么 adjMatrix[i][j] = 1（对于无向图，adjMatrix[j][i] 也为 1），否则 adjMatrix[i][j] = 0。邻接矩阵的优点是实现简单，对于判断两个顶点之间是否有边非常高效，时间复杂度为 $O(1)$。但是，如果图是稀疏图（边的数量远小于顶点数量的平方），邻接矩阵会浪费大量的空间，因为大部分元素都是 0。
2. 邻接表：邻接表是一种更节省空间的图表示方法，对于每个顶点，用一个链表（或动态数组）来存储它的相邻顶点。在 C++ 中，可以使用 std::vector 来实现邻接表。例如，对于顶点 i，adjList[i] 是一个 std::vector<int>，其中存储了与顶点 i 相邻的所有顶点的编号。邻接表的优点是节省空间，适用于稀疏图，并且对于遍历一个顶点的所有相邻顶点很方便。缺点是判断两个顶点之间是否有边，需要遍历邻接表，时间复杂度为 $O(d)$，其中 d 是顶点的度（相邻顶点的数量）。

下面以邻接表为例来实现 BFS。

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

// 图的邻接表表示
class Graph {
private:
    int V; // 顶点数量
    vector<vector<int>> adjList; // 邻接表

public:
    Graph(int vertices) : V(vertices), adjList(vertices) {}

    // 添加边
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        // 如果是无向图，还需要添加 v 到 u 的边
        adjList[v].push_back(u);
    }

    // BFS 实现
    void BFS(int start) {
        bool *visited = new bool[V];
        memset(visited, false, sizeof(bool) * V);

        queue<int> q;
        visited[start] = true;
        q.push(start);

        while (!q.empty()) {
            int current = q.front();
            q.pop();
            cout << current << " ";

            // 将当前顶点的所有未访问相邻顶点加入队列
            for (int i = 0; i < adjList[current].size(); ++i) {
                int neighbor = adjList[current][i];
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }

        delete[] visited;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    cout << "从顶点 2 开始的 BFS 遍历: ";
    g.BFS(2);

    return 0;
}

代码解析

1. 图的定义：Graph 类包含一个整数 V 表示顶点数量，以及一个二维向量 adjList 作为邻接表。构造函数 Graph(int vertices) 初始化顶点数量和邻接表的大小。
2. 添加边：addEdge(int u, int v) 函数用于向图中添加边。对于无向图，需要在邻接表中同时添加 u 到 v 和 v 到 u 的边。
3. BFS 函数：
   • 首先，创建一个布尔数组 visited 并初始化为 false，用于标记每个顶点是否被访问过。
   • 创建一个队列 q，将起始顶点 start 标记为已访问并放入队列。
   • 在 while (!q.empty()) 循环中，从队列中取出一个顶点 current，输出它，并遍历它的所有相邻顶点。如果某个相邻顶点 neighbor 未被访问过，则将其标记为已访问并放入队列。
4. 主函数：在 main 函数中，创建一个有 5 个顶点的图，并添加一些边。然后调用 BFS 函数从顶点 2 开始进行广度优先搜索，并输出遍历结果。

BFS 的时间和空间复杂度

时间复杂度

对于邻接表表示的图，BFS 的时间复杂度为 $O(V + E)$，其中 V 是顶点的数量，E 是边的数量。这是因为每个顶点最多被访问一次（入队一次），时间复杂度为 $O(V)$，而每条边最多被检查两次（一次从边的一端顶点出发，一次从另一端顶点出发），时间复杂度为 $O(E)$。

对于邻接矩阵表示的图，虽然访问每个顶点也是 $O(V)$，但检查每个顶点的所有邻接顶点需要遍历整个矩阵的一行，时间复杂度为 $O(V)$，总共有 V 个顶点，所以总的时间复杂度为 $O(V^2)$。

空间复杂度

BFS 的空间复杂度主要取决于队列和访问标记数组。对于访问标记数组，需要 $O(V)$ 的空间。队列在最坏情况下可能存储所有顶点，所以也需要 $O(V)$ 的空间。因此，总的空间复杂度为 $O(V)$。

优化与扩展

双向 BFS

双向 BFS 是对传统 BFS 的一种优化，它从起始顶点和目标顶点同时开始进行 BFS。这种方法可以显著减少搜索空间，特别是在图比较大且目标顶点距离起始顶点较远的情况下。

双向 BFS 的基本思路是，同时维护两个队列，一个从起始顶点开始，另一个从目标顶点开始。每次迭代时，从两个队列中各取出一个顶点进行扩展，当两个扩展的搜索区域相遇时，就找到了最短路径。

双向 BFS 的时间复杂度比普通 BFS 更低，理论上在完全图中，双向 BFS 的时间复杂度为 $O(\sqrt{V})$，而普通 BFS 的时间复杂度为 $O(V)$。不过，双向 BFS 的实现相对复杂，需要额外的逻辑来处理两个搜索方向的相遇情况。

带权图的 BFS 变体

在带权图中，边具有权重，传统的 BFS 不能直接用于寻找最短路径，因为它没有考虑边的权重。一种改进方法是使用优先队列（Priority Queue）来代替普通队列。优先队列会根据边的权重对顶点进行排序，每次取出权重最小的顶点进行扩展。

这种算法被称为迪杰斯特拉（Dijkstra）算法，它可以在带权图中找到从一个顶点到其他所有顶点的最短路径。迪杰斯特拉算法与 BFS 的主要区别在于，BFS 每次从队列中取出最早加入的顶点，而迪杰斯特拉算法每次从优先队列中取出距离起始顶点权重最小的顶点。

在 C++ 中，可以使用 std::priority_queue 来实现迪杰斯特拉算法。std::priority_queue 默认是大顶堆，需要自定义比较函数来实现小顶堆，以便优先取出权重最小的顶点。

并行 BFS

在现代多核处理器环境下，为了提高 BFS 的执行效率，可以采用并行计算的方式。并行 BFS 的基本思想是将图划分成多个部分，每个部分由一个线程或进程来处理。不同线程同时对各自负责的部分进行 BFS 搜索，然后通过某种同步机制来合并结果。

例如，可以按照顶点编号将图划分为多个子图，每个线程负责一个子图的 BFS 遍历。在遍历过程中，线程之间需要共享访问标记数组等数据结构，并通过锁或其他同步机制来避免数据竞争。并行 BFS 可以充分利用多核处理器的计算能力，大大提高大规模图的搜索效率，但实现起来较为复杂，需要仔细考虑线程同步和负载均衡等问题。

实际案例分析

迷宫求解

假设我们有一个迷宫，用二维数组表示，其中 0 表示通路，1 表示墙壁。我们要从起点找到一条到终点的最短路径。可以将迷宫中的每个格子看作一个顶点，相邻的通路格子之间有边相连。

下面是一个简单的迷宫求解代码示例：

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int ROWS = 5;
const int COLS = 5;

// 方向数组，分别表示上、下、左、右
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

struct Point {
    int x;
    int y;
    int steps;

    Point(int _x, int _y, int _steps) : x(_x), y(_y), steps(_steps) {}
};

bool isValid(int x, int y) {
    return x >= 0 && x < ROWS && y >= 0 && y < COLS;
}

int BFS(int startX, int startY, int endX, int endY, vector<vector<int>> &maze) {
    bool visited[ROWS][COLS];
    memset(visited, false, sizeof(visited));

    queue<Point> q;
    q.push(Point(startX, startY, 0));
    visited[startX][startY] = true;

    while (!q.empty()) {
        Point current = q.front();
        q.pop();

        if (current.x == endX && current.y == endY) {
            return current.steps;
        }

        for (int i = 0; i < 4; ++i) {
            int newX = current.x + dirs[i][0];
            int newY = current.y + dirs[i][1];

            if (isValid(newX, newY) && maze[newX][newY] == 0 &&!visited[newX][newY]) {
                q.push(Point(newX, newY, current.steps + 1));
                visited[newX][newY] = true;
            }
        }
    }

    return -1; // 无法到达终点
}

int main() {
    vector<vector<int>> maze = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0}
    };

    int startX = 0, startY = 0;
    int endX = 4, endY = 4;

    int steps = BFS(startX, startY, endX, endY, maze);
    if (steps != -1) {
        cout << "最短路径步数: " << steps << endl;
    } else {
        cout << "无法到达终点" << endl;
    }

    return 0;
}

代码解析

1. 方向数组：dirs 数组定义了四个方向，分别是上、下、左、右，用于在迷宫中移动。
2. 点结构体：Point 结构体用于存储当前位置的坐标 (x, y) 以及从起点到该点的步数 steps。
3. 合法性检查：isValid 函数用于检查坐标 (x, y) 是否在迷宫范围内。
4. BFS 函数：
   • 初始化一个二维的访问标记数组 visited，用于记录每个格子是否被访问过。
   • 将起点加入队列，并标记为已访问。
   • 在循环中，从队列取出当前点，如果当前点是终点，则返回步数。否则，尝试向四个方向移动，如果新位置合法、是通路且未被访问过，则将新点加入队列，并更新访问标记。
5. 主函数：定义了一个迷宫，并设置起点和终点，调用 BFS 函数求解最短路径步数，并输出结果。

社交网络好友推荐

在社交网络中，可以将用户看作顶点，用户之间的好友关系看作边。假设我们要为某个用户推荐可能认识的人，可以使用 BFS 来实现。

以一个简单的社交网络模型为例，假设每个用户有一个唯一的 ID，并且我们有一个函数 getFriends(int userId) 可以获取某个用户的所有好友 ID。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

// 模拟获取好友列表的函数
vector<int> getFriends(int userId) {
    // 这里只是模拟返回数据，实际应用中会从数据库或其他数据源获取
    if (userId == 1) {
        return {2, 3};
    } else if (userId == 2) {
        return {1, 4};
    } else if (userId == 3) {
        return {1, 5};
    } else if (userId == 4) {
        return {2};
    } else if (userId == 5) {
        return {3};
    }
    return {};
}

void recommendFriends(int targetUserId) {
    unordered_set<int> visited;
    queue<int> q;
    q.push(targetUserId);
    visited.insert(targetUserId);

    while (!q.empty()) {
        int currentUserId = q.front();
        q.pop();

        vector<int> friends = getFriends(currentUserId);
        for (int friendId : friends) {
            if (visited.find(friendId) == visited.end()) {
                cout << "推荐用户: " << friendId << endl;
                visited.insert(friendId);
                q.push(friendId);
            }
        }
    }
}

int main() {
    int targetUserId = 1;
    cout << "为用户 " << targetUserId << " 推荐好友:" << endl;
    recommendFriends(targetUserId);

    return 0;
}

代码解析

1. 好友获取函数：getFriends(int userId) 函数模拟从社交网络数据中获取某个用户的好友列表。在实际应用中，这个函数可能会从数据库查询或调用 API 获取数据。
2. 推荐好友函数：
   • 使用 unordered_set<int> 来记录已经访问过的用户 ID，避免重复推荐。
   • 将目标用户 ID 加入队列，并标记为已访问。
   • 在循环中，从队列取出当前用户 ID，获取其好友列表。对于每个未访问过的好友，输出推荐信息，并将其加入队列和访问集合。
3. 主函数：设置目标用户 ID 为 1，并调用 recommendFriends 函数为该用户推荐好友。

通过以上对 BFS 在不同实际案例中的应用，我们可以看到 BFS 算法在解决各种与图相关的问题中具有重要作用，并且通过 C++ 可以灵活高效地实现。无论是迷宫求解还是社交网络分析，BFS 都能为我们提供有效的解决方案。同时，通过对 BFS 的优化和扩展，我们可以进一步提高其在不同场景下的性能和适用性。在实际应用中，需要根据具体问题的特点选择合适的图表示方法、BFS 变体以及优化策略，以达到最佳的效果。