dfs算法总结_dfs和bfs算法的区别

dfs算法总结_dfs和bfs算法的区别DFS深度优先搜索主要有两种实现方法:栈和递归什么是DFS?说白了就是一直遍历元素的方式而已,我们可以把它看成是一条小蛇,在每个分叉路口随意选择一条路线走,直到撞到南墙,才会调头返回到上一个分叉路口,走另外一条路,有时候运气很好,撞到了目标点,那么这个算法就结束了。模板:参数1DFS(参

大家好,欢迎来到IT知识分享网。

DFS 深度优先搜索

主要有两种实现方法:栈和递归

什么是DFS?说白了就是一直遍历元素的方式而已,我们可以把它看成是一条小蛇,在每个分叉路口随意选择一条路线走,直到撞到南墙,才会调头返回到上一个分叉路口,走另外一条路,有时候运气很好,撞到了目标点,那么这个算法就结束了。

模板:

 参数1 DFS(参数2)
{
     if(返回条件成立) return 参数 ;
    DFS(进行下一步的搜索遍历) ;
回朔;
}

1)if 语句:

作用就是告诉小蛇:是否撞到南墙啦?撞到就返回啦,或者,是否到达终点啦?到了就结束啦!

所以使用DFS解决问题的时候需要思考这两个问题:是否有条件不成立的信息(撞到南墙),是否有条件成立的信息(到达终点)。

还有一个非常重要的信息:是否需要标记访问节点。

2)作标记

是为了防止重复访问,出现环回

dfs算法总结_dfs和bfs算法的区别

 如何标记一个节点是否访问过呢?标记常用方法有数组法和set 

bool visited[length] ; //数组表示,每访问过一个节点,数组将对应元素置为true
Set<类型> set; //建立set,每访问一个节点,将该节点加入到set中去

也可以在原数组上进行标记,具体题目具体分析

3)回朔

这点不能忽略,回退到上一节点,继续向下搜索

 总之使用dfs需要考虑三点:

a,是否有条件不成立的信息(撞南墙)

b,是否有条件成立的信息(到终点)

c,是否需要记录节点(记轨迹)

3)啥时候使用dfs呢 

当我们遇到的问题与路径相关,且不是寻找最短路径(最短路径为BFS,下次再说),或者需要遍历一个集合中的所有元素,或者是查找某一种问题的全部情况时,我们可以考虑使用DFS来求解。

LeetCode常见题目如下:

1、求1到n的全排列

参考博客:https://blog.csdn.net/li_jeremy/article/details/83714298

2、岛屿数量

3、岛屿的最大面积

4、黄金矿工

5、单词搜索

6、全排列

7、无重复字符串的排列组合

8、被围绕的区域

9、路径总和||

10、组合总和 、组合总和|| 、组合总和|||

11、组合 https://leetcode-cn.com/problems/combinations/submissions/

12、 https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/submissions/

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/29362.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信