• Works
    • 笔记
    • 资源
  • 关于我

拉风的博客

入门

【算法入门】深度优先搜索(DFS)

Posted by raphealguo on 30 八月, 2012 Leave a Comment
作者:raphealguo    文章来自http://rapheal.sinaapp.com/tag/%E5%85%A5%E9%97%A8/

1.前言

深度优先搜索(缩写DFS)有点类似广度优先搜索,也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个节点,然后从另一条路开始走到底,这种尽量往深处走的概念即是深度优先的概念。

你可以跳过第二节先看第三节,:)

2.深度优先搜索VS广度优先搜索

2.1演示深度优先搜索的过程

还是引用上篇文章的样例图,起点仍然是V0,我们修改一下题目意思,只需要让你找出一条V0到V6的道路,而无需最短路。

图2-1 寻找V0到V6的一条路(无需最短路径)

假设按照以下的顺序来搜索:

1.V0->V1->V4,此时到底尽头,仍然到不了V6,于是原路返回到V1去搜索其他路径;

2.返回到V1后既搜索V2,于是搜索路径是V0->V1->V2->V6,,找到目标节点,返回有解。

这样搜索只是2步就到达了,但是如果用BFS的话就需要多几步。 [Read more...]

Posted in: 算法入门 | Tagged: dfs, 入门, 算法

【算法入门】广度/宽度优先搜索(BFS)

Posted by raphealguo on 30 八月, 2012 2 Comments
作者:raphealguo    文章来自http://rapheal.sinaapp.com/tag/%E5%85%A5%E9%97%A8/

1.前言

广度优先搜索(也称宽度优先搜索,缩写BFS,以下采用广度来描述)是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域,故得名。

一般可以用它做什么呢?一个最直观经典的例子就是走迷宫,我们从起点开始,找出到终点的最短路程,很多最短路径算法就是基于广度优先的思想成立的。

算法导论里边会给出不少严格的证明,我想尽量写得通俗一点,因此采用一些直观的讲法来伪装成证明,关键的point能够帮你get到就好。

2.图的概念

刚刚说的广度优先搜索是连通图的一种遍历策略,那就有必要将图先简单解释一下。

图2-1 连通图示例图

如图2-1所示,这就是我们所说的连通图,这里展示的是一个无向图,连通即每2个点都有至少一条路径相连,例如V0到V4的路径就是V0->V1->V4。

一般我们把顶点用V缩写,把边用E缩写。 [Read more...]

Posted in: 算法入门 | Tagged: BFS, 入门, 算法

标签

BFS CA CSS dfs ExtCSS HTTP HTTPS jQuery MVVM PHP源码 Sizzle ssl uglifyjs Vue Vue2.x webview模拟器 Web开发 Zend源码 上线 云南游 入门 前端工程 加密 协议 工具 提测 效率 数字签名 数学 旅游 游戏 源码 灰度 监控 硬件 算法 网络模型 计算机 认证

近期评论

  • 捕获页面中全局Javascript异常 - 算法网 发表在《前端代码异常监控》
  • Augustmyv 发表在《如何学习Vue2源码》
  • Holographicuqj 发表在《如何学习Vue2源码》
  • Foamcub 发表在《如何学习Vue2源码》
  • liusir 发表在《关于我》

链接表

  • bang
  • DIV.IO
  • 小木舟

Copyright © 2023 拉风的博客.

Theme by ThemeHall.