首页 > 其他分享 >dfs深度优先搜索

dfs深度优先搜索

时间:2024-09-13 23:02:13浏览次数:10  
标签:优先 adjList target 递归 DFS 搜索 dfs visited 节点

面试题 04.01. 节点间通路 - 力扣(LeetCode)

class Solution {
public:
    bool dfs(unordered_map<int, vector<int>>& adjList, vector<bool>& visited, int current, int target){
        if(current == target){
            return true;
        }
        visited[current] = true;
        for(int g : adjList[current]){
            if(!visited[g]){
                if(dfs(adjList, visited, g, target)){
                    return true;
                }
            }
        }
        return false;
    }
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        //创建邻接表
        unordered_map<int, vector<int>> adjList(n);
        for(auto& edge : graph){
            adjList[edge[0]].push_back(edge[1]);
        }
        //创建访问状态表
        vector<bool> visited(n, false);
        return dfs(adjList, visited, start, target);
    }
};

 dfs的核心要素:

邻接表:unordered_map<int, vector<int>> adjList(n);

访问状态表:vector<bool> visited(n, false)

使用递归的方式实现

一个问题:为什么代码片段

if(dfs(adjList, visited, g, target)){
                    return true;
                }

里面要return true,不是如果current == target,就return了吗?

GPT回答:这行代码确保递归一旦找到目标节点,就立即停止递归并返回 true,无需继续探索其他邻接节点。。

因为 `current == target` 只检查当前递归调用中的节点是否是目标节点,但要记住 DFS 是递归的,因此你需要逐步递归地检查每个节点的邻接节点。如果在某个递归路径中找到了目标节点,我们就应该立即终止该路径上的所有递归,并返回 `true`。

 

DFS(深度优先搜索,Depth-First Search)是一种用于图或树的遍历算法。DFS 的目标是尽可能深地沿着图的每一条分支进行探索,直到遇到终止条件(如没有未访问的邻接节点或找到目标),然后回溯到上一个节点并继续探索其他分支。

关键步骤:

  1. 访问当前节点
  2. 递归地访问未访问的邻接节点
  3. 如果当前节点的所有邻接节点都访问过,回溯到上一层,继续遍历其他节点。

关键点:

  • 递归的深度探索:DFS 会一直沿着一个方向进行深度探索,直到没有邻接节点可访问或找到目标节点。
  • 回溯:如果一个路径探索完毕没有找到目标节点,DFS 会回到上一个节点继续探索其他分支。
  • 递归返回值:如果在某个路径上找到目标节点,整个递归都会提前返回,避免不必要的进一步探索。

DFS 的优缺点:

  • 优点:DFS 适合用于查找图中的某一条路径,或者解决类似迷宫路径等问题,它的递归实现非常直观。
  • 缺点:DFS 可能会进入较深的路径,因此在某些情况下(如图很深或有循环)可能会导致栈溢出,或不一定找到最短路径(相比 BFS,DFS 并不保证找到最短路径)。

时间复杂度:

  • 如果图使用邻接表表示,DFS 的时间复杂度是 O(V + E),其中 V 是节点的数量,E 是边的数量。

标签:优先,adjList,target,递归,DFS,搜索,dfs,visited,节点
From: https://www.cnblogs.com/spp20/p/18413055

相关文章

  • 代码随想录算法训练营,9月13日 | 654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索
    654.最大二叉树题目链接:654.最大二叉树文档讲解︰代码随想录(programmercarl.com)视频讲解︰最大二叉树日期:2024-09-13想法:根据昨天中后序列构造二叉树的经验,要找到数组中的最大值的位置,可以设置两个指针表示子树的范围(左闭右开)Java代码如下:classSolution{publicTreeNo......
  • 自然语言处理系列六十八》搜索引擎项目实战》搜索引擎系统架构设计
    注:此文章内容均节选自充电了么创始人,CEO兼CTO陈敬雷老师的新书《自然语言处理原理与实战》(人工智能科学与技术丛书)【陈敬雷编著】【清华大学出版社】文章目录自然语言处理系列六十八搜索引擎项目实战》搜索引擎系统架构设计搜索引擎项目代码实战总结自然语言处理系......
  • 【每日一题】LeetCode 2398.预算内的最多机器人数目(滑动窗口、数组、二分查找、前缀和
    【每日一题】LeetCode2398.预算内的最多机器人数目(滑动窗口、数组、二分查找、前缀和、堆(优先队列))题目描述给定两个整数数组chargeTimes和runningCosts,分别代表n个机器人的充电时间和运行成本。再给定一个整数budget,表示预算。我们需要计算在不超过预算的情况下,最......
  • leetcode刷题day17|二叉树Part05(654.最大二叉树、617.合并二叉树、700.二叉搜索树中的
    654.最大二叉树构造树一般采用的是前序遍历,因为先构造中间节点,然后递归构造左子树和右子树。递归三步曲:1、传入参数,整数数组,数组的开始和结束,返回树的中间节点。2、终止条件:开始大于等于结束,即数组为空。3、递归逻辑:找到最大的元素,记录元素其下标,构建中间节点;递归构造......
  • 按图搜索的实时性:阿里巴巴拍立淘API返回值的快速响应
    阿里巴巴拍立淘API作为一种基于图像识别技术的搜索服务,其返回值的快速响应是其实时性的重要体现。以下是对阿里巴巴拍立淘API返回值的快速响应的详细解释,并包含代码示例。一、快速响应机制图像识别技术:阿里巴巴拍立淘API利用先进的图像识别技术,能够迅速分析用户上传的图片特征,并与......
  • fastDFS - 单机部署 + nginx
    准备查看操作系统的版本信息[root@lab10~]#cat/etc/redhat-releaseCentOSLinuxrelease7.9.2009(Core)查看操作系统的网卡地址[root@lab10~]#ipaddressshowens322:ens32:<BROADCAST,MULTICAST,UP,LOWER_UP>mtu1500qdiscpfifo_faststateUPgroupdef......
  • nginx 添加 ngx_fastdfs_module 模块
    目录nginx添加ngx_fastdfs_module模块背景安装fastdfslibcommon组件安装libserverframe组件安装fastdfs源码编译安装nginx重新源码编译下载ngx_fastdfs_module模块下载nginx源码包替换nginx添加ngx_fastdfs_module模块背景我在机器上源码安装了一个nginx,然后用户又让......
  • 基于matlab的黄金搜索法【开源/可直接复制粘贴】
    黄金搜索法是一种无须函数导数的数值优化方法。它基于黄金分割比例来选择新的搜索区间,以逐步缩小搜索范围并逼近极值点。在每次迭代中,算法会根据当前搜索区间的长度和黄金分割比例来计算两个新的点,并在这两个点处评估函数值。然后,根据这两个点的函数值比较结果,选择包含更优解(......
  • 掌握CFML:在输出缓冲区中高效搜索字符串的技巧
    掌握CFML:在输出缓冲区中高效搜索字符串的技巧在开发过程中,特别是使用ColdFusionMarkupLanguage(CFML)进行Web开发时,处理大量数据并快速找到特定字符串是一项常见且重要的任务。为了提高程序效率,我们经常需要在输出缓冲区中搜索特定的字符串,并在必要时对其进行处理。本文将分......
  • HDFS批量清理过期文件
    #!/bin/bashsource~/.bashrc#HADOOP所在的bin目录HADOOP_BIN_PATH=/opt/cloudera/parcels/CDH/bin#待检测的HDFS目录d1=/tmp1d2=/tmp/sac-sac1d3=/tmp/cep-bu4d4=/tmp/test_data_standardd5=/tmp/test_data_standard_sac#将待检测的目录(可以为多个)加载至数组中......