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

文章目录

前言
一、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 - 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;
}