【c/c++】深度DFS

一、DFS 核心原理：什么是深度优先搜索？

DFS 的本质是 **“一条路走到黑，走不通就回头”**，即优先沿着当前路径深入探索，直到无法前进时回溯到上一个分支点，选择新的路径继续搜索。

1.1 核心思想拆解

• 访问与标记：每访问一个节点，立即标记为 “已访问”，避免重复访问（死循环）。
• 递归 / 栈模拟：通过递归的 “函数调用栈” 或显式的 “栈数据结构” 保存当前路径的分支点，用于回溯。
• 回溯：当当前节点的所有邻接节点都已访问时，返回上一层节点，继续探索其他未访问的邻接节点。

1.2 直观示例：无向图的 DFS 遍历

假设有如下无向图（顶点 0-4）：

plaintext

0 connected to 1, 4
1 connected to 0, 2, 3, 4
2 connected to 1, 3
3 connected to 1, 2, 4
4 connected to 0, 1, 3

从顶点 0 开始的 DFS 遍历顺序可能为：0 → 1 → 2 → 3 → 4（递归版），具体过程如下：

1. 访问 0，标记为已访问；
2. 探索 0 的邻接节点 1（未访问），访问 1 并标记；
3. 探索 1 的邻接节点 2（未访问），访问 2 并标记；
4. 探索 2 的邻接节点 3（未访问），访问 3 并标记；
5. 探索 3 的邻接节点 4（未访问），访问 4 并标记；
6. 4 的邻接节点（0、1、3）均已访问，回溯到 3；
7. 3 的邻接节点均已访问，回溯到 2；
8. 2 的邻接节点均已访问，回溯到 1；
9. 1 的邻接节点均已访问，回溯到 0；
10. 0 的邻接节点均已访问，遍历结束。

二、图的存储：DFS 的 “地基”

DFS 依赖图的存储结构，邻接表是最常用的存储方式（空间效率高于邻接矩阵）。下面先明确 C 和 C++ 中邻接表的实现差异：

三、C 语言实现 DFS：手动管理内存的细节

C 语言没有 STL，需要手动实现邻接表、栈和内存释放，适合理解 DFS 的底层逻辑。

3.1 完整代码（递归 + 非递归）

c

运行

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 1. 邻接表节点结构体（存储单个邻接顶点）
typedef struct Node {int vertex;       // 邻接顶点的编号struct Node* next;// 指向下一个邻接节点的指针
} Node;// 2. 图结构体
typedef struct Graph {int numVertices;  // 顶点总数bool* visited;    // 标记顶点是否被访问（动态数组）Node** adjLists;  // 邻接表：指针数组，每个元素指向一个Node链表
} Graph;// 3. 工具函数1：创建单个邻接节点
Node* createNode(int v) {Node* newNode = (Node*)malloc(sizeof(Node)); // 分配节点内存if (newNode == NULL) { // 内存分配失败处理（易忽略细节）printf("Memory allocation failed for Node!\n");exit(1);}newNode->vertex = v;newNode->next = NULL;return newNode;
}// 4. 工具函数2：创建图
Graph* createGraph(int vertices) {Graph* graph = (Graph*)malloc(sizeof(Graph));if (graph == NULL) {printf("Memory allocation failed for Graph!\n");exit(1);}graph->numVertices = vertices;// 初始化邻接表（指针数组）graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));if (graph->adjLists == NULL) {printf("Memory allocation failed for adjLists!\n");free(graph); // 避免内存泄漏exit(1);}// 初始化访问标记数组graph->visited = (bool*)malloc(vertices * sizeof(bool));if (graph->visited == NULL) {printf("Memory allocation failed for visited!\n");free(graph->adjLists);free(graph);exit(1);}// 初始时，所有顶点均未访问，邻接表为空for (int i = 0; i < vertices; i++) {graph->adjLists[i] = NULL;graph->visited[i] = false;}return graph;
}// 5. 工具函数3：添加无向边（src ↔ dest）
void addEdge(Graph* graph, int src, int dest) {// 1. 向src的邻接表添加destNode* newNode = createNode(dest);newNode->next = graph->adjLists[src]; // 头插法（效率高）graph->adjLists[src] = newNode;// 2. 向dest的邻接表添加src（无向图对称）newNode = createNode(src);newNode->next = graph->adjLists[dest];graph->adjLists[dest] = newNode;
}// 6. 递归实现DFS（核心）
void dfsRecursive(Graph* graph, int vertex) {// 步骤1：标记当前顶点为已访问graph->visited[vertex] = true;printf("%d ", vertex); // 访问操作（可替换为其他逻辑）// 步骤2：遍历当前顶点的所有邻接节点Node* temp = graph->adjLists[vertex]; // 指向邻接表的头节点while (temp != NULL) {int neighbor = temp->vertex;// 步骤3：若邻接节点未访问，递归调用if (!graph->visited[neighbor]) {dfsRecursive(graph, neighbor);}temp = temp->next; // 移动到下一个邻接节点}
}// 7. 非递归实现DFS（用栈模拟递归，核心）
void dfsIterative(Graph* graph, int startVertex) {// 步骤1：重置访问标记（避免受之前递归调用的影响）for (int i = 0; i < graph->numVertices; i++) {graph->visited[i] = false;}// 步骤2：创建栈（动态数组模拟，top=-1表示空栈）int* stack = (int*)malloc(graph->numVertices * sizeof(int));if (stack == NULL) {printf("Memory allocation failed for stack!\n");return;}int top = -1;// 步骤3：起始顶点入栈并标记stack[++top] = startVertex;graph->visited[startVertex] = true;printf("Iterative DFS: ");// 步骤4：栈非空则循环while (top != -1) {// 步骤5：弹出栈顶顶点并访问int current = stack[top--];printf("%d ", current);// 步骤6：邻接节点逆序入栈（保证与递归顺序一致）Node* temp = graph->adjLists[current];// 先收集所有未访问的邻接节点int* neighbors = (int*)malloc(graph->numVertices * sizeof(int));int count = 0;while (temp != NULL) {int neighbor = temp->vertex;if (!graph->visited[neighbor]) {neighbors[count++] = neighbor;graph->visited[neighbor] = true; // 入栈即标记，避免重复入栈}temp = temp->next;}// 逆序入栈（因为头插法的邻接表是逆序的）for (int i = count - 1; i >= 0; i--) {stack[++top] = neighbors[i];}free(neighbors); // 释放临时数组}printf("\n");free(stack); // 释放栈内存
}// 8. 工具函数4：释放图的所有内存（避免内存泄漏）
void freeGraph(Graph* graph) {// 1. 释放每个邻接表的链表节点for (int i = 0; i < graph->numVertices; i++) {Node* temp = graph->adjLists[i];while (temp != NULL) {Node* prev = temp;temp = temp->next;free(prev); // 释放单个节点}}// 2. 释放邻接表数组、访问标记数组、图本身free(graph->adjLists);free(graph->visited);free(graph);
}// 测试主函数
int main() {// 1. 创建含5个顶点的图Graph* graph = createGraph(5);// 2. 添加边addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 3. 递归DFSprintf("Recursive DFS: ");dfsRecursive(graph, 0);printf("\n");// 4. 非递归DFSdfsIterative(graph, 0);// 5. 释放内存freeGraph(graph);return 0;
}

3.2 关键细节解析

1. 内存管理：C 语言中必须手动释放malloc分配的内存（如freeGraph函数），否则会导致内存泄漏。
2. 邻接表插入：使用头插法（newNode->next = adjLists[src]; adjLists[src] = newNode），时间复杂度 O (1)。
3. 非递归的栈操作：
   • 入栈时立即标记为 “已访问”，避免同一节点多次入栈；
   • 邻接节点需逆序入栈，因为头插法的邻接表是 “逆序存储” 的（如 0 的邻接表是4→1，逆序后入栈为1→4，保证遍历顺序与递归一致）。

四、C++ 实现 DFS：STL 简化开发

C++ 的vector（动态数组）和stack（栈容器）可替代手动内存管理，代码更简洁，且支持更多高级功能（如路径查找）。

4.1 完整代码（递归 + 非递归 + 路径查找）

cpp

运行

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm> // 用于fill函数
using namespace std;// 图类（封装性更好）
class Graph {
private:int numVertices;       // 顶点总数vector<vector<int>> adjList; // 邻接表：vector的vectorvector<bool> visited;  // 访问标记：vector自动管理内存// 递归DFS辅助函数（私有，对外隐藏实现）void dfsRecursiveUtil(int vertex) {// 1. 标记并访问当前顶点visited[vertex] = true;cout << vertex << " ";// 2. 遍历所有未访问的邻接顶点（范围for循环简化代码）for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {dfsRecursiveUtil(neighbor);}}}// 路径查找辅助函数（回溯思想）bool findPathUtil(int curr, int target, vector<int>& path) {// 1. 标记当前顶点并加入路径visited[curr] = true;path.push_back(curr);// 2. 若找到目标，返回trueif (curr == target) {return true;}// 3. 递归探索邻接顶点for (int neighbor : adjList[curr]) {if (!visited[neighbor]) {if (findPathUtil(neighbor, target, path)) {return true; // 找到路径后直接返回，不继续探索}}}// 4. 回溯：当前顶点不在路径上，移除并返回falsepath.pop_back();return false;}public:// 构造函数：初始化顶点数、邻接表、访问标记Graph(int vertices) : numVertices(vertices),adjList(vertices), // 初始化adjList为含vertices个空vectorvisited(vertices, false) {} // 初始均为false// 1. 添加无向边void addEdge(int src, int dest) {adjList[src].push_back(dest);adjList[dest].push_back(src);}// 2. 递归DFS入口（公开接口，重置访问标记）void dfsRecursive(int start) {fill(visited.begin(), visited.end(), false); // 重置标记cout << "Recursive DFS: ";dfsRecursiveUtil(start);cout << endl;}// 3. 非递归DFS（用STL stack）void dfsIterative(int start) {fill(visited.begin(), visited.end(), false);stack<int> st; // STL stack，自动管理内存// 起始顶点入栈并标记st.push(start);visited[start] = true;cout << "Iterative DFS: ";while (!st.empty()) {// 弹出栈顶并访问int curr = st.top();st.pop();cout << curr << " ";// 邻接顶点逆序入栈（保证顺序一致）// rbegin()/rend()：反向迭代器，从尾到头遍历for (auto it = adjList[curr].rbegin(); it != adjList[curr].rend(); ++it) {int neighbor = *it;if (!visited[neighbor]) {visited[neighbor] = true;st.push(neighbor);}}}cout << endl;}// 4. 高级功能：查找从start到target的路径（回溯+DFS）bool findPath(int start, int target, vector<int>& path) {fill(visited.begin(), visited.end(), false);path.clear(); // 清空传入的路径容器return findPathUtil(start, target, path);}
};// 测试主函数
int main() {// 1. 创建含5个顶点的图Graph graph(5);// 2. 添加边graph.addEdge(0, 1);graph.addEdge(0, 4);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(1, 4);graph.addEdge(2, 3);graph.addEdge(3, 4);// 3. 递归DFSgraph.dfsRecursive(0);// 4. 非递归DFSgraph.dfsIterative(0);// 5. 查找路径（0→3）vector<int> path;if (graph.findPath(0, 3, path)) {cout << "Path from 0 to 3: ";for (int v : path) {cout << v << " ";}cout << endl;} else {cout << "No path from 0 to 3!" << endl;}return 0;
}

4.2 C++ 实现的核心优势

1. STL 容器简化代码：
   • vector<vector<int>> adjList：自动扩容，无需手动管理邻接表内存；
   • stack<int> st：封装了栈的 push/pop/top 操作，无需手动实现数组栈。
2. 范围 for 循环：for (int neighbor : adjList[vertex]) 替代 C 语言的指针遍历，代码更易读。
3. 封装性：将邻接表、访问标记和 DFS 逻辑封装在Graph类