欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的广度优先搜索--python实现

程序员文章站 2022-03-14 09:16:43
...

最近在看《算法图解》,第六章中的广度优先搜索中的题目。自己实现一遍,算是做个记录吧。

关系网络图如下:

图的广度优先搜索--python实现

目的:找到朋友与朋友的朋友这些人中,谁是 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")