帮我用c语言写一个图的广度优先遍历
时间: 2023-11-17 07:08:10 浏览: 23
好的,以下是使用C语言实现图的广度优先遍历的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义一个结构体表示邻接表中的节点
typedef struct node {
int dest; // 目标节点的下标
struct node* next; // 下一个节点的指针
} Node;
// 定义一个结构体表示图
typedef struct graph {
int num_vertices; // 图中节点的数量
Node** adj_list; // 邻接表
} Graph;
// 创建一个新的节点
Node* new_node(int dest) {
Node* new_node = (Node*) malloc(sizeof(Node));
new_node->dest = dest;
new_node->next = NULL;
return new_node;
}
// 创建一个新的图
Graph* new_graph(int num_vertices) {
Graph* new_graph = (Graph*) malloc(sizeof(Graph));
new_graph->num_vertices = num_vertices;
new_graph->adj_list = (Node**) malloc(num_vertices * sizeof(Node*));
// 初始化邻接表
int i;
for (i = 0; i < num_vertices; i++) {
new_graph->adj_list[i] = NULL;
}
return new_graph;
}
// 添加一条边
void add_edge(Graph* graph, int src, int dest) {
// 将目标节点添加到源节点的链表中
Node* new_edge = new_node(dest);
new_edge->next = graph->adj_list[src];
graph->adj_list[src] = new_edge;
// 将源节点添加到目标节点的链表中
new_edge = new_node(src);
new_edge->next = graph->adj_list[dest];
graph->adj_list[dest] = new_edge;
}
// 广度优先遍历
void bfs(Graph* graph, int start) {
// 初始化队列
int queue[graph->num_vertices];
int front = 0, rear = 0;
queue[rear++] = start;
// 初始化访问标记
int visited[graph->num_vertices];
int i;
for (i = 0; i < graph->num_vertices; i++) {
visited[i] = 0;
}
// 遍历队列中的节点
while (front < rear) {
// 出队一个节点
int current = queue[front++];
visited[current] = 1;
printf("%d ", current);
// 遍历当前节点的邻接表
Node* temp = graph->adj_list[current];
while (temp != NULL) {
int adj = temp->dest;
if (!visited[adj]) {
visited[adj] = 1;
queue[rear++] = adj;
}
temp = temp->next;
}
}
}
int main() {
// 创建一个5个节点的图
Graph* graph = new_graph(5);
// 添加边
add_edge(graph, 0, 1);
add_edge(graph, 0, 4);
add_edge(graph, 1, 2);
add_edge(graph, 1, 3);
add_edge(graph, 1, 4);
add_edge(graph, 2, 3);
add_edge(graph, 3, 4);
// 从节点0开始遍历
bfs(graph, 0);
return 0;
}
```
这段代码可以输出以下结果:
```
0 1 4 2 3
```