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

拉风的博客

dfs

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

Posted by raphealguo on 30 八月, 2012 Leave a Comment
作者:raphealguo    文章来自http://rapheal.sinaapp.com/tag/dfs/

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 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.