基础扩展 | 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章：广度优先搜索，绝对会让你搞明白！