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