Python-广度优先搜索

如图所示：

 

以此图为例寻找末尾为“m”的名称。这里使用广度优先搜索，这个可以回答两类问题：

第一类问题：从节点A出发，有前往节点B的路径吗？

第二类问题：从节点A出发，前往节点B的哪条路径最短？

那这里其实就是寻找末尾为“m”名称的最短路径。

from collections import deque   def person_is_seller(name):     return name[-1] == ‘m‘  graph = {} graph["you"] = ["alice", "bob", "claire"] graph["bob"] = ["anuj", "peggy"] graph["alice"] = ["peggy"] graph["claire"] = ["thom", "jonny"] graph["anuj"] = [] graph["peggy"] = [] graph["thom"] = [] graph["jonny"] = []  def search(name):     search_queue = deque()     search_queue += graph[name]     searched = []     while search_queue:         person = search_queue.popleft()         if person not in searched:             if person_is_seller(person):                 print(person + ‘ is a mongo seller‘)                 return True             else:                 search_queue += graph[person]                 searched.append(person)     return False  search("you")

这里使用到了散列表的概念，以及Python中deque函数来创建一个双端队列。 

查看更多关于Python-广度优先搜索的详细内容...