图
图模拟一组连接，由节点和边组成，一个节点可能与众多节点直接相连，这些节点被称为邻居。
广度优先搜索
广度优先搜索是一种图算法，主要解决两种问题：
1.从节点A出发，有前往节点B的路径吗？
2.从节点A出发，前往节点B的哪条路径最短？
芒果销售商问题
假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他，而找这个销售商最好的办法就是在你的关系网中寻找，下面使用广度优先搜索实现这个问题：
|
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 dequedef 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 graphdef check_person(person): """检查是否是销售商""" if person == ‘mango‘: # 给一个简单的条件，只要名字是mango的就是销售商 return True return Falsedef 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 Falseif __name__ == ‘__main__‘: graph = do_map() print(search(‘you‘, graph)) |
原文：https://www.cnblogs.com/heimaguangzhou/p/11590714.html