广度优先遍历c语言 递归
时间: 2023-09-25 20:15:30 浏览: 50
广度优先遍历(BFS)通常是使用队列进行非递归实现的,但是也可以使用递归进行实现。下面给出使用递归实现BFS的C语言代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 100
int graph[MAX_N][MAX_N]; // 邻接矩阵表示的图
bool visited[MAX_N]; // 记录节点是否被访问
void bfs(int cur, int n) {
if (visited[cur]) return; // 当前节点已经被访问过,直接返回
visited[cur] = true; // 标记当前节点已经被访问
printf("%d ", cur); // 输出当前节点
int i;
for (i = 0; i < n; i++) { // 遍历当前节点的所有邻居
if (graph[cur][i] && !visited[i]) { // 如果当前节点和邻居之间有边并且邻居没有被访问过
bfs(i, n); // 递归访问邻居节点
}
}
}
int main() {
int n, m; // n个节点,m条边
scanf("%d%d", &n, &m);
int i, u, v;
for (i = 0; i < m; i++) { // 读入图的边
scanf("%d%d", &u, &v);
graph[u][v] = graph[v][u] = 1; // 无向图,所以要将双向边都设置为1
}
bfs(0, n); // 从节点0开始进行BFS遍历
return 0;
}
```
这里使用一个 `visited` 数组来记录每个节点是否被访问过,如果当前节点已经被访问过,则直接返回,否则标记当前节点已经被访问,输出当前节点,并递归访问当前节点的所有邻居节点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![](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)