广度优先搜索

一种用来解决最短路径的算法。这个最短不是时间或者距离的最短而是边最少。欢聚话说就是做地铁的时候换乘最少。

图简介

图有节点和边组成，一个节点可能有很多节点与之相连，它们成为邻居。

查找最短路径

我们现在加入你想找个朋友帮忙代购一台电脑，于是你就在朋友圈里寻找，然后求助你的朋友让他们在各自的朋友圈帮你查找。于是知道找到为你代购的人。你的朋友就是一维关系，你朋友的朋友属于二维关系，等等。当然离你越近的说明路径就最短，关系就最近，越能帮你代购东西。

图.jpg

设计思路

我们先把自身的一维关系列出来，这里是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的路径，有的话是找出最短路径
• 需要按加入顺序检查搜索列表中的人，否则找到的不是最短路径
• 对于检查过的节点不要在去检查，否则会造成循环。