图是一种重要的数据结构，它由节点和边构成，常用于描述网络、社交关系、物流等复杂的实际问题。在图的应用中，图的遍历是一种基本的操作，它以某个节点为起点，按照一定的规则顺序地访问图中的所有节点。常用的图的遍历方式有深度优先搜索和广度优先搜索。
一、深度优先搜索
深度优先搜索（Depth First Search，DFS）是一种递归的搜索方式，它从某个节点出发，沿着一条路径深入图中，直到走到某个叶子节点或无法前进为止，然后回溯到上一个节点，继续沿着其他路径搜索。
1. 递归实现
深度优先搜索可以用递归的方式实现，核心代码如下：
```
void DFS(int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v);
}
}
}
```
其中，`visited`数组表示节点是否已被访问过，`adj`数组表示图中每个节点的邻接表。
2. 非递归实现
深度优先搜索还可以用非递归的方式实现，这种方式使用栈来存储访问顺序，核心代码如下：
```
void DFS(int u) {
stack
s.push(u);
visited[u] = true;
while (!s.empty()) {
int x = s.top();
s.pop();
for (int v : adj[x]) {
if (!visited[v]) {
s.push(v);
visited[v] = true;
}
}
}
}
```
其中，`stack`表示栈，每次取出栈顶元素，并将其未访问过的邻居节点压入栈中。
二、广度优先搜索
广度优先搜索（Breadth First Search，BFS）是一种迭代的搜索方式，它从某个节点出发，沿着一层层地扩展，直到遍历完整个图为止。
1. 实现方式
广度优先搜索可以用队列来实现，核心代码如下：
```
void BFS(int u) {
queue
q.push(u);
visited[u] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int v : adj[x]) {
if (!visited[v]) {
q.push(v);
visited[v] = true;
}
}
}
}
```
其中，`queue`表示队列，每次取出队首元素，并将其未访问过的邻居节点加入队列中。
2. 应用场景
广度优先搜索常用于解决最短路径问题，例如在地图上找到两个地点之间的最短路径，或者在社交网络中找到两个人之间的最短路径。
三、深度优先搜索与广度优先搜索的比较
深度优先搜索和广度优先搜索各有优缺点，应根据实际问题选择合适的算法。
1. 时间复杂度
深度优先搜索和广度优先搜索的时间复杂度都是$O(V+E)$，其中$V$是节点数，$E$是边数。但是深度优先搜索在搜索深度较大的图时可能会超时。
2. 空间复杂度
深度优先搜索的空间复杂度是$O(V)$，因为递归栈的深度最大为节点数。而广度优先搜索的空间复杂度是$O(V)$，因为需要存储每个节点的邻接表和访问状态。
3. 应用场景
深度优先搜索常用于求解图的连通性、拓扑排序、欧拉回路等问题，而广度优先搜索常用于求解最短路径、最小生成树等问题。
四、
