C语言广度优先搜索(BFS)遍历图解与代码实现

广度优先搜索过程

使用广度优先搜索来遍历一个图的过程如下。首先以一个未被访问过的顶点作为起始顶点，例如以1号点作为起始顶点。

将1号点放入队列中，然后将与1号点相邻的所有未访问过的顶点（即2、3、5号顶点）依次放入队列中：

接下来取出队首元素（2号顶点），将其相邻的未访问过的顶点4号放入到队列中。此时所有顶点都已被访问过，遍历结束：

最终得到的遍历序列为：1 → 2 → 3 → 5 → 4（具体顺序取决于相邻顶点的存储顺序，但层级关系不变）。整个过程形象地展示了如图形水波般向外扩展的效果：

当所有节点被访问完毕后，整个遍历流程完成：

主要思想

1. 初始化：选择一个未被访问的顶点作为起点，将其加入队列并标记为已访问。
2. 循环处理：只要队列不为空，就取出队首顶点 cur。
3. 拓展邻居：检查 cur 的所有相邻顶点。如果某个邻居未被访问，则将其加入队列，并标记为已访问。
4. 结束条件：当队列为空或所有顶点都被访问过时，遍历结束。

BFS的核心在于“先进先出”（FIFO）的队列机制，它保证了在同一层次的节点会被连续访问，从而实现由近及远的扫描效果。

第1步：定义数据结构与初始化

为了表示图和进行遍历，我们需要以下变量：

• e[101][101]：二维数组，用于存储图的邻接矩阵。这里假设99999999代表无穷大（无边）。
• book[101]：标记数组，book[i]=1表示顶点i已被访问过，防止重复入队。
• que[10001]：一维数组模拟队列。
• head, tail：分别指向队头和队尾的位置指针。

初始化邻接矩阵

首先将所有距离初始化为极大值，自身到自身的距离设为0：

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
        if (i == j) e[i][j] = 0;
        else e[i][j] = 99999999;

读入边信息

因为是无向图，输入边 a b 时，需双向赋值：

scanf("%d %d", &a, &b);
e[a][b] = 1;
e[b][a] = 1;

第2步：执行BFS遍历逻辑

这一步是核心算法部分，通过队列控制访问顺序。

起点入队

从1号顶点出发，将其加入队列末尾，并标记为已访问：

que[tail] = 1;
tail++; // 队尾指针后移
book[1] = 1; // 标记1号顶点已入列

循环弹出与拓展

当 head < tail 且未达到边界时，持续循环：

1. 获取当前点：cur = que[head];
2. 扫描所有邻居：遍历 i`从1到n`。
3. 判断与入队：如果 e[cur][i] == 1（有边相连）且 book[i] == 0（未访问），则：
   que[tail] = i;
tail++; book[i] = 1;
4. 更新队头：当前点处理完毕，head++，准备处理下一个节点。

while (head < tail && tail <= n)
{
    cur = que[head];
    for (i = 1; i <= n; i++)
    {
        if (e[cur][i] == 1 && book[i] == 0)
        {
            que[tail] = i;
            tail++;
            book[i] = 1;
        }
        if (tail > n) break; // 提前退出优化
    }
    head++;
}

完整代码实现

#include <stdio.h>
int main()
{
    int i, j, m, a, b, cur, n, book[101] = { 0 }, e[101][101];
    int que[10001], head, tail;

    // 输入顶点数n和边数m
    scanf("%d %d", &n, &m);

    // 初始化二维矩阵
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999; // 假设99999999为无穷大

    // 读入顶点之间的边
    for (i = 1; i <= n; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1; // 无向图，双向连接
    }

    // 队列初始化
    head = 1;
    tail = 1;

    // 从1号顶点出发，将1号顶点加入队列
    que[tail] = 1;
    tail++;
    book[1] = 1; // 标记1号顶点已经入列

    // 当队列不为空时循环
    while (head < tail && tail <= n)
    {
        cur = que[head]; // 当前正在访问的顶点编号
        for (i = 1; i <= n; i++)
        {
            // 判断从顶点cur到顶点i是否有边，并判断顶点i是否访问过
            if (e[cur][i] == 1 && book[i] == 0)
            {
                // 如果从顶点cur到顶点i有边，且顶点i没有被访问过，将顶点i入列
                que[tail] = i;
                tail++;
                book[i] = 1; // 标记表示已经访问过
            }
            if (tail > n) // 表示所有点都已经访问过（针对连通图的小优化）
                break;
        }
        head++;
        // 注意这个地方，不要忘记head++后，才能继续向下拓展
    }

    // 输出遍历结果
    for (i = 1; i < tail; i++)
        printf("%d", que[i]);

    return 0;
}

简要总结

广度优先搜索（BFS）通过队列实现了图的层级遍历。关键点在于使用 book 数组防止回路造成的死循环或重复计算。相比深度优先搜索，BFS通常用于寻找最短路径问题。以上就是C语言广度优先搜索遍历的详细内容，更多关于C语言数据结构与算法的资料请关注本站其它相关文章！