当前位置：

首页 > 编程开发 > C++实现深度优先搜索方法详解

C++实现深度优先搜索方法详解

作者：小确幸时间：2025-08-06 浏览：0

C++中DFS递归调用栈可通过迷宫比喻理解，每次进入新节点即将其信息压入栈，回溯时弹出。调用栈深度反映搜索深度，过深可能导致栈溢出。处理环的方法是使用visited数组标记已访问节点，避免重复访问；另一种方法是采用三种状态（未访问、正在访问、已访问）来检测环。DFS与BFS的主要区别在于搜索方式：1.DFS尽可能深入探索路径，适合路径查找和环检测；2.BFS逐层扩展，适合寻找最短路径和连通分量。选择DFS的情况包括需要找到任意路径、检测图环或内存受限的场景，而BFS更适合需最短路径或完全遍历的问题。

C++如何实现深度优先搜索 C++深度优先搜索的代码实现

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它的核心思想是尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被发现为止。

#include 
#include 

using namespace std;

void dfs(int node, vector>& adj, vector& visited) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

int main() {
    int n, m; // n: 节点数量, m: 边的数量
    cin >> n >> m;

    vector> adj(n); // 邻接表
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 如果是无向图
    }

    vector visited(n, false);

    // 从节点0开始DFS
    dfs(0, adj, visited);
    cout << endl;

    return 0;
}

如何理解C++中DFS递归的调用栈？

想象一下，你在一座迷宫里，手里拿着一根线。你总是沿着一条路走到底，如果走到尽头，就沿着线退回上一个路口，再选择另一条路。这个“线”就是调用栈。

每次调用dfs函数，就像你在迷宫里走到了一个新的路口。这个路口的信息（节点编号、邻接表、访问标记）都会被压入调用栈。当dfs函数到达一个没有未访问邻居的节点时，函数执行完毕，就像你走到了迷宫的死胡同。这时，函数会从调用栈中弹出，回到上一个路口，继续搜索。

调用栈的深度反映了DFS搜索的深度。如果图非常深，调用栈可能会变得很大，导致栈溢出。

如何处理C++ DFS中的环？

在图中存在环的情况下，DFS可能会陷入无限循环。解决这个问题的方法是使用一个visited数组来跟踪已经访问过的节点。在上面的代码示例中，visited[node] = true;这一行代码就是用来标记节点已经被访问过。在递归调用dfs函数之前，会检查邻居节点是否已经被访问过if (!visited[neighbor])，如果已经被访问过，则跳过该邻居节点，避免无限循环。

另一种方法是使用三种状态来标记节点：未访问、正在访问、已访问。当第一次遇到一个节点时，将其标记为“正在访问”。当该节点的所有邻居都访问完毕后，将其标记为“已访问”。如果在DFS过程中遇到一个“正在访问”的节点，则说明存在环。

C++ DFS与BFS的区别是什么？什么时候应该使用DFS？

DFS和BFS都是图遍历算法，但它们的搜索方式不同。DFS像是一个“深度优先”的探险家，总是尽可能深地探索一条路径，直到无法继续前进才回溯。而BFS则像是一个“广度优先”的侦察兵，从起点开始，一层一层地向外扩展，先访问所有距离起点为1的节点，再访问所有距离起点为2的节点，以此类推。

选择DFS还是BFS取决于具体的问题：

DFS的优点：
- 更容易实现。
- 占用空间更少（在某些情况下）。
- 可以用于检测环。
- 可以用于解决路径搜索问题，例如迷宫求解。
BFS的优点：
- 可以找到最短路径（在无权图中）。
- 可以用于寻找连通分量。

如果问题需要找到最短路径，或者需要遍历图的所有节点，BFS通常是更好的选择。如果问题只需要找到一条路径，或者需要检测环，DFS可能更适合。此外，如果图非常深，BFS可能会占用更多的内存，因为需要存储所有已访问节点的队列。在这种情况下，DFS可能更有效。

本文内容来源于互联网，如有侵权请联系删除。

作者最新文章

Windows 10 2026-09-16 17:44

Python安装后怎么打开：使用IDLE或命令行启动解释器 2026-09-16 13:54

Windows系统Python安装教程：下载、勾选PATH及环境变量配置 2026-09-16 13:53

“等灯不计时”落地解析：算法善意如何转化为技术能力与生态协同 2026-09-08 18:03

英伟达推出NVHBM：定制HBM带宽提升30%并扩展NVLink Fusion生态 2026-09-08 17:31

编程开发 C++

上一篇：哈啰单车退款申请方法详解

下一篇： LangGraph官网下载入口及安装步骤详解

相关文章更多

LangGraph官网下载入口及安装步骤详解

Python 环境配置

09.22

windsurf ide使用教程新手快速入门指南

新手教程开发工具 AI编程代码编辑器

09.22

genspark ai developer 2.0使用教程

AI开发全栈开发

09.22

langgraph agent流式加streamlit实现流式输出教程

Python开发

09.22

讯飞星火认知大模型能用多久？免费使用期限说明

讯飞星火 API调用

09.22

C++动态数组初始化怎么写？常用语句与代码示例

内存管理 C++ 动态数组

09.21

C++类构造与析构函数详解

C++

08.17

C++中std::upper

C++

08.16

C++常对象与成员解析

C++

08.15

using namespace 使用中遇到的问题怎么解决

08.07

热门文章更多

Yandex中文入口及登录使用全攻略 51漫画高清入口及最新章节更新 B站免费入口永久有效网址推荐 58动漫网入口及永久访问方法蓝海书屋免费小说全本阅读推荐入口 B站免费入口网站高效连接方法

精品专题更多

装机必备

正软商城装机必备专区，精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件，帮助用户快速完成新电脑软件配置。

Windows

正软商城Windows软件专区，汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件，提供软件介绍、系统要求、正版授权及购买下载服务。

macOS软件

正软商城macOS软件专区，精选适用于Mac电脑的办公、设计、影音、效率、开发和系统工具，提供软件功能介绍、macOS兼容版本、正版授权及购买下载服务。

IOS软件

正软商城iOS软件专区，精选适用于iPhone和iPad的办公、学习、影音、设计、效率及AI应用，提供功能介绍、适用设备、系统要求和正版获取方式等信息。

正软商城AI软件专区，汇集AI写作、AI绘画、AI视频、AI办公、AI编程、AI翻译、智能客服和数据分析等人工智能工具，提供功能介绍、适用平台、收费方式及正版购买信息。

Mac软件更多

灵活计算器

灵活计算器是一款笔记式算数应用，支持实时计算、动态关联和云端同步功能。记录、整理和输出之间的过渡会更自然，适合长期写作、做笔记或持续沉淀个人内容。

macOS软件 Android IOS软件装机必备

赤友清理大师

赤友清理大师是一款为 Mac 设计的智能清理优化工具，可精准扫描垃圾、大文件、重复文件等，释放磁盘空间。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

macOS软件装机必备

极度公式

极度公式是一款跨平台专业LaTeX公式识别编辑软件，支持OCR公式识别和多平台编辑。和使用说明，避免使用，享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

Windows macOS软件 Linux 装机必备

图几

图几是一款适用于 macOS 的截图、标注与美化工具，支持离线操作保障隐私。界面整理和高频系统操作被放到一起考虑，桌面或窗口内容一多时，管理起来会更省心。

macOS软件装机必备

密码键盘

密码键盘是一款兼具安全性与便捷性的高效密码管理器。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows macOS软件 Android IOS软件装机必备

思源笔记

思源笔记是一款本地笔记软件，提供所见即所得的编辑方式，为长文写作带来顺滑的体验。记录、整理和输出之间的过渡会更自然，适合长期写作、做笔记或持续沉淀个人内容。

Windows macOS软件 Android IOS软件装机必备

Office 365 简体中文

一款文字处理软件，一种订阅式的跨平台办公软件，基于云平台提供多种服务，通过将 Excel 和 Outlook 等应用与 OneDrive 和 Microsoft Teams 等强大的云服务相结合，Office 365 可让任何人使用任何设备随时随地创建和共享内容。

WALTR PRO

WALTR是一款电脑至iOS文件传输转换工具，操作简单，快速实现文件识别与传送。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

Windows macOS软件

CodeExpander

CodeExpander 是一款快捷短语输入增强工具，通过键入缩写自动展开为自定义文段，提升工作效率。任务管理和过程控制会更完整，持续下载、批量同步或需要稳定传输流程的场景会更适合它。

Windows macOS软件

Mountain Duck

Mountain Duck 是一款能将多个网盘挂载到本地的工具，像本地磁盘一样使用网盘。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。

Windows macOS软件

Menuist

Menuist 是一款面向 macOS 的 Finder 右键菜单增强工具，主要用来补充新建文件、快捷导航等常用操作，让日常文件管理和访问路径时更高效、更顺手。

macOS软件

Mole

Mole 是一款专为 Mac 设计的深度清理优化工具，涵盖缓存清理、应用管理及实时状态监控等功能。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。

macOS软件

WINDOWS 更多

Windows 10

Windows 10 是一款微软推出的经典操作系统，拥有硬件兼容性与多任务处理能力。它更偏向把系统状态查看和常用调节动作放在一起，适合需要持续观察和微调设备状态的场景。

Windows 10 Windows 操作系统装机必备

极度公式

Windows macOS软件 Linux 装机必备

密码键盘

密码键盘是一款兼具安全性与便捷性的高效密码管理器。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows macOS软件 Android IOS软件装机必备

思源笔记

Windows macOS软件 Android IOS软件装机必备

傲梅轻松备份

傲梅轻松备份是一款专业易用的数据备份软件，为重要数据提供安全保障。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows 装机必备

Office 365 简体中文

Wise Folder Hider Pro

Wise Folder Hider Pro 是一款专业级文件和文件夹隐藏加密软件，为私密数据添加多重保护。高频操作更强调就近处理，浏览、整理和跨目录移动文件时，来回切换和重复点击都会少很多。

Windows

WALTR PRO

Windows macOS软件

CodeExpander

Windows macOS软件

PinStack

PinStack是一款轻量级的Windows平台剪贴板管理工具，优化您的剪贴板使用体验。它更偏向把系统状态查看和常用调节动作放在一起，适合需要持续观察和微调设备状态的场景。

Windows

Mountain Duck

Windows macOS软件

Seer

Seer是一款在Win平台下的空格键功能增强效率工具，只需轻敲空格键，就能预览几乎任何格式的文件。它更适合把零散的小功能集中起来使用，处理高频琐碎任务时会更省事。

Windows