答案：文章介绍了C++中使用邻接表和递归实现图的深度优先搜索（DFS）的方法，包括图的表示、DFS遍历逻辑、完整代码示例及注意事项。
深度优先搜索（DFS）是一种用于遍历或搜索图和树的算法。在C++中，可以通过递归或栈来实现图的DFS。下面介绍如何用邻接表表示图，并使用递归方式实现DFS遍历。
图的表示：邻接表
在C++中，通常使用vector
例如，一个包含n个节点的图：
vector添加边（假设是无向图）：
立即学习“C++免费学习笔记（深入）”；
graph[u].push_back(v);graph[v].push_back(u);
DFS递归实现
使用布尔数组visited[]记录节点是否被访问过，防止重复访问。
核心思路：从起始节点开始，标记为已访问，然后递归访问其所有未访问的邻接节点。
void dfs(int node, vectorvisited[node] = true;
cout
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
完整示例代码
以下是一个完整的C++程序，演示如何构建图并进行DFS遍历：
#include iostream>#include
using namespace std;
void dfs(int node, vector
visited[node] = true;
cout
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
int main() {
int n = 5; // 节点数
vector
// 添加边
graph[0].push_back(1);
graph[1].push_back(0);
graph[0].push_back(2);
graph[2].push_back(0);
graph[1].push_back(3);
graph[3].push_back(1);
graph[2].push_back(4);
graph[4].push_back(2);
vector
cout dfs(0, visited, graph);
cout
return 0;
}
注意事项与扩展
该实现适用于无向无权图。若图为有向图，添加边时只需单向添加。对于带权图，可使用vector
非递归版本可用stack模拟递归过程，避免深层递归导致的栈溢出。
基本上就这些，掌握邻接表和递归访问逻辑就能灵活应用DFS解决连通性、路径查找等问题。
