一种用来解决最短路径的算法。这个最短不是时间或者距离的最短而是边最少。欢聚话说就是做地铁的时候换乘最少。
图简介
图有节点和边组成,一个节点可能有很多节点与之相连,它们成为邻居。
查找最短路径
我们现在加入你想找个朋友帮忙代购一台电脑,于是你就在朋友圈里寻找,然后求助你的朋友让他们在各自的朋友圈帮你查找。于是知道找到为你代购的人。你的朋友就是一维关系,你朋友的朋友属于二维关系,等等。当然离你越近的说明路径就最短,关系就最近,越能帮你代购东西。
设计思路
我们先把自身的一维关系列出来,这里是bill的一维关系是jack ,robin, calm,然后分别找出他们三个的一维关系也就是bill的二维关系。
代码实现
class Friend:
def __init__(self, name, canBuy):
self.name = name
self.canBuy = canBuy
robin = Friend('robin', True)
jack = Friend('jack', False)
calm = Friend('calm', False)
jessica = Friend('jessica', True)
rose = Friend('rose', False)
calvin = Friend('calvin', True)
graph = {}
graph['bill'] = [robin, jack, calm]
graph['robin'] = [calvin]
graph['jack'] = []
graph['calm'] = [jessica]
graph['jessica'] = []
graph['rose'] = []
graph['calvin'] = []
def searchName(name):
searchQue = graph[name]
searched = []
while searchQue:
person = searchQue.pop(0)
if person not in searched:
if person.canBuy:
return person
else:
name = person.name
searchQue += graph[name]
searched.append(person)
print searchName('bill').name
特点
- 广度优先搜索是否有从A-B的路径,有的话是找出最短路径
- 需要按加入顺序检查搜索列表中的人,否则找到的不是最短路径
- 对于检查过的节点不要在去检查,否则会造成循环。