本帖最后由 yangrui 于 2019-1-10 14:03 编辑
图
图模拟一组连接,由节点和边组成,一个节点可能与众多节点直接相连,这些节点被称为邻居。
广度优先搜索
广度优先搜索是一种图算法,主要解决两种问题:
1.从节点A出发,有前往节点B的路径吗?
2.从节点A出发,前往节点B的哪条路径最短?
芒果销售商问题
假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他,而找这个销售商最好的办法就是在你的关系网中寻找,下面使用广度优先搜索实现这个问题:
[Python] 纯文本查看 复制代码 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))
|