广度优先搜索c代码
时间: 2023-06-21 18:19:25 浏览: 47
以下是广度优先搜索的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100 //定义队列的最大长度
//定义队列结构体
typedef struct {
int data[MAX_QUEUE_SIZE];
int front, rear;
} Queue;
//初始化队列
void initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}
//判断队列是否为空
int isQueueEmpty(Queue *q) {
return q->front == q->rear;
}
//判断队列是否已满
int isQueueFull(Queue *q) {
return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}
//向队列中添加元素
void enqueue(Queue *q, int x) {
if (isQueueFull(q)) {
printf("Queue is full, can not enqueue.\n");
exit(-1);
}
q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
}
//从队列中取出元素
int dequeue(Queue *q) {
if (isQueueEmpty(q)) {
printf("Queue is empty, can not dequeue.\n");
exit(-1);
}
int x = q->data[q->front];
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return x;
}
//广度优先搜索函数
void bfs(int n, int m, int maze[][m], int start_x, int start_y) {
int visited[n][m]; //记录每个点是否被访问过
int dx[4] = {-1, 0, 1, 0}; //定义四个方向的x偏移量
int dy[4] = {0, 1, 0, -1}; //定义四个方向的y偏移量
Queue q;
initQueue(&q); //初始化队列
visited[start_x][start_y] = 1; //标记起点已被访问
enqueue(&q, start_x * m + start_y); //将起点加入队列
while (!isQueueEmpty(&q)) { //当队列不为空时进行搜索
int cur = dequeue(&q); //取出队头元素
int x = cur / m, y = cur % m; //计算当前位置的坐标
printf("(%d, %d)\n", x, y); //输出当前位置的坐标
for (int i = 0; i < 4; i++) { //遍历四个方向
int nx = x + dx[i], ny = y + dy[i]; //计算新位置的坐标
if (nx >= 0 && nx < n && ny >= 0 && ny < m && //判断新位置是否越界
maze[nx][ny] == 0 && !visited[nx][ny]) { //判断新位置是否可行且未被访问
visited[nx][ny] = 1; //标记新位置已被访问
enqueue(&q, nx * m + ny); //将新位置加入队列
}
}
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
int maze[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &maze[i][j]);
}
}
bfs(n, m, maze, 0, 0); //从起点(0, 0)开始搜索
return 0;
}
```
这个代码实现了一个简单的迷宫问题的搜索,输出了搜索过程中经过的位置的坐标。你可以根据需要修改代码中的数据结构和搜索逻辑,以适应不同的应用场景。