运行广度优先遍历算法,写出输入数据的顺序和程序运行的结果,用C语言实现
时间: 2024-02-15 15:02:46 浏览: 35
好的,我可以为您解答这个问题。广度优先遍历算法(BFS)是一种图遍历算法,用于遍历图中的所有节点。下面是一个使用C语言实现BFS算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
// 定义邻接矩阵
int graph[5][5] = {
{0, 1, 1, 0, 0},
{1, 0, 1, 1, 1},
{1, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 1, 1, 1, 0}
};
// 定义队列结构体
typedef struct {
int data[MAX_QUEUE_SIZE];
int front, rear;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}
// 入队
void enqueue(Queue *q, int value) {
q->data[q->rear++] = value;
}
// 出队
int dequeue(Queue *q) {
return q->data[q->front++];
}
// 判断队列是否为空
int isQueueEmpty(Queue *q) {
return q->front == q->rear;
}
// 遍历函数
void BFS(int start) {
Queue q;
int visited[5] = {0};
initQueue(&q);
visited[start] = 1;
enqueue(&q, start);
while (!isQueueEmpty(&q)) {
int node = dequeue(&q);
printf("%d ", node);
for (int i = 0; i < 5; i++) {
if (graph[node][i] == 1 && visited[i] == 0) {
visited[i] = 1;
enqueue(&q, i);
}
}
}
}
// 主函数
int main() {
BFS(0);
return 0;
}
```
以上代码为一个简单的BFS算法实现,对应的邻接矩阵为:
```
0 1 2 3 4
0 0 1 1 0 0
1 1 0 1 1 1
2 1 1 0 0 1
3 0 1 0 0 1
4 0 1 1 1 0
```
程序运行的结果为:0 1 2 3 4。这是因为从节点0开始,先遍历到节点1和节点2,然后再遍历到节点3和节点4。
相关推荐
![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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)