C++如何实现深度优先搜索DFS_C++递归遍历图节点教程【逻辑】

尼克

发布时间：2026-02-08 00:37:35

679人浏览过

来源于php中文网

原创

DFS在C++中需靠显式状态控制，邻接表递归必须传节点索引并用引用visited防重入；手动栈需压栈前标记访问；树可省visited，图必须用；慎用vector。

c++如何实现深度优先搜索dfs_c++递归遍历图节点教程【逻辑】

DFS 在 C++ 中不是靠“教程逻辑”驱动的，而是靠明确的状态控制和递归终止条件；写错往往是因为没管住访问标记或忽略图的存储结构差异。

用 `vector>` 存邻接表时怎么写 DFS 递归

这是最常用也最容易出错的场景：邻接表本身不带节点 ID，递归函数必须显式传入当前节点索引，并用外部 visited 数组防重入。

visited 必须是全局或引用传入，不能在每次递归里新建
遍历邻居要写成 for (int neighbor : graph[u])，别手抖写成 for (int i = 0; i
递归前必须先设 visited[u] = true，否则可能重复进入同一节点

void dfs(int u, const vector>& graph, vector& visited) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v, graph, visited);
        }
    }
}

遇到 `std::stack` 手动模拟栈时要注意什么

递归本质是系统栈，手动栈容易漏掉“已访问但未处理完”的状态。非递归 DFS 不等于把递归改成 while + stack 就完事。

压栈前就要标记 visited[u] = true，否则同一节点可能被多次压入
出栈后才处理该节点（比如输出、收集），但邻居的访问判断仍依赖 visited
如果要还原路径或记录深度，得额外存 pair（节点+深度），不能只压节点

DFS 遍历树和遍历一般图的区别在哪

树无环、有向且连通，所以不需要 visited 数组也能跑通；但只要图里存在环或多个连通分量，不加访问控制就会无限递归或漏节点。

医真AI+开放平台

医真AI+ 医学AI开放平台

下载

立即学习“C++免费学习笔记（深入）”；

树：可直接用 dfs(root)，子节点天然不回指父节点
一般图：必须用 visited，且初始化要覆盖全部可能节点编号（比如 0~n-1）
无向图边存两次，graph[u].push_back(v) 和 graph[v].push_back(u) 缺一不可

为什么用 `vector` 做访问数组有时会慢还出错

vector 是特化模板，内部按位存储，operator[] 返回的是代理对象而非引用，可能导致 visited[i] = true 失效。

调试时发现某节点反复进入？优先换成 vector 或 vector
性能敏感场景（比如百万节点），位操作反而因 cache 不友好变慢
Clang/GCC 对 vector 的迭代器行为也有差异，跨平台项目尽量避开

真正卡住人的从来不是“怎么写递归”，而是没想清楚图的输入形式、节点编号范围、是否带权、有向还是无向——这些决定了 visited 数组大小、邻接表构造方式、以及要不要加额外状态字段。

C++如何实现二叉树的层序遍历_C++使用队列实现树的广度优先【算法】

C++中bitset怎么用_C++位运算及位图容器使用指南【位操作】

C++如何实现自定义内存对齐的数组_C++使用alignas控制内存布局【底层】

C++中lock_guard怎么用_C++多线程自动加锁解锁机制【并发】

C++中std::stacktrace怎么打印崩溃堆栈_C++23原生回溯功能教程【诊断】

相关标签:

栈 ai c++ 递归函数区别为什么 for while 递归 bool char int 栈 operator 对象

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++中try_lock怎么使用_c++多线程锁优化【进阶】下一篇：暂无

作者最新文章

千牛如何设置限时打折活动_千牛特价工具配置方法【全攻略】

2026-02-06 12:31

百度贴吧怎么修改头像百度贴吧头像上传失败怎么办【常见问题】

2026-02-06 12:33

PPT如何快速调出开发工具 PPT加载项与控件启用方法

2026-02-06 12:43

UC浏览器如何开启手势操作_UC浏览器快捷手势设置【指南】

2026-02-06 12:43

PPT动画大师之路 PPT平滑切换零基础【精通】

2026-02-06 12:52

C++如何检测程序是否重复启动_C++利用互斥量创建单实例程序【方案】

2026-02-06 12:59

Excel怎么批量插入图片 Excel图片一键对齐单元格【插件】

2026-02-06 13:10

Sublime如何一键对齐冒号后面的内容_Sublime对齐插件进阶用法【技巧】

2026-02-06 13:25

Linux怎么限制特定IP访问_Linux配置hosts.allow黑名单【笔记】

2026-02-06 13:26

C++如何获取Windows系统服务列表_C++调用EnumServicesStatus方法【系统】

2026-02-06 13:31

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发 AI 聊天问答

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发 AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI 编程开发 Agent智能体

腾讯元宝

腾讯混元平台推出的AI助手

文档处理 AI 聊天问答

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发 AI 文本写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发 AI 文本写作

智谱清言 - 免费全能的AI助手

AI 编程开发 Agent智能体

相关专题

while的用法

while的用法是“while 条件: 代码块”，条件是一个表达式，当条件为真时，执行代码块，然后再次判断条件是否为真，如果为真则继续执行代码块，直到条件为假为止。本专题为大家提供while相关的文章、下载、课程内容，供大家免费下载体验。

2023.09.25

string转int

在编程中，我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算，或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

626

2023.08.02

int占多少字节

int占4个字节，意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值，在某些情况下也可能是2个字节或8个字节，int是一种常用的数据类型，用于表示整数，需要根据具体情况选择合适的数据类型，以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

552

2024.08.29