悠悠楠杉
网站页面
C++图的深度优先搜索（DFS）实现详解
11/23
![]()
cpp
void Graph::DFSUtil(int v, std::unordered_set
visited.insert(v);
std::cout << v << " ";
for (int neighbor : adjList[v]) {
if (visited.find(neighbor) == visited.end()) {
DFSUtil(neighbor, visited);
}
}
}
void Graph::DFSRecursive() {
std::unorderedset
for (int i = 0; i < vertices; ++i) {
if (visited.find(i) == visited.end()) {
DFSUtil(i, visited);
}
}
}
上述代码中，DFS_Recursive函数遍历所有顶点，确保图中存在多个连通分量时也能完整遍历。unordered_set用于记录已访问节点，避免重复访问和无限循环。
非递归实现DFS：栈的应用
虽然递归写法简洁，但在图规模较大时可能引发栈溢出。此时，使用显式栈进行迭代实现更为稳健。
cpp
void Graph::DFSIterative() {
std::unorderedset
std::stack
for (int i = 0; i < vertices; ++i) {
if (visited.find(i) != visited.end()) continue;
stk.push(i);
while (!stk.empty()) {
int curr = stk.top();
stk.pop();
if (visited.find(curr) != visited.end()) continue;
visited.insert(curr);
std::cout << curr << " ";
// 逆序压入邻接点，保证访问顺序与递归一致
std::vector<int> temp;
for (int neighbor : adjList[curr]) {
if (visited.find(neighbor) == visited.end()) {
temp.push_back(neighbor);
}
}
// 倒序入栈，模拟递归的深度优先
for (auto it = temp.rbegin(); it != temp.rend(); ++it) {
stk.push(*it);
}
}
}
}
这里使用std::stack模拟系统调用栈。注意邻接点需逆序压入，以保证访问顺序与递归版本一致。例如，若邻接点为{2,3,4}，应先压入4，再3，最后2，这样弹出时才是2、3、4的顺序。
完整测试示例
cpp
int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
std::cout << "递归DFS: ";
g.DFS_Recursive();
std::cout << std::endl;
std::cout << "迭代DFS: ";
g.DFS_Iterative();
std::cout << std::endl;
return 0;
}
输出结果为：
递归DFS: 0 1 3 4 2 5
迭代DFS: 0 1 3 4 2 5
两种实现方式结果一致，验证了正确性。
小结
DFS不仅是图遍历的工具，更是许多高级算法（如拓扑排序、强连通分量、桥与割点检测）的基础。在C++中，通过邻接表结合递归或栈，可以灵活高效地实现DFS。开发者应根据具体场景选择合适的方式：小规模图推荐递归以保持代码清晰；大规模图则建议使用迭代避免栈溢出。
掌握DFS的实现原理，有助于深入理解图论算法的本质，为后续学习更复杂的图算法打下坚实基础。
