队列图的广度优先遍历c
时间: 2023-06-21 08:22:58 浏览: 62
好的,以下是队列实现的广度优先遍历的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义队列结构体
struct queue {
int data;
struct queue* next;
};
// 全局变量,头结点、尾结点
struct queue* front = NULL;
struct queue* rear = NULL;
// 入队操作
void enqueue(int data) {
struct queue* temp = (struct queue*)malloc(sizeof(struct queue));
temp->data = data;
temp->next = NULL;
if (front == NULL && rear == NULL) {
front = rear = temp;
return;
}
rear->next = temp;
rear = temp;
}
// 出队操作
void dequeue() {
struct queue* temp = front;
if (front == NULL) {
printf("队列已空\n");
return;
}
if (front == rear) {
front = rear = NULL;
} else {
front = front->next;
}
free(temp);
}
// 判断队列是否为空
int is_empty() {
if (front == NULL) {
return 1;
} else {
return 0;
}
}
// 广度优先遍历
void bfs(int G[][7], int start, int n) {
int i = start, j;
int visited[7] = { 0 };
printf("%d ", i);
visited[i] = 1;
enqueue(i);
while (!is_empty()) {
i = front->data;
dequeue();
for (j = 1; j < n; j++) {
if (G[i][j] == 1 && visited[j] == 0) {
printf("%d ", j);
visited[j] = 1;
enqueue(j);
}
}
}
}
int main() {
// 定义邻接矩阵
int G[7][7] = {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 1, 0, 0, 0},
{0, 1, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0}
};
bfs(G, 1, 7);
return 0;
}
```
这里以一个邻接矩阵图为例进行广度优先遍历,如果需要遍历其他类型的图,只需要修改邻接矩阵的表示方法即可。