Python图算法之广度优先搜索

布满荆棘的人生 2022-02-20 08:56 192阅读 0赞

**图算法之广度优先搜索（breadth-first search，BFS）：**  
广度优先搜索是一种用于图的查找算法，可解决以下两类问题：  
第一类问题：从节点A出发，有前往节点B的路径吗？  
第二类问题：从节点A出发，前往节点B的哪条路径最短？

**需要两个步骤：**  
(1) 使用图来建立问题模型。(2) 使用广度优先搜索解决问题。

**什么是图：**  
图用于模拟不同的东西是如何相连的，由节点（node）和边（edge）组成。  
在广度优先搜索中，先检查一度关系（直接关系），再检查二度关系（直接关系的直接关系），以此类推，这需要一种先进先出（First In First Out，FIFO）的数据结构，队列则是这种数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。

广度优先搜索的运行时间通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。

**注意：**  
广度优先搜索一定不能重复搜索已搜索过的数据，否则可能导致无限循环搜索。

可用于类似公交换乘次数最少的案例。

**示例：查找人际关系网中关系最近的第一个水果销售商**

from collections import deque					#collections是Python内建的一个集合模块，提供了许多有用的集合类。deque是队列类，可创建一个双端队列
    
    # graph是一张以you为主体的人际关系网，值是键对应的朋友
    graph = {} 
    graph["you"] = ["alice", "bob", "claire"] 
    graph["bob"] = ["anuj", "peggy"] 
    graph["alice"] = ["peggy"] 
    graph["claire"] = ["thom", "jonny"] 
    graph["anuj"] = [] 
    graph["peggy"] = [] 
    graph["thom"] = [] 
    graph["jonny"] = [] 
    
    # 判断是否是水果商
    def person_is_seller(name):
    	return name[-1] == 'm'						#这里简单以名字最后一个字母是m的人作为水果商
    
    # 查找人际关系网中是否有水果商
    def search(name):
    	search_queue = deque() 						#创建一个队列
    	search_queue += graph[name]					#初始入队，将you的直接朋友入队
    	searched = []								#已检查过的人，防止是2个人共同的朋友被重复检查
    	while search_queue:							#如果队列不为空，则继续检查
    		person = search_queue.popleft()			#第一个出队检查
    		if not person in searched:				#防止重复检查，最糟糕时会导致无限循环检查
    			if person_is_seller(person):		#是水果商
    				print(person + '是水果商。')
    				return True
    			else: 								#不是水果商
    				search_queue += graph[person]	#将被检查人的朋友入队
    				searched.append(person)			#将检查过的人添加到已测list中，防止重复检查
    	print('你的人际关系网中无水果商。')
    	return False								#人际关系网中无水果商
    
    search('you')

**结果为：**

thom是水果商。

**示例：**  
词梯问题：在英文单词表中，有一些单词非常相似，它们可以通过只变换一个字符而得到另一个单词。比如：hive–>five；wine–>line；line–>nine；nine–>mine…，那么，就存在这样一个问题：给定一个单词作为起始单词(相当于图的源点)，给定另一个单词作为终点，求从起点单词经过的最少变换(每次变换只会变换一个字符)，变成终点单词。

from pythonds.graphs import Graph
    from pythonds.basic import Queue
    
    # 构建词梯图
    def buildGraph():
    	d = {}											#初始化单词桶字典
    	g = Graph()										#实例化图类
    	wordlist = ['fool', 'foul', 'foil', 'fail', 'fall', 'pall', 'poll', 'pool', 'cool', 'pole', 'pope', 'pale', 'page', 'sale', 'sage']		 #词表
    	# 创建由一个字母组成的单词桶
    	for line in wordlist:							#循环每个单词
    		for i in range(len(line)):					#循环每个单词的长度
    			bucket = line[:i] + '_' + line[i+1:]	#将单词转换成'_ool'样式的单词桶
    			if bucket in d:							#若单词桶字典中已有该样式的单词桶，则
    				d[bucket].append(line)				#直接向该单词桶中添加该单词
    			else:									#若单词桶字典中没有该样式的单词桶，则
    				d[bucket] = [line]					#添加单词桶及单词
    	# 为同一桶中的单词添加顶点和边
    	for bucket in d:								#循环单词桶字典中的单词桶
    		for word1 in d[bucket]:						#循环单词桶中的单词
    			for word2 in d[bucket]:					#循环取出该单词所在桶中的所有单词
    				if word1 != word2:					#若2个单词不同，则
    					g.addEdge(word1, word2)			#在2个单词间添加双向边
    	return g 										#返回词梯图
    
    # 广度优先搜索
    def bfs(g, start):
    	start.setDistance(0)							#初始化起始点的距离为0
    	start.setPred(None)								#初始化起始点的前导(父节点)为None
    	vertQueue = Queue()								#初始化队列
    	vertQueue.enqueue(start)						#入队
    	while (vertQueue.size() > 0):					#当队列不为空时循环
    		currentVert = vertQueue.dequeue()			#出队节点为当前节点
    		for nbr in currentVert.getConnections():	#循环当前节点的所有邻居节点
    			if (nbr.getColor() == 'white'):			#节点初始为白色，即若节点未被搜索(白色)，则
    				nbr.setColor('gray')				#搜索到时被设置为灰色
    				nbr.setDistance(currentVert.getDistance() + 1)	#该邻居节点距离为当前节点距离+1
    				nbr.setPred(currentVert)			#将当前节点设为该邻居节点的前导(父节点)
    				vertQueue.enqueue(nbr)				#该邻居节点入队
    		currentVert.setColor('black')		#搜索完当前节点的所有邻居节点后，将当前节点设为黑色
    
    # 回溯打印整个词梯
    def traverse(y):
    	x = y
    	while (x.getPred()):							#当该节点的前导(父节点)存在时循环
    		print(x.getId())							#打印该节点的键
    		x = x.getPred()								#将该节点的前导(父节点)设为该节点，继续循环
    	print(x.getId())								#打印根节点的键
    
    g = buildGraph()									#构建词梯图
    bfs(g, g.getVertex('fool'))							#广度优先搜索，初始顶点为'fool'
    traverse(g.getVertex('sage'))						#回溯打印整个词梯，最终顶点为'sage'

结果为：

sage
    sale
    pale
    pall
    poll
    pool
    fool