图的广度优先搜索--python实现
程序员文章站
2022-03-14 09:16:43
...
最近在看《算法图解》,第六章中的广度优先搜索中的题目。自己实现一遍,算是做个记录吧。
关系网络图如下:
目的:找到朋友与朋友的朋友这些人中,谁是 Seller。
大体思路: 首先使用散列表实现图中关系,然后按关系的远近(关系梯度),按顺序将人名字放着一个队列里,最后按队列一个个 判断是不是我们要找的人。
结果:找到朋友中的 Seller,或者搜索队列变空,你的关系网中没有 Seller。
代码实现:
# -*-coding:utf-8-*-
from collections import deque
#用散列表实现图
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["alice"] = ["peggy"]
graph["bob"] = ["anuj", "peggy"]
graph["claire"] = ["thom", "jonny"]
graph["peggy"] = []
graph["anuj"] = []
graph["thom"] = []
graph["jonny"] = []
# 搜索朋友里面谁是 seller
def search(name):
#创建搜索队列
search_queue = deque()
#初始化搜索队列
search_queue += graph[name]
#记录已经搜索过的人
searched = []
#只要队列不空就一直搜索
while len(search_queue) > 0:
#取出队列中最先加进去的一个人
person = search_queue.popleft()
# 只有他没有被搜索过才进行搜索
if not person in searched:
# 查看是不是seller
if person_is_seller(person):
print(person + " is a seller")
return True
else:
# 不是seller,所以将他的朋友都加入搜索队列
search_queue += graph[person]
# 标记这个人已经被搜索过了
searched.append(person)
return False
# 判定是不是seller,规则是名字以 m 结尾就是 Seller
def person_is_seller(person):
if person[-1] == "m":
return True
else:
return False
# 测试
search("you")
上一篇: JavaSE——装饰流