文档章节

见女神的极简之途——BFS算法

 开普勒鑫球
发布于 2018/04/03 17:40
字数 994
阅读 10
收藏 0

 

三月,空气中弥漫着恋爱的味道,程序员哧溜君忽然接到女神电话要去见丈母娘了(喜闻乐见),女神一再叮嘱头一次得好好地准备准备,而且不能迟到:

  • 到【艾欧尼亚】做头发;

  • 到【德玛西亚】买给岳父的保养品;

  • 到【扭曲丛林】买给丈母娘的护肤品;

  • 到【皮城警备】买给准小侄子的玩具;

  • 最后才能到【女神家】……

每个地方的距离都很远,如何合理地规划路线?这相似的场景,程序员哧溜君不觉笑了起来……

 

BFS是什么

BFS全称为Breadth-First-Search,即⼴度优先遍历算法,是经典的连通图遍历算法。简单的说, BFS是从根结点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问则算法结束。

换成算法语来描述的话就是:

  • 首先将根节点放到待遍历的队列Q中;

  • 循环从Q中获取待遍历的节点N;

  • 获取节点N通过条边可以到达的所有节点集合L;

  • 循环遍历节点集合 L,判断L的元素是否存在于已遍历的节点集合C中;

    • 已存在集合 C中,则忽略;

    • 不存在集合 C中,则将此节点加⼊到队列 Q中;

  • 循环遍历Q直到Q为空则遍历结束。

(没看懂没关系,后面有详细讲解呢,哧溜~)

 

BFS⽤来做什么

BFS作为图遍历的基础算法,它的算法思想被很多高级算法借鉴和使用。 Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

 

我们可以对哧溜君见丈母娘之路进行建模,A点为哧溜君所在之处,B点为目的地,找到A与B之间的最短路径。

 

针对上述问题有很多算法方案可以解决,其中BFS算法是较简单和直接的方案。以A节点为根节点通过BFS遍历其他节点,直到遍历到B节点为止,这种理想情况下说起来还是比较简单的。

 

但是不要认为这样就可以完美解决这个问题,完美的解决方案还需要考虑以下因素:

  • 哧溜君在行走的过程中,如何避免遇到前女友;

  • 在那么多的目的地之中寻找最先去的目的地;

  • 在哧溜君去往目的地的路上,判断是否需要翻墙、踩水坑、闯红灯;

 

BFS怎么做

以上都是理论知识,读起来可能比较枯燥。我们举个例子来进一步说明BFS算法。给定一个图,从图中一个节点出发,通过BFS遍历所有能遍历的节点。

  • 图的初始状态如下:

  • 初始状态,从顶点 1开始,队列 ={1};

  • 访问1的邻接顶点, 1出队变⿊, 2,3⼊队,队列 ={2,3,};

  • 访问2的邻接结点, 2出队,4⼊队,队列 ={3,4};

  • 访问3的邻接结点, 3出队,队列 ={4};

  • 访问4的邻接结点, 4出队,队列 ={空};

     

经过上述遍历过程,我们已经通过BFS算法找到所有节点1可以到达的节点,进一步可以分析出节点1到每个节点的最短距离,哈哈哈哈哈……

 

程序员哧溜君经过一番计算后,

 

 

 

终于……终于……从梦中醒来了。

程序员怎么可能有女朋友啊,而且还是女神!

还是去程序里继续new对象吧。

回复“BFS”获取示例代码,欢迎和哧溜君一起交流,尤其欢迎女神!

 

推荐阅读:机器人编程大赛的沙盒源代码正式开放提供下载啦!

编辑:开普勒鑫球-哧溜君、大玲、剑圣

 

本文转载自:https://mp.weixin.qq.com/s/lgUQt8uOp8nZJKVGUMr9vg

粉丝 1
博文 31
码字总数 0
作品 0
南京
私信 提问
深度学习中不得不学的Graph Embedding方法

这里是 的第十四篇文章,之前已经有无数同学让我介绍一下Graph Embedding,我想主要有两个原因: 一是因为Graph Embedding是推荐系统、计算广告领域最近非常流行的做法,是从word2vec等一路发...

王喆的机器学习笔记
2019/04/30
0
0
bryce1010专题——BFS

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/82924309 bryce1010专题——BFS 1. BFS模板题: PO...

bryce1010
2018/10/02
0
0
Kotlin Weekly 中文周报 —— 16

Kotlin 开发中文周报 文章 Android 开发者的一些实用技巧。(github.com) Ravindra 在 DevfestAhm 2017 的演讲。 像 Kotlin 的专家一样测试 。(blog.karumi.com) 将 Kotlin 库发布到 jCente...

DoubleThunder
2017/11/13
0
0
遇到女神应该使用什么样的暗恋思维

这是一年前的回忆 一个是隔壁邻居家儿子,一个是同事的儿子。前者很腼腆,后者很开朗。最近他们都遇到了同一个问题:暗恋上了班上的女生。(我很八卦,请原谅) 不知道大家上学时候(我们从初...

shenyisyn
2014/12/11
0
0
【HDU - 1010】Tempter of the Bone(dfs+剪枝)

Tempter of the Bone 直接上中文了 Descriptions: 暑假的时候,小明和朋友去迷宫中寻宝。然而,当他拿到宝贝时,迷宫开始剧烈震动,他感到地面正在下沉,他们意识到这是一个陷阱!他们想尽一...

Sky丨Star
2019/07/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Hadoop入门

概述 Hadoop是一个由Apache基金会所开发的分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。Hadoop实现了一个分布式文...

阿dai学长
51分钟前
34
0
Go Web 编程之 数据库

概述 数据库用来存储数据。只要不是玩具项目,每个项目都需要用到数据库。现在用的最多的还是 MySQL,PostgreSQL的使用也在快速增长中。 在 Web 开发中,数据库也是必须的。本文将介绍如何在...

darjunlee
今天
79
0
spring-boot-maven-plugin not found的解决方案。

通过IDE创建一个springboot项目, <plugin> <groupId>org.springframework.boot</groupId>//这行红色 <artifactId>spring-boot-maven-plugin</artifactId>//这行红色</plugin> 提示sprin......

一片云里的天空
今天
118
0
OSChina 周三乱弹 —— 我可能是个憨憨

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @宇辰OSC :分享Hare Je的单曲《Alan Walker-Faded(Hare Je remix)》: #今日歌曲推荐# 可以放松大脑的一首纯音乐 《Alan Walker-Faded(Har...

小小编辑
今天
966
8
搞定SpringBoot多数据源(3):参数化变更源

春节将至,今天放假了,在此祝小伙伴们新春大吉,身体健康,思路清晰,永远无BUG! 一句话概括:参数化变更源意思是根据参数动态添加数据源以及切换数据源,解决不确定数据源的问题。 1. 引言...

mason技术记录
昨天
99
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部