广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的结构的算法。这个算法从图的某一结点开始遍历，然后访问所有相邻的节点。然后对这些相邻节点，再看它们的未被访问过的相邻节点，以此类推。这种方式就是广度优先，也可以理解为先访问完一层再访问下一层。
以下是一个使用广度优先搜索访问图的C语言代码示例。为了简化问题，我们假设图中的节点表示为整数，并使用邻接矩阵来表示图。代码中有详细的注释和解释。
#include <stdio.h>
#define SIZE 40
struct queue {
int items[SIZE];
int front;
int rear;
};
// 创建一个新的队列
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}
// 向队列中添加元素
void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
// 从队列中移除元素
int dequeue(struct queue* q) {
int item;
if (q->front == -1) {
printf("Queue is empty");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
}
}
return item;
}
// 检查队列是否为空
int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}
// 创建一个图
struct Graph {
int numVertices;
int** adjMatrix;
};
// 创建一个新的图
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjMatrix = malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; i++) {
graph->adjMatrix[i] = malloc(vertices * sizeof(int));
}
// 初始化邻接矩阵
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++)
graph->adjMatrix[i][j] = 0;
}
return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
graph->adjMatrix[src][dest] = 1;
graph->adjMatrix[dest][src] = 1;
}
// 执行广度优先搜索
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();
int visited[graph->numVertices];
for (int i = 0; i < graph->numVertices; i++)
visited[i] = 0;
visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
// 遍历当前节点的所有邻居
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adjMatrix[currentVertex][i] == 1 && !visited[i]) {
enqueue(q, i);
visited[i] = 1;
}
}
}
}
// 主函数
int main() {
struct Graph* graph = createGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);
bfs(graph, 0);
return 0;
}
代码的主要步骤如下：
创建一个队列：在广度优先搜索中，我们使用队列来存储尚未访问过的节点。在这个示例中，我们使用一个结构体来表示队列，并实现了向队列中添加元素（enqueue）、从队列中移除元素（dequeue）以及检查队列是否为空（isEmpty）的操作。
创建一个图：我们使用一个结构体来表示图，并实现了创建新图（createGraph）和添加边（addEdge）的操作。在这个示例中，我们假设图是无向的，所以如果存在一条从节点A到节点B的边，那么就存在一条从节点B到节点A的边。
执行广度优先搜索：
- 首先，我们创建一个数组（visited）来记录哪些节点已经被访问过。然后，我们将起始节点添加到队列中，并标记为已访问。
- 然后，我们进入一个while循环，直到队列为空为止。在每次循环中，我们都从队列中移除一个节点，并访问这个节点。
- 对于每个被访问的节点，我们都遍历它的所有相邻节点，并检查它们是否已经被访问过。如果一个相邻节点尚未被访问过，那么就将它添加到队列中，并标记为已访问。
主函数：在主函数中，我们创建了一个新的图，并添加了一些边。然后，我们从节点0开始执行广度优先搜索。
