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

拉风的博客

BFS

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

Posted by raphealguo on 30 八月, 2012 2 Comments
作者:raphealguo    文章来自http://rapheal.sinaapp.com/tag/bfs/

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.