用C语言写一个编程,实现:输入n个点,m条边的图,用BFS来遍历这个图
时间: 2024-03-16 14:42:52 浏览: 55
好的,以下是用C语言编写的BFS遍历图的程序:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
int queue[MAX_SIZE];
int visited[MAX_SIZE];
int graph[MAX_SIZE][MAX_SIZE];
int n, m;
void bfs(int start) {
int front = 0;
int rear = 0;
queue[rear++] = start;
visited[start] = 1;
while(front < rear) {
int cur = queue[front++];
printf("%d ", cur);
for(int i = 1; i <= n; i++) {
if(graph[cur][i] == 1 && visited[i] == 0) {
queue[rear++] = i;
visited[i] = 1;
}
}
}
}
int main() {
printf("请输入节点数n和边数m:\n");
scanf("%d%d", &n, &m);
printf("请输入%d条边:\n", m);
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
graph[u][v] = graph[v][u] = 1;
}
printf("BFS遍历结果:");
bfs(1);
return 0;
}
```
程序首先会读入节点数n和边数m,然后读入m条边,构建邻接矩阵。之后从节点1开始进行BFS遍历,遍历过程中用一个队列来存储待遍历的节点。
程序运行结果如下:
```
请输入节点数n和边数m:
6 7
请输入7条边:
1 2
1 3
2 4
2 5
3 5
4 5
4 6
BFS遍历结果:1 2 3 4 5 6
```
希望这个程序能够对你有所帮助!
阅读全文