路径规划（一）：广度优先搜索算法（BFS）

一、概述

??广度优先搜索算法，简称BFS（Breadth-First Search），是一种图搜索算法。它从起始节点开始，依次遍历与起始节点相邻的节点，然后依次遍历与这些节点相邻但尚未访问的节点，直到遍历完所有与起始节点连接的节点。
??BFS的优点是能够找到最短路径。当需要找到两个节点之间的最短路径时，可以使用BFS来解决。它也适用于无权图的遍历，以及寻找图中的连通分量和环的问题。

二、BFS算法步骤

BFS算法的步骤如下：

1. 创建一个队列，用于存储待访问的节点。
2. 将起始节点入队列。
3. 标记起始节点为已访问。
4. 当队列不为空时执行以下步骤：
   • 出队列当前节点，并访问该节点。
   • 对当前节点的所有邻接节点进行以下操作：
     • 如果邻接节点未被访问，则将其入队列，并标记为已访问。
5. 重复步骤4直到队列为空。

三、相关代码

#include <stdio.h>

#define MAX_SIZE 100

int graph[MAX_SIZE][MAX_SIZE]; // 图的邻接矩阵
int visited[MAX_SIZE]; // 访问标记数组
int queue[MAX_SIZE]; // 队列

int front = -1; // 队列头指针
int rear = -1; // 队列尾指针

// 入队列
void enqueue(int vertex) {
    if (rear == MAX_SIZE - 1) {
        printf("Queue is full.\n");
        return;
    }
    if (front == -1) {
        front = 0;
    }
    rear++;
    queue[rear] = vertex;
}

// 出队列
int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue is empty.\n");
        return -1;
    }
    int vertex = queue[front];
    front++;
    return vertex;
}

// 广度优先搜索算法
void bfs(int start, int numVertices) {
    // 初始化访问标记数组
    for (int i = 0; i < numVertices; i++) {
        visited[i] = 0;
    }

    // 将起始节点入队列并标记为已访问
    enqueue(start);
    visited[start] = 1;

    while (front != -1 && front <= rear) {
        // 出队列并访问节点
        int currentVertex = dequeue();
        printf("%d ", currentVertex);

        // 遍历当前节点的邻接节点
        for (int i = 0; i < numVertices; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int numVertices, start;
    printf("Enter the number of vertices in the graph: ");
    scanf("%d", &numVertices);

    printf("Enter the adjacency matrix of the graph:\n");
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    printf("Enter the starting vertex: ");
    scanf("%d", &start);

    printf("BFS traversal: ");
    bfs(start, numVertices);

    return 0;
}