困难C++6 分钟2,255 字

C++图的BFS遍历

图的广度优先搜索:像水波一样一圈圈探索

想象一下,你把一颗石子扔进平静的湖面,水面会泛起一圈一圈的波纹,从中心向外扩散。​广度优先搜索(BFS)​ 就像这种波纹——它从一个起点出发,先访问离起点最近的邻居,再访问邻居的邻居,一层一层向外探索。在计算机里,BFS常用来解决“最短路径”“连通性”等问题,比如在迷宫游戏里找到从起点到终点的最短路线,或者在社交网络中找出你和某个朋友之间最少通过几个人认识。


1. BFS的核心思想:先近后远

BFS的规则很简单:​先访问离起点距离为1的所有顶点,再访问距离为2的,然后是距离为3的……

举个例子:假设你是一个班长,要在班级里快速传递一个通知。你先把通知告诉坐在你周围的4个同学(距离为1),然后这4个同学再告诉他们周围的同学(距离为2),这样消息就像波纹一样扩散开。​BFS保证每个节点第一次被访问时,就是从起点到它的最短路径​​(在无权图中)。

  • 生活中的例子​​:老师让小明把作业传给全班同学,但不能重复传。小明先把作业递给前后左右的同学,这些同学再递给他们周围还没拿到作业的人。这样每次传递,作业离小明就更远一层,这就是BFS。

2. 用队列实现“一层一层”的访问

BFS需要一个关键工具:​队列​​(Queue)。队列的特点是“先进先出”,就像排队买零食——先排的人先买到。在BFS中,我们先把起点加入队列,然后重复以下步骤:

  1. 从队列取出​一个顶点(排在最前面的)。
  2. 访问​这个顶点(比如打印它的编号)。
  3. 把这个顶点的所有未访问的邻居​加入队列(排在队尾)。

这样,队列里永远先存放“当前层”的顶点,再存放“下一层”的顶点。因为队列先进先出,所以当前层的顶点会先被取出并访问,之后才是下一层。

对比生活中的排队​​:想象你在游乐场排队玩过山车, BFS就相当于让一个项目的工作人员先服务完当前排队的游客,然后再叫下一批游客进入。而DFS(深度优先搜索)就像一个人发现一个好玩的项目就一口气玩到底,再回来玩别的。


3. 代码实现:一步一步拆解

我们还是用邻接表​来存储图(每个顶点用数组存它的邻居列表)。需要一个 visited 数组记录哪些顶点已经被访问过,防止重复入队。

下面这段代码实现了从起点0开始的BFS遍历:

cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100;            // 最大顶点数
vector<int> graph[MAXN];         // 邻接表,graph[i]里存着i的所有邻居编号
bool visited[MAXN];              // 标记是否访问过

void bfs(int start) {
    queue<int> q;                // 创建一个队列,用来存待访问的顶点
    q.push(start);               // 把起点放进队列
    visited[start] = true;       // 标记起点已访问

    while (!q.empty()) {
        int u = q.front();       // 取出队首顶点(当前要访问的顶点)
        q.pop();                 // 把它从队列里删掉
        cout << u << " ";        // 访问这个顶点(打印编号)

        // 遍历u的所有邻居
        for (int v : graph[u]) {
            if (!visited[v]) {   // 如果邻居还没访问过
                visited[v] = true; // 标记为已访问(防止重复)
                q.push(v);       // 邻居入队,等到下一层再访问
            }
        }
    }
}

代码关键点​​:

  • 每次从队列取出一个顶点,立即访问它。
  • 遍历它的邻居时,​只有未访问过的邻居才入队​​,并且要立刻标记为已访问。为什么要立刻标记?因为如果不标记,同一个邻居可能被多个上层顶点重复加入队列,导致死循环(比如两个顶点互相连接)。

4. 完整的可运行示例:一个具体图

让我们用一个小图来测试。图中有5个顶点(编号0到4),边为:0-1, 0-2, 1-3, 1-4(无向图)。从顶点0开始BFS。

cpp
int main() {
    int n = 5;   // 顶点数
    int m = 4;   // 边数
    // 手动加边,也可以用循环输入
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(0);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(0);
    graph[3].push_back(1);
    graph[4].push_back(1);

    bfs(0); // 从顶点0开始遍历
    return 0;
}

运行结果:0 1 2 3 4

过程解释​​:

  • 第一层(距离0):起点0。访问0,把它的邻居1和2入队。队列:[1, 2]
  • 第二层(距离1):取出1,访问1,把它的未访问邻居3和4入队。队列:[2, 3, 4]
  • 取出2,访问2(它只有邻居0,但0已访问,无新邻居)。队列:[3, 4]
  • 第三层(距离2):取出3,访问3;取出4,访问4。队列空。 输出顺序正好是先距离1的(1和2),再距离2的(3和4)。

5. 常见错误(新手要小心)

  • 忘记标记 visited​​:如果只入队不标记,同一个顶点可能被多次加入队列,程序会无限循环(因为每次从队列取出又会把它的邻居再入队)。​一定要在入队时立即标记,而不是在访问时标记​​(虽然访问时标记也可以,但入队时标记可以防止重复入队,更高效)。
  • 邻接表只加一边​​:对于无向图,边 u-v 需要在 graph[u] 和 graph[v] 中都加入,否则遍历时只能单向走。如果忘记加另一侧,会导致部分顶点无法到达。
  • 队列使用错误​​:注意 q.front() 只返回队首元素,要用 q.pop() 删除它。忘记 pop 会导致死循环。
  • 起点未标记​​:bfs 函数开头一定要把起点标记为已访问,否则起点自己可能被重复加入队列。

6. BFS和DFS的对比:一个水平,一个垂直

特点 BFS(广度优先) DFS(深度优先)
数据结构 队列 栈(或递归)
访问顺序 一层一层,先近后远 一条路走到底,再回溯
适用场景 最短路径(无权图)、连通性 拓扑排序、路径查找、连通块
记忆辅助 像水波扩散 像钻头往下钻

举个例子:如果你在迷宫里找出口,BFS保证第一次找到出口时走的是最短路径;DFS则可能先钻进一条死胡同,绕很远才能找到出口。


7. 完整可运行的代码(包含输入)

下面是一个完整的程序,可以从键盘输入顶点数和边数,然后输入所有边,最后从顶点0开始BFS遍历。

cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100;            // 最大顶点数
vector<int> graph[MAXN];         // 邻接表
bool visited[MAXN];              // 访问标记

void bfs(int start) {
    queue<int> q;                // 队列
    q.push(start);               // 起点入队
    visited[start] = true;       // 标记起点

    while (!q.empty()) {
        int u = q.front();       // 取出队首
        q.pop();
        cout << u << " ";        // 访问当前顶点

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);       // 未访问的邻居入队
            }
        }
    }
}

int main() {
    int n, m;                    // n个顶点,m条边
    cout << "请输入顶点数和边数:";
    cin >> n >> m;

    cout << "请输入每条边的两个顶点(编号从0开始):" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);   // 无向图,加边两次
        graph[v].push_back(u);
    }

    cout << "BFS遍历结果(从顶点0开始):";
    bfs(0);
    cout << endl;
    return 0;
}

运行示例​​:

请输入顶点数和边数:5 4
请输入每条边的两个顶点(编号从0开始):
0 1
0 2
1 3
1 4
BFS遍历结果(从顶点0开始):0 1 2 3 4

8. 学完BFS后,可以继续学习什么?

  • 用BFS求最短路径​​:记录每个顶点是从哪个顶点过来的(父节点),遍历结束后反向输出路径。
  • BFS与队列的更多应用​​:比如在树中做层序遍历,在网格中做“洪水填充”算法(类似“扫雷”游戏自动展开空白区域)。
  • DFS(深度优先搜索)​​​:用栈或递归实现,适合解决“全排列”“八皇后”等问题。
  • 图的存储方式​​:邻接矩阵 vs 邻接表,了解不同数据结构的优缺点。
  • 拓扑排序​​:利用队列的BFS思想可以解决课程安排等依赖关系问题。

BFS是你掌握图算法的一把钥匙,理解它之后,很多看似复杂的问题都能用“一层一层扩散”的思路来解决。试着写一个小程序,用BFS找到从你家到学校的地图最短路线吧!

同类知识点