深度优先遍历（Depth-First Search，简称DFS）是一种用于图遍历的基本算法。它通过深入地探索图中的路径，尽可能远地访问未被访问的节点。在本文中，我们将详细介绍深度优先遍历的概念、算法步骤。
概念
深度优先遍历的基本思想是从图的某一节点出发，沿着一条路径一直探索到达最远的节点，然后回退到前一个节点，继续探索下一条路径，直到所有的节点都被访问过。
当进行深度优先遍历（DFS）时，我们需要按照一定的步骤来遍历图中的节点。
选择起始节点：选择图中的一个起始节点作为遍历的起点。
标记已访问：将起始节点标记为已访问，并将其放入数据结构中，比如栈或递归调用。
探索相邻节点：从起始节点开始，探索与其相邻的节点。这是通过查找邻接表来实现的，邻接表存储了每个节点的相邻节点信息。
深入探索：选择一个相邻节点，标记为已访问，并将其放入数据结构中。然后，从这个相邻节点出发，继续探索其相邻节点，形成一个深入的路径。这一步是递归的核心。
回溯：当没有未访问的相邻节点时，回溯到上一个节点，继续探索其他未访问的相邻节点。这可以通过从数据结构中弹出节点来实现，或者从递归调用中返回。
重复步骤3至步骤5：重复以上步骤，直到所有节点都被访问。在遍历过程中，我们会在每一步都遵循深入路径并回溯的原则，直到没有未访问的节点为止。
通过以上步骤，DFS能够遍历图中的所有节点，同时可以生成一棵DFS树，它展示了从起始节点出发的探索路径。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
int V; // 节点数
vector<vector<int>> adj; // 邻接表
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void DFS(int start) {
vector<bool> visited(V, false); // 记录节点是否被访问过
stack<int> s; // 使用栈来辅助实现DFS
s.push(start);
while (!s.empty()) {
int current = s.top();
s.pop();
if (!visited[current]) {
cout << current << " ";
visited[current] = true;
}
// 将当前节点的未访问相邻节点入栈
for (int neighbor : adj[current]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
};
int main() {
Graph g(5); // 创建一个有5个节点的图
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
cout << "Depth First Traversal (starting from vertex 0): ";
g.DFS(0);
return 0;
}
所以我们步骤可以归结为
1. 选择起始节点
DFS的第一步是选择一个起始节点作为遍历的起点。这个起始节点是从图中的一个节点开始的位置，用来启动遍历过程。
2. 标记已访问
一旦选择了起始节点，我们将其标记为“已访问”，以确保我们不会重复访问同一个节点。
3. 探索相邻节点
从起始节点开始，我们探索与其相邻的节点。图可以用邻接表或邻接矩阵来表示。在深度优先遍历中，我们会按顺序检查一个节点的相邻节点，并选择一个尚未访问的相邻节点进行下一步探索。
4. 深入探索
一旦我们选择了一个未访问的相邻节点，我们会进一步深入探索该节点。这是通过递归或栈（堆栈）的方式实现的。我们将选定的相邻节点标记为已访问，并将其添加到遍历路径中，然后以该节点为起点继续探索其相邻节点。
5. 回溯
如果一个节点的所有相邻节点都已被访问，或者没有相邻节点，我们将回溯到之前的节点。这可以通过从栈中弹出节点或者从递归调用中返回来实现。回溯是深度优先遍历的一个关键特性，它允许我们在一个路径被完全探索后，返回到之前的节点继续探索其他路径。
6. 重复探索步骤
我们重复以上步骤，直到所有节点都被访问。在遍历的过程中，我们会遵循深入路径并回溯的原则，直到所有节点都被访问为止。
在DFS过程中，我们可以生成一棵DFS树，以起始节点为根，并且按照访问的次序来连接各个节点。这棵树能够展示起始节点出发的探索路径。
