使用Python实现广度优先搜索

图
图模拟一组连接，由节点和边组成，一个节点可能与众多节点直接相连，这些节点被称为邻居。

广度优先搜索
广度优先搜索是一种图算法，主要解决两种问题：
       1.从节点A出发，有前往节点B的路径吗？
       2.从节点A出发，前往节点B的哪条路径最短？


芒果销售商问题
假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他，而找这个销售商最好的办法就是在你的关系网中寻找，下面使用广度优先搜索实现这个问题：

[Python] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

from collections import deque     def do_map():     """实现图"""     graph = dict()     graph["you"] = ["zhangsan", "lisi", "wangwu"]     graph["zhangsan"] = ["xiaoming", "xiaohong"]     graph["lisi"] = ["liniu", "you"]     graph["wangwu"] = ["wangniu", "mango"]     graph["xiaoming"] = []     graph["xiaohong"] = []     graph["liniu"] = []     graph["wangniu"] = []     graph["mango"] = []       return graph     def check_person(person):     """检查是否是销售商"""     if person == 'mango':   # 给一个简单的条件，只要名字是mango的就是销售商         return True     return False     def search(name, graph):     """广度优先搜索-销售商"""     search_queue = deque()  # 创建队列     search_queue += graph[name]  # 将一度关系加入队列       searched = []  # 准备一个已经搜寻过销售商的列表       # 只要队列不为空，     while search_queue:         person = search_queue.popleft()  # 取出第一个人           # 判断该人是否已经检查过了         if person not in searched:             # 判断该数据是否是要搜索的销售商             if check_person(person):                 print('%s is a mango seller' % person)                 return True               else:                 # 不是，将这个人的朋友即二度关系加入队列                 search_queue += graph[person]                   # 将这个人标记为检查过                 searched.append(person)       # 队列查完都没有就说明没找到     return False     if __name__ == '__main__':     graph = do_map()     print(search('you', graph))

更多技术资讯可关注：gzitcast