1. BFS是干嘛的？ -- 解决异地恋乘车转车次数最少的问题，啊呸~
- BFS是一种[盲目搜索是盲目搜索法，目的是系统地展开并检查中的所有节点，以找寻结果。
举个栗子：假设从A城市到B城市有多种转车方案，用广度优先算法计算出那条路线的转车次数最少。[这个例子还要用在后面的狄克斯特拉算法]
2. 下面就来用算法解决这个问题：
本人觉得这个算法最重要的是教会一种表示图的方法
image.png- 我们如何用代码表示上面的图呢？
先表示城市吧？
city['A'] = ['E', 'D']
city[‘E’] = ['F', 'G']
city[‘D’] = ['G', 'H']
city['F'] = ['G', 'B_love']
city[‘G’] = ['B_love']
city['H'] = ['B_love']
city['B'] = []
这样就表示了城市的关系。
接下来，我们要做的就是搜索所有的节点，如果该节点满足以“love”结尾，则表示可以到达该城市.- 当然要从自己所在的城市向外找 仔细规划下寻妻之旅吧：
你带着一个本子记下A，A城市可以看见连着E,D两座城市,然后你再在本子上列下 E, F；
找完A，很显然不是有love的城市，所以你在本子上划掉了A城市；
你在找E的时候，看见了E的城市连着 F, G, 所以你决定找完D之后，去找F,G,所以你在本子下记下来F,G 。
找D的城市看见了G,H; 所以你在本子下,划掉D, 列下G,H 。 （这里当你找到G的时候，发现以前去过，所以你决定不去找G了）
这样，一直找下去，直到你找到B城市。
本子代表了队列
3. Talk is cheap, show me the code
# 广度优先算法
from collections import deque
city = dict()
city["A"] = ["E", "D"]
city["E"] = ["F", "G"]
city["D"] = ["G", "H"]
city["F"] = ["G","B_LOVE"]
city["G"] = ["B_LOVE"]
city["H"] = ["B_LVOE"]
city["B_LOVE"] = []
def BFSearch(startCity):
searched = [] # 存放已经查找过的城市
search_queen = deque()
search_queen += city[startCity]
while search_queen:
print(search_queen)
cityname = search_queen.popleft()
if not cityname in searched:
if isCityB(cityname):
print(cityname + " here her is ... ")
return True
else:
searched.append(cityname) # 添加已经搜查过的节点
search_queen += city[cityname] #如果不是正确的节点，则添加该节点的子节点到搜查的队列中
return False
def isCityB(name):
return name[-4:] == 'LOVE' #截取后四位 判断是否是她的城市
print(BFSearch("A"))
就这样，搜查到了符合的城市
运行结果
参考:
