文章目录
- 前言
- 一、BFS的思路
- 二、BFS的C语言实现
- 1. 图的表示
- 2. 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 - B
addEdge(graph, 0, 2); // A - C
addEdge(graph, 1, 3); // B - D
addEdge(graph, 1, 4); // B - E
addEdge(graph, 2, 4); // C - E
addEdge(graph, 3, 5); // D - F
addEdge(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算法篇的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
