用c语言写一个对邻接表表示的无向图进行广度优先遍历
时间: 2023-07-14 13:12:35 浏览: 102
无向图的邻接表构建和遍历
5星 · 资源好评率100%
好的,下面是示例代码:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXV 1000 // 最大节点数
typedef struct node{
int v;
struct node *next;
}node;
node *adj[MAXV]; // 邻接表
int visited[MAXV]; // 记录节点是否被访问过
int queue[MAXV]; // 队列
int front = 0, rear = 0; // 队列的头和尾
void add_edge(int u, int v){
// 添加边
node *p = (node*)malloc(sizeof(node));
p->v = v;
p->next = adj[u];
adj[u] = p;
p = (node*)malloc(sizeof(node));
p->v = u;
p->next = adj[v];
adj[v] = p;
}
void bfs(int start){
// 广度优先遍历
queue[rear++] = start;
visited[start] = 1;
while(front < rear){
int u = queue[front++];
printf("%d ", u);
node *p = adj[u];
while(p != NULL){
int v = p->v;
if(!visited[v]){
queue[rear++] = v;
visited[v] = 1;
}
p = p->next;
}
}
}
int main(){
int V, E;
scanf("%d%d", &V, &E); // 输入节点数和边数
for(int i=0; i<E; i++){
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
}
bfs(0); // 从节点0开始遍历
return 0;
}
```
代码中使用了邻接表来表示无向图,并且使用了队列来实现广度优先遍历。在遍历的过程中,使用visited数组记录节点是否被访问过,避免重复遍历。
阅读全文