宽度优先搜索算法总结
在DSF和BSF之间，BSF可以尽可能地使用BSF算法。 这是因为DSF的递归算法使用了堆栈，但堆栈的深度有限制。 python的上限是1000。 否则，导致堆栈溢出的DSF主要借用堆栈来实现递归算法，而BSF使用队列尽可能多地构建两端队列(deque )来实现算法的目的。 由于使用queue涉及多线程锁，因此对于BSF使用较慢的场景，连接块问题、层次遍历问题和拓扑排序问题BSF在初始化构建队列(deque )时，始终会遍历访问日志BSF模板结构
-1.初始化队列(deque )和访问日志
-2.while循环访问队列pop队列中的每个节点for循环访问此pop出站节点的邻居节点
-3.确定节点的相邻节点是否已被访问
-4.如果邻居节点未被访问，将其添加到队列中，并将邻居节点记录在访问记录中
#！ /usr/稳健火/env python #-- coding : utf-8-- * ' ' bfs算法模板' ' '导入收集' ' # step 1:初始化#注意每次加入队列时，node都会逐一发出distance={node : 0} #以记录队列中的节点是否被访问。 ' ' # step2:不断访问队列。 # while循环每次都会出现pop队列中的一个点。 如果“”while queue: #队列未被访问，则继续访问node=queue.popleft(# )。 for neighbor in node.get_neighbor ) ) : # )节点旁边的节点if neighbor in distance: # (如果已访问此邻居) 同样，在这里queue和标记决不分离。 进入队列后，标记将立即被访问。 否则，就会产生重复元素。 距离[ neighbor ]=distance [ node ]1#如果邻居节点未被访问，它将记录在距离中，然后加上访问消耗queue.append(neighbor ) 示例) ) # ex1: cloneGraph# )等待定义主函数defclonegraph ) self。 节点) : # step 1: findnodesnodes=self.find _ nodes _ by _ bfs (node ) step 2: copynodesmapping=self.copping 映射(返回映射[node] def find _ nodes _ by _ bfs ) node ) :queue=collections.deque ) [ node ] visited wile queue 3360 curt _ node=queue.pop left (forneighorincurt _ node.neig hors 3360 ifneighborinvisited 3360 continuevivion )可视) defcopy_nodes ) self， nodes (3360 mapping={ } fornodeinnodes 3360 mapping [ node ]=undirectedgraphnode (node.label ) returnmappingdefcopy_ ) returnmappingdefcopy mapping (: fornodeinnnodes 360 new _ ) forneighborinnode.neighbors 3360 new _ neighbor=mapping ) ) neighbor new _ node.neighbors.append (new _ neighbor ) # end，dict ) :DICT.add(end ) queue=collections.deque ([开始] ) visited=set (开始) ) distance=0while queque
word = queue.popleft() if word == end: return distance for next_word in self.get_next_words(word, dict): if next_word in visited: continue visted.add(next_word) queue.append(next_word) return 0def get_next_words(self, word, dict): next_words = [] for i in range(len(word)): left, right = word[:i], word[i+1:] for char in 'abcdefghijklmnopqrstuvwxyz': if word[i] == char: continue new_word = left + char + right if new_word in dict: next_words.append(new_word) return next_words# ex3: number of IslandsDIRECTIONS = [(1,0),(0,1),(0,-1),(-1,0)]class Solution: def numIslands(self, grid): # 特殊情况处理 if not grid or not grid[0]: return 0 islands = 0 visited = set() for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] and (i,j) not in visited: self.bfs(grid, i, j, visited) island += 1 return islands def bfs(self, grid, i, j, visited): queue = collections.deque((x,y)) visited.add((x,y)) while queue: x, y = queue.popleft() for delta_x, delta_y in DIRECTIONS: next_x = x + delta_x next_y = y + delta_y if not self.is_valid(grid, next_x, next_y, visited): continue visited.add((next_x, next_y)) def is_valid(self, grid, x, y, visited): n, m = len(grid), len(grid[0]) # 如果出界，返回False if not (0<= x <n and 0<= y <m): return False # 如果已经bsf过，不要再次bsf if (x,y) in visited: return False # 如果是1，为true，反之为false return grid[x][y]# ex4: Knight shortest PathOFFSETS = [(-2,-1),(-2,1),(-1,2),(1,2), (2,1),(2,-1),(1,-2),(-1,-2)]class Solution1: def shortestPath(self, grid, source, destination): queue = collections.deque(source.x, source.y) disToSrcMap = {(source.x, source.y): 0} while queue: x, y = queue.popleft() if (x, y) == (destination.x, destination.y): return disToSrcMap[(x,y)] for dx, dy in OFFSETS: next_x, next_y = x + dx, y + dy if not self.is_valid(next_x, next_y, grid): continue if (next_x, next_y) in disToSrcMap: continue queue.append((next_x, next_y)) disToSrcMap[(next_x, next_y)] = disToSrcMap[(x,y)] + 1 return -1 def is_valid(self, x, y, grid): n, m = len(grid), len(grid[0]) if x < 0 or x >= n or y <0 or y>=m: return False else: return True# ex5: course schedule iidef findOrder(self, numCourses, prerequisites): graph = [[] for i in range(numCourses)] # 1. 统计每个点的入度 in_degree = [0] * numCourses for node_in, node_out in prerequisites: graph[node_out] = node_in in_degree[node_out] += 1 # 2.每个入度为0的点放入队列作为起始点 queue = collections.deque() for i in range(len(in_degree)): if in_degree[i] == 0: queue.append(i) # 记录已修课程 num_choose = 0 # 记录拓扑顺序 topo_order = [] # 3.顺序查找队列课程 while queue: now_pos = queue.popleft() topo_order.append(now_pos) num_choose += 1 for next_pos in graph[now_pos]: in_degree[next_pos] -= 1 if in_degree[next_pos] == 0: queue.append(next_pos) return topo_order if num_choose == numCourses else []# ex6: topological sortingclass Solution2: def topSort(self, graph): #1.统计每个点的入度 node_to_indegree = self.get_indegree(graph) #2.将每个入度为0的点放入队列 start_node = [x for x in graph if node_to_indegree[x] == 0] queue = collections.deque(start_node) # 记录拓扑顺序 order = [] #3. 不断从队列中拿出点 while queue: node = queue.popleft() order.append(node) for neighbor in node.neighbors: node_to_indegree[neighbor] -= 1 if node_to_indegree[neighbor] == 0: queue.append(neighbor) return order def get_indegree(self, graph): node_to_indegree = {x:0 for x in graph} for node in graph: for neighbor in node.neighbors: node_to_indegree[neighbor] += 1 return node_to_indegree