BFS算法篇——从晨曦到星辰，BFS算法在多源最短路径问题中的诗意航行（上）

引言

在浩渺的图论宇宙中，图的每一条边、每一个节点都是故事的组成部分。每当我们站在一个复杂的迷宫前，开始感受它的深邃时，我们往往不再局限于从单一的起点发起探索。或许，有无数个起点、无数条探索的轨迹在同时交织。这时，便是多源广度优先搜索（Multi-Source
BFS）登场的时刻。

如同晨曦的曙光照亮夜空，多个源点同时发散开来，照亮迷宫的每一个角落，指引着我们找到通往目标的最短路径。多源BFS不仅仅是一个算法，它是多重探索的交响曲，协调着每一个起点的步伐，最终走向那个我们期待已久的目标。

一、多源BFS的概述

在经典的广度优先搜索（BFS）中，我们从一个源点出发，按层次依次扩展到邻居节点，直到找到目标节点。而在多源BFS的情境下，存在多个起始点，我们不再仅仅从单一节点开始，而是同时从多个节点出发，展开多条路径的探索。这种策略不仅提高了算法的效率，也让多源点的最短路径问题变得更加优雅。

二、应用场景

多源BFS算法广泛应用于那些需要从多个起点同时进行搜索的场景。例如：

• 地图导航：从多个起点（例如多个车站或不同的出发地）同时计算到达目的地的最短路径。
• 信息传播：在网络中，有多个信息源（如多个广告商）同时传播信息，如何找到每个节点到达某个信息源的最短时间。
• 社交网络分析：分析多个朋友间的最短社交距离，或者多个用户间的互动路径。

三、算法步骤

多源BFS与普通BFS的最大区别在于

• 初始时我们将所有的源点放入队列中，而不是仅有一个源点。之后的步骤与普通BFS相似，依旧是逐层访问邻居节点，只不过这一次，我们的探索是由多个起点同时进行的。

• 初始化：将所有源点加入队列，并标记为已访问。

• 队列处理：每次从队列中取出一个节点，检查它的邻居节点。如果邻居节点未被访问过，则将其加入队列并标记为已访问。

• 终止条件：直到所有可能的节点都被访问完，或者达到目标节点。

四、代码实现

以下是用C语言实现多源BFS的代码，通过它可以求解一个迷宫中多个起点到目标节点的最短路径问题。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

// 定义节点
typedef struct {
    int x, y, dist;
} Node;

// 四个方向：上、下、左、右
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 队列操作
typedef struct {
    Node nodes[MAX * MAX];
    int front, rear;
} Queue;

// 队列初始化
void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

// 入队
void enqueue(Queue* q, Node node) {
    q->nodes[q->rear++] = node;
}

// 出队
Node dequeue(Queue* q) {
    return q->nodes[q->front++];
}

// 判断队列是否为空
bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

// 多源BFS求最短路径
int multiSourceBFS(int maze[MAX][MAX], Node sources[], int numSources, int targetX, int targetY, int n, int m) {
    Queue q;
    initQueue(&q);

    bool visited[MAX][MAX] = {false};
    
    // 将所有源点加入队列并标记为已访问
    for (int i = 0; i < numSources; i++) {
        visited[sources[i].x][sources[i].y] = true;
        enqueue(&q, sources[i]);
    }

    while (!isEmpty(&q)) {
        Node current = dequeue(&q);

        // 如果到达目标节点
        if (current.x == targetX && current.y == targetY) {
            return current.dist;
        }

        // 处理四个方向的邻居
        for (int i = 0; i < 4; i++) {
            int newX = current.x + directions[i][0];
            int newY = current.y + directions[i][1];

            // 判断是否越界，是否可以走
            if (newX >= 0 && newX < n && newY >= 0 && newY < m && maze[newX][newY] == 0 && !visited[newX][newY]) {
                visited[newX][newY] = true;
                enqueue(&q, (Node){newX, newY, current.dist + 1});
            }
        }
    }

    return -1; // 无法到达目标
}

int main() {
    // 迷宫示例：0 表示通路，1 表示墙
    int maze[MAX][MAX] = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 1, 0},
        {1, 1, 0, 0, 0}
    };

    int n = 4, m = 5; // 迷宫的行列数
    Node sources[] = {{0, 0, 0}, {0, 1, 0}}; // 多个源点
    int numSources = 2; // 源点个数
    int targetX = 3, targetY = 4; // 目标节点

    int result = multiSourceBFS(maze, sources, numSources, targetX, targetY, n, m);
    if (result != -1) {
        printf("从多个源点到目标的最短路径长度为: %d\n", result);
    } else {
        printf("无法到达目标\n");
    }

    return 0;
}

五、代码解释

• 结构体定义：我们定义了一个 Node 结构体来表示队列中的每个节点，包括节点的坐标 (x, y) 和到达该节点的步数 dist。

• 队列操作：Queue 结构体用于实现队列，enqueue 和 dequeue 操作分别用于插入节点和取出节点。

多源BFS 核心逻辑：

• 通过将所有源点放入队列中，启动多个路径的并行探索。
• 每次从队列中取出一个节点，检查它的邻居节点，并根据条件判断是否可以扩展到该邻居节点。
• 如果找到目标节点，立即返回当前的路径长度。

六、总结

多源BFS就像是一场协调并行的交响乐，不同的源点在同一时刻开始演奏，最终汇聚成一条优雅的最短路径。通过这种并行的探索方式，我们不仅加速了路径搜索，也让算法的运行效率得到了显著提升。

如同多束光线从不同方向照亮世界，BFS在多源点的帮助下展现了它的另一种优雅，给我们提供了一个更加高效且完美的解决方案。在未来的复杂世界中，无论有多少起点，我们都可以从中找到最短的路径，指引我们走向每一个光明的目的地

本篇关于多源BFS的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！