c语言中dfs和bfs
时间: 2024-06-13 10:04:53 浏览: 12
DFS和BFS是图遍历中两种常见的算法,它们在C语言中的实现如下:
DFS的实现:
```c
#define MAXN 1000
int head[MAXN], ver[MAXN], nxt[MAXN], tot = 1;
bool vis[MAXN];
void add(int x, int y) {
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void dfs(int x) {
vis[x] = true;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (!vis[y]) dfs(y);
}
}
```
BFS的实现:
```c
#define MAXN 1000
int head[MAXN], ver[MAXN], nxt[MAXN], tot = 1;
bool vis[MAXN];
void add(int x, int y) {
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void bfs(int x) {
queue<int> q;
q.push(x);
vis[x] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (!vis[y]) {
vis[y] = true;
q.push(y);
}
}
}
}
```
其中,DFS使用递归实现,BFS使用队列实现。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)