图的深度优先搜索从起始顶点开始沿路径深入访问，使用邻接表和递归或栈实现；需标记访问状态避免重复，对不连通图需多次调用DFS以遍历所有节点。
图的深度优先搜索（DFS）是一种用于遍历或搜索图中节点的算法。它从一个起始顶点开始，沿着一条路径尽可能深入地访问未访问过的邻接点，直到无法继续前进，再回溯并尝试其他分支。C++ 中可以通过邻接表或邻接矩阵结合递归或栈来实现 DFS。
使用邻接表和递归实现 DFS
邻接表是表示图的一种高效方式，尤其适用于稀疏图。使用 vector<vector<int>> 存储每个顶点的邻接点，配合布尔数组记录访问状态。
步骤说明：
- 创建图的邻接表结构
- 维护一个 visited 数组防止重复访问
- 从指定起点开始递归访问所有未访问的邻接点
代码示例：
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V; // 顶点数量
vector<vector<int>> adj; // 邻接表
void dfsUtil(int v, vector<bool>& visted) {
visted[v] = true;
cout << v << " ";
for (int neighbor : adj[v]) {
if (!visted[neighbor]) {
dfsUtil(neighbor, visted);
}
}
}
public:
Graph(int V) {
this->V = V;
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);
dfsUtil(start, visited);
}
};
// 使用示例
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
cout << "从顶点 0 开始的 DFS 遍历: ";
g.dfs(0);
return 0;
}
使用栈实现非递归 DFS
递归本质是系统调用栈，也可以手动使用 stack 实现 DFS，避免递归带来的栈溢出风险，尤其在图较大时更安全。
核心思路：
- 用 stack 存储待访问的顶点
- 每次取出栈顶，标记为已访问并输出
- 将其未访问的邻接点压入栈
非递归实现代码片段：
void dfsIterative(int start) {
vector<bool> visited(V, false);
stack<int> stk;
stk.push(start);
while (!stk.empty()) {
int curr = stk.top();
stk.pop();
if (visited[curr]) continue;
visited[curr] = true;
cout << curr << " ";
// 逆序压入邻接点，保证顺序一致（可选）
for (auto it = adj[curr].rbegin(); it != adj[curr].rend(); ++it) {
if (!visited[*it]) {
stk.push(*it);
}
}
}
}
注意事项与优化建议
DFS 实现时需注意以下几点：
- 确保图的索引从 0 或 1 开始统一，避免越界
- 无向图添加边时要双向插入
- 访问数组大小初始化为 V，并初始为 false
- 若图不连通，需对每个未访问顶点调用 DFS 才能遍历全图
基本上就这些。根据实际需求选择递归或迭代方式，邻接表适合大多数场景。理解状态标记和回溯机制是掌握 DFS 的关键。
