专栏首页完美Excel基础扩展 | 16. 队列应用示例:广度优先搜索

基础扩展 | 16. 队列应用示例:广度优先搜索

学习Excel技术,关注微信公众号:

excelperfect

在前一篇文章《基础扩展 | 15:队列》中,我们使用VBA代码实现了队列数据结构,本文将在广度优先搜索中应用队列。因此,本文的基础代码在《基础扩展 | 15:队列》中。

广度优先搜索是一种图算法,能够让你找出两者之间的最短路径。下面,我们使用《图解算法:像小说一样有趣的算法入门书》中的一个示例,使用VBA代码来实现广度优先搜索。

示例是这样的:假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。你可以在你的朋友中查找,看他是否是芒果销售商;如果没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找。你的朋友关系网如下图1所示,朋友是一度关系,朋友的朋友是二度关系。

图1

一度关系胜过二度关系,二度关系胜过三度关系,依此类推。因此,你应该先在一度关系中搜索,确定其中没有芒果销售商后,才在二度关系中搜索。这正是广度优先搜索所做的。在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系。具体到图1所示的例子,先检查ALICE、BOB、CLAIRE,再检查ANUJ、PEGGY、THOM、JONNY。

因此,在队列中,一度关系在二度关系之前加入查找名单,然后按添加顺序查找。下面是完整的VBA代码:

'创建新队列

Dim SearchQueue As New Queue

Sub BFS()

Dim myDic As Object

Dim myDicSearched As Object

Dim pearson

Dim i As Long

'创建字典对象

Set myDic =CreateObject("Scripting.Dictionary")

Set myDicSearched =CreateObject("Scripting.Dictionary")

'构建图

myDic.Item("you") =Array("alice", "bob", "claire")

myDic.Item("bob") =Array("anuj", "peggy")

myDic.Item("alice") =Array("peggy")

myDic.Item("claire") =Array("thom", "jonny")

myDic.Item("anuj") =Array("")

myDic.Item("peggy") =Array("")

myDic.Item("thom") =Array("")

myDic.Item("jonny") =Array("")

'将你的邻居加入到搜索队列中

For i = 0 To UBound(myDic.Item("you"))

SearchQueue.AddmyDic.Item("you")(i)

Next i

'只要队列不为空就执行循环

Do While Not SearchQueue.QueueEmpty

'取出队列中的第一个人

pearson = SearchQueue.Remove()

'检查这个人是否被检查过

If Not myDicSearched.Exists(pearson)Then

'如果这个人是芒果销售商

If PearsonIsSeller(pearson) Then

Debug.Print pearson &"是芒果销售商."

'不是芒果销售商

ElseIf pearson <>"" Then

'将这个人的朋友加入搜索队列

For i = 0 ToUBound(myDic.Item(pearson))

SearchQueue.AddmyDic.Item(pearson)(i)

Next i

'将这个人添加到已搜索的字典列表

myDicSearched.Add pearson,""

End If

End If

Loop

'释放

Set myDic = Nothing

End Sub

'判断是否是芒果销售商示例代码

Function PearsonIsSeller(name)As Boolean

If Right(name, 1) = "m" Then

PearsonIsSeller = True

End If

End Function

注意,运行上述代码需要先创建队列数据结果,这已经在《基础扩展 | 15:队列》中实现,为了节省篇幅,这里没有重复列出。

运行上述代码的结果如下图2所示。

图2

代码的图片版如下:

如果你对广度优先算法原理还有疑问,可以研究一下《图解算法:像小说一样有趣的算法入门书》中的第6章:广度优先搜索,绝对会让你搞明白!

本文分享自微信公众号 - 完美Excel(excelperfect)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Excel应用实践04:分页单独打印Excel表中的数据

    在实际工作中,我们经常会遇到想将工作表中的数据(如下图1所示的“数据”工作表)导入到固定的表格(如下图2所示)中并打印。

    fanjy
  • Excel VBA解读(138): 自定义函数时使用字节数组实现更快的字符串处理

    如果有很多行,要查找每行字符串第一个大写字母的位置,则使用数组公式会花费不少时间。

    fanjy
  • Matlab加上VBA编程,表格就能画画了

    之前学习Matlab是为了参加一个数学建模的比赛,但是在慢慢的学习当中发现了matlab这款软件是真的有趣,真的非常有用,大家没事也可以去学习一下使用matla...

    FB客服
  • Excel VBA解读(135): 影响工作表公式中运用自定义函数效率的Bug及解决方法

    在前面的两篇文章中,我们通过简单地修改VBA代码来使自定义函数运行得更快。本文将聚焦于Excel中会影响到自定义函数的Bug,并探讨如何避免它们。

    fanjy
  • Excel VBA解读(134): 使用Excel函数提高自定义函数的效率

    在上篇文章中,我们展示了自定义函数有效的方式是通过将单元格区域读取到Variant型数组来传递单元格区域数据。本文将介绍在自定义函数中最有效的方式是使用Exce...

    fanjy
  • Excel VBA解读(137): 让使用用户定义函数的数组公式更快

    Excel数组公式能够做很多令人惊讶的事情。除了在输入完后要按Ctrl+Shift+Enter组合键外,与普通公式一样。本文主要研究使用用户定义函数的数组公式。

    fanjy
  • Excel应用实践03:使用Excel进行个人计划执行记录与统计分析

    一转眼,2019年已至4月,自从年初立下flag后,便努力朝着实现它的方向奔跑。有些执行得很好,比如每天更新完美Excel微信公众号,坚持每天学习,而有些则还没...

    fanjy
  • VBA实用小程序50: 在指定的单元格中插入指定的形状

    下面的自定义函数使用Shapes集合对象的AddShape方法及其参数,可以在指定的单元格中插入指定的形状。

    fanjy
  • Excel应用实践06:进行多条件统计

    这是在知乎上看到的一个问题,我试着用VBA来解决。欢迎大家就自已使用Excel中遇到的问题或想要的解决方案提问,我将尽力解答。

    fanjy
  • Excel VBA解读(143): 在自定义函数中使用整列引用时,如何更有效率?

    Excel用户经常发现在公式中使用整列的引用很方便,这样可避免每次添加新数据时都必须调整公式。因此,当编写用户自定义函数时,可能会使用:

    fanjy

扫码关注云+社区

领取腾讯云代金券