BFS应用：图的遍历

#创建图,用字典，用list是不是也行？不行
graph={}
graph['you']=['alice','bob','claire']
graph['bob']=['anju','peggy']
graph['alice']=['peggy']
graph['claire']=['thon','jonny']
graph['anju']=[]
graph['peggy']=[]
graph['thon']=[]
graph['jonny']=[]
#BFS：while队不空，出队，如果队首是要找的名字，return，否则，结点val（邻居）入队,先试试用列表吧
def isMangoSaler(node_name,name):
    if node_name==name:
        return True
    else:
        return False
def BFS(start_node):
    list_BFS=[start_node]
    while list_BFS!=[]:
        name=list_BFS.pop(0)
        if isMangoSaler(name,'thon'):
            return True
        else:
            for i in graph[name]:
                list_BFS.append(i)
    return False
print BFS('you')

《算法图解》P85,这里用list当做deque，然后用pop（0）和append出队入队，一样能用。然后加上去重。

graph['you']=['alice','bob','claire']
graph['bob']=['anju','peggy']
graph['alice']=['peggy']
graph['claire']=['thon','jonny']
graph['anju']=[]
graph['peggy']=[]
graph['thon']=[]
graph['jonny']=['you']
#BFS：while队不空，出队，如果队首是要找的名字，return，否则，结点val（邻居）入队,先试试用列表吧,
# 标记已经遍历过的结构，可以用，一个list去记录。也可以
def isMangoSaler(node_name,name):
    if node_name==name:
        return True
    else:
        return False
def BFS(start_node):
    list_visit=[]
    list_BFS=[start_node]
    while list_BFS!=[]:
        name=list_BFS.pop(0)
        if name in list_visit:
            pass
        else:
            list_visit.append(name)
            if isMangoSaler(name,'thon'):
                return True
            else:
                for i in graph[name]:
                    list_BFS.append(i)
    return False
print BFS('you')