C++中实现图的深度优先遍历需用邻接表存储图，通过递归或栈进行节点访问并标记已访问节点避免重复。1. 使用vector表示邻接表；2. 递归实现DFS，从起始节点出发，访问未访问的邻接点并递归调用；3. 非递归实现使用stack模拟调用栈，压入起始节点后循环处理；4. 完整示例展示了从节点0开始的遍历过程，输出可能为0 1 3 2 4。若图非连通，需对每个未访问节点调用DFS。
在C++中实现图的深度优先遍历（DFS），核心是使用递归或栈来访问每个顶点，并避免重复访问。通常结合邻接表存储图结构，再通过标记数组记录已访问节点。
1. 图的表示：邻接表
C++中常用vector的数组或vector的vector来表示邻接表。例如，用vector假设图有n个节点，编号从0到n-1，可以这样初始化：
vector// 添加边 u - v
graph[u].push_back(v);
graph[v].push_back(u);
2. DFS递归实现
递归方式更直观，从起始节点开始，访问其所有未被访问的邻接点，并对每个邻接点递归调用DFS。需要一个布尔数组visited[]来记录访问状态：
vectorvoid dfs(int u) {
visited[u] = true;
cout
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v);
}
}
}
调用时指定起始节点，比如从节点0开始：
立即学习“C++免费学习笔记（深入）”；
dfs(0);3. 使用栈的非递归实现
若想避免递归带来的栈溢出风险（尤其在深层图中），可用STL中的stack模拟系统调用栈。步骤如下：
- 创建栈，压入起始节点
- 标记该节点为已访问
- 循环直到栈空：弹出一个节点并访问，将其所有未访问邻接点压栈并标记
void dfs_iterative(int start) {
stack
st.push(start);
vector
visited[start] = true;
while (!st.empty()) {
int u = st.top();
st.pop();
cout
for (int v : graph[u]) {
if (!visited[v]) {
st.push(v);
visited[v] = true;
}
}
}
}
4. 完整示例代码
以下是一个完整可运行的DFS示例（递归版）：include iostream>
include
using namespace std;
vector
vector
void dfs(int u) {
visited[u] = true;
cout
for (int v : graph[u]) {
if (!visited[v])
dfs(v);
}
}
int main() {
int n = 5; // 节点数
graph.resize(n);
visited.assign(n, false);
// 添加边
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);
cout
dfs(0);
return 0;
}
输出结果为：0 1 3 2 4（具体顺序可能因邻接点插入顺序而异）
基本上就这些。根据实际需求选择递归或迭代方式，注意处理连通性问题——如果是非连通图，需对每个未访问节点都调用一次DFS。
