广度宽度优先搜索(BFS)

广度宽度优先搜索(BFS)

广度/宽度优先搜索(BFS)

【算法入门】

1.前言

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

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

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

2.图的概念

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

图2-1 连通图示例图

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

一般我们把顶点用V缩写,把边用E缩写。

3.广度优先搜索

3.1.算法的基本思路

常常我们有这样一个问题,从一个起点开始要到一个终点,我们要找寻一条最短的路径,从图2-1举例,如果我们要求V0到V6的一条最短路(假设走一个节点按一步来算)【注意:

Word文档免费下载Word文档免费下载:广度宽度优先搜索(BFS) (共11页,当前第1页)

你可能喜欢

  • 广度优先搜索
  • 深度优先搜索算法
  • 系统故障诊断方法
  • 信息学奥赛
  • 规划模型

广度宽度优先搜索(BFS)相关文档

最新文档

返回顶部