深度遍历和广度遍历例题
在计算机科学中，遍历是指按照某种规则访问数据结构中的每个节点。深度遍历和广度遍历是两种常见的遍历方式。本文将从定义、实现、应用等多个角度来探讨深度遍历和广度遍历，并通过例题来进一步理解这两种遍历方式。
一、定义
深度遍历（DFS）和广度遍历（BFS）都是图遍历算法，而图是由节点（或顶点）和边组成的抽象模型。深度遍历是沿着图的深度遍历所有节点，一次访问一个分支，并尽可能深地搜索每个节点。广度遍历则是依次访问节点的所有邻居，然后继续从这些邻居开始访问它们的邻居，逐层扩展，直到访问所有节点。
二、实现
DFS和BFS都可以用递归或迭代实现。对于DFS而言，递归实现较为简单，一个基本的DFS程序框架如下：
```
// 递归版深度优先遍历
void DFS(int node) {
visited[node] = true;
for (auto next : graph[node]) {
if (!visited[next])
DFS(next);
}
}
```
而BFS则需要借助队列实现，一个基本的BFS程序框架如下：
```
// 队列版广度优先遍历
void BFS(int start) {
queue
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
for (auto next : graph[node]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
}
```
需要注意的是，DFS和BFS一般需要借助visited数组来记录访问过的节点，防止节点被重复访问。
三、应用
深度遍历和广度遍历在图的遍历中具有广泛的应用，比如求解最短路、连通性问题、拓扑排序等。以下是一个基于DFS求解连通性问题的例题：
给定一个包含n个节点和m条边的无向图，判断其中是否存在环。
根据无向图中是否存在环的定义，我们可以通过判断每个节点的邻居是否已经被访问过来判断此题的答案。如果某个邻居节点已经访问过，并且不是当前节点的父节点，那么就存在环。一个基本的DFS实现如下：
```
bool hasCycle(int node, int parent) {
visited[node] = true;
for (auto next : graph[node]) {
if (!visited[next])
if (hasCycle(next, node))
return true;
else if (next != parent)
return true;
}
return false;
}
```
值得注意的是，如果图不连通，需要对每个节点都进行判断。
