当前位置:

首页 > 编程开发 > 深度优先搜索(DFS)算法解释,具体原理和步骤图解,以及Python代码实现DFS算法

深度优先搜索(DFS)算法解释,具体原理和步骤图解,以及Python代码实现DFS算法

DFS算法又名深度优先搜索,作为递归算法,通过堆栈,在避免循环的同时遍历目标所有节点。DFS算法的工作原理图解以具有5个节点的无向图为例,如下图:从节点0开始,DFS算法首先将其放入Visited列表并将其所有相邻顶点放入堆栈。接着,访问堆栈顶部的节点1,并转到其相邻节点。因为0已经被访问过,所以访问2。节点2有一个未访问的相邻节点4,因此我们将其添加到堆栈顶部并访问它。现在,还有最后一个节点没有访问,我们继续往下。在最后访问3之后,已经没有还未访问的相邻节点,因此我们完成了该无向图的深度优先遍历。DFS

本文目录

    DFS算法又名深度优先搜索,作为递归算法,通过堆栈,在避免循环的同时遍历目标所有节点。

    DFS算法的工作原理图解

    以具有5个节点的无向图为例,如下图:

    DFS算法概念原理详细图解 Python代码实现DFS算法

    从节点0开始,DFS算法首先将其放入Visited列表并将其所有相邻顶点放入堆栈。

    DFS算法概念原理详细图解 Python代码实现DFS算法

    接着,访问堆栈顶部的节点1,并转到其相邻节点。因为0已经被访问过,所以访问2。

    DFS算法概念原理详细图解 Python代码实现DFS算法

    节点2有一个未访问的相邻节点4,因此我们将其添加到堆栈顶部并访问它。

    DFS算法概念原理详细图解 Python代码实现DFS算法

    现在,还有最后一个节点没有访问,我们继续往下。在最后访问3之后,已经没有还未访问的相邻节点,因此我们完成了该无向图的深度优先遍历。

    DFS算法概念原理详细图解 Python代码实现DFS算法

    DFS算法伪代码

    在init()函数中,请注意我们在每个节点上运行DFS函数。这是因为图可能有两个不同的不连贯部分,因此为了确保覆盖每个顶点,我们还可以在每个节点上运行DFS算法。

    DFS(G, u)
        u.visited = true
        for each v ∈ G.Adj[u]
            if v.visited == false
                DFS(G,v)
    init() {
        For each u ∈ G
            u.visited = false
         For each u ∈ G
           DFS(G, u)
    }

    Python代码实现DFS算法

    def dfs(graph, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
    
        print(start)
    
        for next in graph[start] - visited:
            dfs(graph, next, visited)
        return visited
    
    graph = {'0': set(['1', '2']),
             '1': set(['0', '3', '4']),
             '2': set(['0']),
             '3': set(['1']),
             '4': set(['2', '3'])}
    
    dfs(graph, '0')
    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    相关文章 更多
    如何在Visual Studio2022导入已有代码文件夹创建项目
    如何在Visual Studio2022导入已有代码文件夹创建项目

    详解 Visual Studio 2022 如何从现有代码文件夹创建 C++、C# 或 VB 项目,对比打开文件夹与加载 .sln 文件的区别,避免重复构建结构,确保项目配置正确。

    Visual Studio2019导出导入IDE布局窗口配置文件
    Visual Studio2019导出导入IDE布局窗口配置文件

    详细步骤指南:在 VS2019 中调整并保存工具窗口布局,使用导入导出向导选择 Window Layouts 类别生成 .vssettings 文件,并在另一台机器或实例中恢复布局,同时处理多显示器适配问题。

    VisualStudio2022社区版如何从官网下载安装包
    VisualStudio2022社区版如何从官网下载安装包

    详细讲解 Visual Studio 2022 社区版的官方下载入口、引导程序获取、工作负载配置及安装启动步骤,确保用户正确安装开发环境。

    Visual Studio2017调试附加到进程,附加运行中程序
    Visual Studio2017调试附加到进程,附加运行中程序

    学习在 Visual Studio 2017 中通过“附加到进程”功能调试正在运行的应用程序。了解如何正确选择进程实例、配置调试类型,并解决因符号文件或源码不匹配导致的断点失效问题。

    Visual Studio2019禁用IDE后台自动代码扫描提升速度
    Visual Studio2019禁用IDE后台自动代码扫描提升速度

    针对 Visual Studio 2019 编辑大型项目时的卡顿问题,提供分语言关闭后台代码分析的具体步骤,包括 C#/VB 的分析范围设置、C++ 的后台分析禁用选项以及 .NET Framework 的项目文件配置方法。

    Visual Studio2017解决方案资源管理器窗口不见了找回办法
    Visual Studio2017解决方案资源管理器窗口不见了找回办法

    Visual Studio 2017 解决方案资源管理器不见了怎么办?通过快捷键 Ctrl+Alt+L、视图菜单或重置窗口布局即可快速恢复。本文详解各种场景下的找回技巧及注意事项。

    Visual Studio2022代码注释插件管理与卸载方法
    Visual Studio2022代码注释插件管理与卸载方法

    详细指南:如何在 Visual Studio 2022 中安全卸载代码注释扩展。涵盖打开扩展管理器、区分禁用与卸载、处理待处理更改及确认卸载结果的操作步骤。

    Visual Studio2022重置IDE全部设置恢复默认界面
    Visual Studio2022重置IDE全部设置恢复默认界面

    当 Visual Studio 2022 的界面布局或编辑器设置混乱时,可通过内置向导一键重置所有设置。本文详解操作步骤,涵盖是否备份现有配置的选择逻辑及默认集合的选取方法,确保用户能安全、高效地恢复初始开发环境。

    Visual Studio2019编辑器代码折叠区域自定义设置
    Visual Studio2019编辑器代码折叠区域自定义设置

    掌握 Visual Studio 2019 的代码折叠功能,包括使用 Ctrl+M 快捷键切换视图、通过 #region 配对创建自定义折叠块,以及调整可折叠区域的高亮颜色,帮助开发者更高效地浏览和管理大型代码文件。

    Visual Studio2017C++静态库项目引用配置实操
    Visual Studio2017C++静态库项目引用配置实操

    针对 Visual Studio 2017 C++ 开发,讲解如何正确引用静态库。涵盖同解决方案项目引用添加方法,以及外部 .lib 文件的包含目录、库目录和链接器输入配置步骤,帮助开发者避免头文件缺失或链接失败问题。

    查看更多
    精品专题 更多
    装机必备
    装机必备

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

    Windows
    Windows

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

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。