基于队列实现bfs算法c语言
时间: 2024-05-07 13:20:33 浏览: 18
以下是基于队列实现BFS算法的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 1000
typedef struct {
int x;
int y;
} Point;
typedef struct {
Point data[MAX_QUEUE_SIZE];
int front;
int rear;
} Queue;
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
int isEmpty(Queue *q) {
return (q->front == -1 && q->rear == -1);
}
int isFull(Queue *q) {
return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}
void enqueue(Queue *q, Point p) {
if (isFull(q)) {
printf("Error: Queue is full!\n");
exit(EXIT_FAILURE);
}
if (isEmpty(q)) {
q->front = q->rear = 0;
} else {
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
}
q->data[q->rear] = p;
}
Point dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Error: Queue is empty!\n");
exit(EXIT_FAILURE);
}
Point p = q->data[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
}
return p;
}
void bfs(int **graph, int n, int start) {
Queue q;
initQueue(&q);
int visited[n];
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
Point p = {start, 0};
visited[start] = 1;
enqueue(&q, p);
while (!isEmpty(&q)) {
Point curr = dequeue(&q);
printf("%d ", curr.x);
for (int i = 0; i < n; i++) {
if (graph[curr.x][i] == 1 && visited[i] == 0) {
Point next = {i, curr.y + 1};
visited[i] = 1;
enqueue(&q, next);
}
}
}
}
int main() {
int n = 8;
int **graph = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
graph[i] = (int *)malloc(n * sizeof(int));
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = 0;
}
}
graph[0][1] = graph[1][0] = 1;
graph[0][2] = graph[2][0] = 1;
graph[1][3] = graph[3][1] = 1;
graph[1][4] = graph[4][1] = 1;
graph[2][5] = graph[5][2] = 1;
graph[2][6] = graph[6][2] = 1;
graph[4][7] = graph[7][4] = 1;
bfs(graph, n, 0);
return 0;
}
```
该代码是一个简单的BFS实现,图的邻接矩阵存储在一个二维数组中,函数 `bfs` 接受该二维数组、顶点数和起点编号作为参数,并输出遍历结果。在函数中使用了一个队列来辅助实现BFS。具体实现可参考代码注释。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)