DFS(深度优先搜索)算法

Depth-First-Search

深度优先算法，是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。

当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。 这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点， 则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

DFS可用堆栈(Stack)和递归(Recursive)两种方法实现

如何跟踪下一步搜索的位置?

使用Stack： 列表中只从一端添加和移除:

• Push：添加元素
• Pop：删除一个元素

如何跟踪访问过的内容?

HashSet:：常量添加，删除和搜索

如何跟踪从开始到目标的路径?

HashMap：将每个节点链接到发现它的节点

堆栈和递归实现过程（伪代码）：

                    

BFS (广度优先搜索)算法

Breadth-First-Search

BFS是从根节点开始，沿着树的宽度遍历树的节点。

如果所有节点均被访问，则算法中止。 广度优先搜索的实现本篇笔记采用队列。

如何跟踪下一步搜索的位置?

Queue：列出你只从一端添加和移除的地方

• enqueue：添加一个元素
• deque：删除一个元素

如何跟踪访问过的内容?

HashSet：定时添加，删除和搜索

如何跟踪从开始到目标的路径?

HashMap：将每个节点链接到发现它的节点

和DFS唯一不同的是BFS使用队列来实现，伪代码如下：

学习参考资料：

深度优先和广度优先的Python实现

【Python算法】遍历(Traversal)、深度优先(DFS)、广度优先(BFS)

搜索思想——DFS & BFS（基础基础篇）

最新文章

1. Android开源益智游戏“斗地主”单机版源代码
2. lottery概率问题
3. [Spring] 事务级别定义
4. 第一章 ------ AutoYout介绍
5. linux下php-fpm 启动参数及重要配置
6. 02.lib-v1.js
7. G711
8. python mongodb 读写CSV文件
9. [Swustoj 24] Max Area
10. 【Android Studio】没有先安装JDK
11. SKPhysicsJointSpring类
12. mysql null值转换
13. 祖国版SoloWheel：Airwheel爱尔威火星车 拆箱&上手经验_运动户外_晒物广场_什么值得买
14. Fiddler捕获localhost的网站
15. npm管理工具介绍
16. sqlalchemy 外键
17. 008 使用POJO对象绑定请求参数
18. easyui datagrid 诡异的无法显示问题
19. JdbcTemplate详解
20. [BZOJ3560]DZY Loves Math V(欧拉函数)

热门文章

1. MAC EI Capitan上更新系统自带SVN版本号(关闭SIP方能sudo rm)
2. R8500 MPv2 版本 刷 Kong编译的 ddwrt 后，使用Entware-ng 安装opkg安装第三方软件
3. django 拷贝一个 model 实例
4. 【iCore1S 双核心板】DEMO V1.0 测试程序发布
5. Java编程的逻辑 (80) - 定时任务的那些坑
6. react给一个div行内加背景图片并实现cover覆盖模式居中显示
7. Go的微服务库kite
8. [Object Tracking] **Mask R-CNN
9. [UFLDL] ConvNet
10. js的 new Date()日期格式化显示以及js获取时间戳