dfs.rar_dfs_in

深度优先搜索（DFS，Depth-First Search）是一种用于遍历或搜索树或图的算法，它从根节点开始，沿着某一分支深入到尽可能深的层次，如果此路径无法到达目标，就回溯到上一个节点，尝试另一条分支。在C++中实现DFS，通常会用到递归或者栈数据结构。 DFS的基本思想： 1. 从根节点开始，将其标记为已访问。 2. 访问当前节点的一个未被访问的邻接节点，将其作为新的当前节点，并重复步骤1。 3. 如果所有邻接节点都被访问过，就回溯到上一节点，选择下一个未访问的邻接节点继续搜索。 4. 这个过程持续到所有可达节点都被访问为止。 C++中实现DFS的方法通常有两种：递归和非递归（使用栈）。 **递归实现DFS：** 递归是DFS最直观的实现方式，代码简洁易懂。在C++中，我们可以定义一个函数，参数为当前节点，然后在函数内部遍历其邻接节点并进行递归调用。这里假设我们有一个邻接列表表示的图。 ```cpp #include <vector> using namespace std; // 定义图的节点 struct Node { int id; vector<Node*> neighbors; }; // 递归DFS void dfs(Node* node, vector<bool>& visited) { visited[node->id] = true; cout << "Visited node " << node->id << endl; for (Node* neighbor : node->neighbors) { if (!visited[neighbor->id]) { dfs(neighbor, visited); } } } ``` **非递归（栈）实现DFS：** 对于大型图，递归可能导致栈溢出，这时可以使用非递归方式，通过手动管理栈来实现DFS。 ```cpp #include <stack> using namespace std; void dfs(Node* node, vector<bool>& visited, stack<Node*>& s) { visited[node->id] = true; cout << "Visited node " << node->id << endl; s.push(node); while (!s.empty()) { Node* current = s.top(); s.pop(); for (Node* neighbor : current->neighbors) { if (!visited[neighbor->id]) { visited[neighbor->id] = true; cout << "Visited node " << neighbor->id << endl; s.push(neighbor); } } } } ``` 在上述两种方法中，都需要一个`visited`数组来记录每个节点是否已被访问，避免重复访问。在实际应用中，可能会根据需求进行优化，例如，使用边集表示图、增加数据存储、处理环等问题。 总结，深度优先搜索（DFS）是图论和算法中的重要概念，C++提供了多种实现方式，包括递归和非递归。理解DFS的工作原理和C++实现，有助于解决各种图遍历问题，如拓扑排序、寻找强连通分量、判断有向图是否存在环等。在实际编程中，我们需要根据具体场景选择合适的实现方式。