BFS算法篇——广度优先搜索，探索未知的旅程（上）

前言

广度优先搜索（BFS）是一种广泛应用于图论中的算法，常用于寻找最短路径、图的遍历等问题。与深度优先搜索（DFS）不同，BFS通过层级地探索节点来确保最先访问的节点距离源点较近，因此它可以用来求解最短路径问题。让我们深入了解这个算法，并通过具体的例子和代码来进一步掌握它的实现。

一、BFS的思路

BFS的主要思想是从起始节点开始，首先访问该节点的所有邻接节点，然后再访问这些邻接节点的邻接节点。BFS利用队列的先进先出（FIFO）特性保证了节点是按层次顺序被访问的。

二、BFS的C语言实现

1. 图的表示

在C语言中，我们常用邻接表来表示图。对于无向图，我们可以使用一个邻接矩阵或者邻接链表。在这里，我们采用邻接链表表示图。

2. BFS的实现

以下是C语言实现BFS算法的具体代码，图使用邻接表表示：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_NODES 6  // 节点数量// 图的邻接表结构
typedef struct Node {int data;struct Node* next;
} Node;typedef struct Graph {Node* adjList[MAX_NODES];
} Graph;// 队列结构
typedef struct Queue {int items[MAX_NODES];int front, rear;
} Queue;// 创建一个新的图
Graph* createGraph() {Graph* graph = (Graph*)malloc(sizeof(Graph));for (int i = 0; i < MAX_NODES; i++) {graph->adjList[i] = NULL;}return graph;
}// 向图中添加一条边
void addEdge(Graph* graph, int src, int dest) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = dest;newNode->next = graph->adjList[src];graph->adjList[src] = newNode;// 因为是无向图，所以添加反向边newNode = (Node*)malloc(sizeof(Node));newNode->data = src;newNode->next = graph->adjList[dest];graph->adjList[dest] = newNode;
}// 初始化队列
void initQueue(Queue* q) {q->front = -1;q->rear = -1;
}// 入队
void enqueue(Queue* q, int value) {if (q->rear == MAX_NODES - 1) {printf("队列已满\n");return;}if (q->front == -1) {q->front = 0;}q->rear++;q->items[q->rear] = value;
}// 出队
int dequeue(Queue* q) {if (q->front == -1) {printf("队列为空\n");return -1;}int item = q->items[q->front];q->front++;if (q->front > q->rear) {q->front = q->rear = -1;}return item;
}// 判断队列是否为空
bool isQueueEmpty(Queue* q) {return q->front == -1;
}// 广度优先搜索BFS
void bfs(Graph* graph, int start) {bool visited[MAX_NODES] = {false};  // 访问标志数组Queue q;initQueue(&q);// 标记起始节点为已访问，并入队visited[start] = true;enqueue(&q, start);while (!isQueueEmpty(&q)) {// 出队并访问节点int node = dequeue(&q);printf("%c ", node + 'A');  // 输出节点（假设节点是字母A, B, C...）// 遍历当前节点的所有邻接节点Node* temp = graph->adjList[node];while (temp) {int adjNode = temp->data;if (!visited[adjNode]) {visited[adjNode] = true;enqueue(&q, adjNode);}temp = temp->next;}}
}int main() {// 创建图并添加边Graph* graph = createGraph();addEdge(graph, 0, 1);  // A - BaddEdge(graph, 0, 2);  // A - CaddEdge(graph, 1, 3);  // B - DaddEdge(graph, 1, 4);  // B - EaddEdge(graph, 2, 4);  // C - EaddEdge(graph, 3, 5);  // D - FaddEdge(graph, 4, 5);  // E - F// 执行BFS从节点A（索引0）开始printf("BFS遍历结果: ");bfs(graph, 0);// 释放内存free(graph);return 0;
}

三、代码解析

图的表示：

• 图使用邻接表表示。每个节点用一个链表来存储与其直接相连的节点。Graph结构体中有一个数组 adjList 来保存所有节点的邻接链表。

队列的实现：

• 队列用数组来实现，包含 front 和 rear 来管理队列的操作。队列用于按顺序访问图的每个节点。

BFS的实现：

• 使用队列来管理待访问的节点。首先将起始节点标记为已访问并入队。然后逐步出队并访问节点，访问节点的邻接节点，如果邻接节点未被访问，则将其标记为已访问并入队。
• 输出遍历的节点（假设节点为字母，如 A, B, C, …）。

四、输出结果

假设图的结构如下所示：

    A -- B -- D|    |    |C -- E -- F

输出结果将为：

BFS遍历结果: A B C D E F 

这意味着从节点 A 开始，BFS按层次遍历的顺序访问了图中的所有节点。

五、总结

• BFS是一种通过逐层扩展来遍历图的算法，通常用于求解最短路径问题、图的遍历等。
• 在C语言中，BFS通常使用队列来实现，队列的先进先出特性确保了图的层次遍历。
• 本例中通过邻接表表示图，使用队列来实现BFS遍历，从而找到节点间的最短路径。
• 广度优先搜索在实际问题中具有广泛的应用，例如在社交网络分析、路径规划等方面，都可以发挥其强大的作用。

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