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