搜索

  深度优先搜索和广度优先搜索广泛的应用于树和图中，但是他们的应用远不止于此。

BFS

  广度优先搜索一层一层地进行遍历，每层遍历都是以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点，遍历过的节点不能再次被遍历。

  第一层：

  0->{6.2.1.5}

  第二层：

  6->{4}

  2->{}

  1->{}

  5->{3}

  第三层：

  4->{}

  3->{}

  每一层遍历的节点都与根节点的距离相同，设di表示第i个节点与根节点的距离，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 di <= dj。利用这个结论，可以求解最短路径等 最优解 问题：第一次遍历到目的节点，其所经过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径，无权图是指从一个节点到另一个节点的代价都记为 1。

在程序实现BFS时需要考虑以下问题：

• 队列：用来存储每一轮遍历得到的节点
• 标记：对于遍历过的节点，应该将其标记，防止重复遍历。

最新文章

1. .NET Core Web 应用部署到 Docker 中运行
2. IOS开发中的几种设计模式介绍
3. Linux下添加硬盘，分区，格式化详解
4. js markdown chart flow
5. Javascript脚本应该放在哪里？
6. spark与storm的对比
7. Yii 增删改查 测试记录
8. android studio 使用的一些注意，一些报错的解决方法（原创）
9. ASP.NET MVC with Entity Framework and CSS一书翻译系列文章之第三章：搜索、高级过滤和视图模型
10. android:Fragment动画的东西
11. sencha cmd常用命令汇总
12. 自学Zabbix3.5.2-监控项item-types监控类型
13. angular2^ typescript 将 文件和Json数据 合并发送到服务器（1.客户端处理）
14. java的io库用到的装饰模式是如何体现的?
15. SaltStack数据系统-Grans详解
16. luogu P2680 运输计划
17. 分区实践 注意分区名 p2018-01 p2018-02 被解释为同一分区名
18. opencv学习之路（10）、ROI与mask掩码
19. firefox驱动的下载地址
20. Spring-事务管理（Transaction）

热门文章

1. Jdbc连接数据库基本步骤详解_java - JAVA
2. NOIP模拟赛(by hzwer) T3 小奇回地球
3. layui js动态添加的面板不能折叠
4. java 用RGB生成图片动态命名
5. WEB实现大文件上传和下载
6. POJ 3691 DNA repair ( Trie图 &amp;&amp; DP )
7. Java——类
8. [HG]钻石游戏diamond 题解
9. Java网络编程与NIO详解10：深度解读Tomcat中的NIO模型
10. SQL优化案例