宽度优先搜索算法总结
- 在DSF和BSF之间，能用BSF尽量用BSF算法，因为DSF的递归算法使用到了栈，而栈的深度是有限制的，在python中的上限是1000，否则会导致栈溢出
- DSF主要借用栈来实现递归算法，而BSF则是使用队列来实现
- BSF尽量构建双端队列（deque）来实现算法目的，因为用queue会涉及多线程加锁导致变慢
- BSF使用的场景包括：连通块问题，层级遍历问题和拓扑排序问题
- BSF在初始化构建队列（deque）时，一定要绑定构建访问记录
BSF模版结构：
-1. 初始化队列（deque）和访问记录
-2.while循环访问队列+每次pop队列中一个节点+for循环访问的这个pop出节点的邻居节点
-3.判断节点邻居节点是否被访问
-4.若邻居节点未被访问，添加到队列中并将该邻居节点记录到访问记录中
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
BFS算法模版
"""
import collections
"""
# step1:初始化
# 注意：这个queue和标记永不分离，一旦进入队列，立刻要被标记已被访问
"""
queue = collections.deque() # 定义一个双端队列，保证每次加入队列的node会一个个出
distance = {node : 0} # 用来记录队列中的节点是否被访问
"""
# step2: 不断访问队列
# while循环+每次pop队列中的一个点出来
"""
while queue: # 如果队列没被访问完就继续访问
node = queue.popleft() # 从队列的左边一个个提出来
for neighbor in node.get_neighbor(): # 依次找到节点的邻居节点
if neighbor in distance: # 如果这个邻居节点已被访问，则跳过
continue
# 注：同上，这里queue和标记永不分离，一旦进入队列，立刻要被标记已被访问，否则会有重复元素出现
distance[neighbor] = distance[node] + 1 # 如果邻居节点没被访问，则记录到distance中，并加*问消耗
queue.append(neighbor) # 最后将没访问的邻居节点加入队列中，等待访问这个邻居节点
"""
#样例
"""
# ex1: cloneGraph
# 定义主函数
def cloneGraph(self, node):
# step 1: find nodes
nodes = self.find_nodes_by_bfs(node)
# step 2: copy nodes
mapping = self.copy_nodes(nodes)
# step 3: copy edges
self.copy_edges(nodes, mapping)
return mapping[node]
def find_nodes_by_bfs(node):
queue = collections.deque([node])
visited = set([node])
while queue:
curt_node = queue.popleft()
for neighor in curt_node.neighors:
if neighbor in visited:
continue
visited.add(neighbor)
queue.append(neighbor)
return list(visited)
def copy_nodes(self, nodes):
mapping = {}
for node in nodes:
mapping[node] = UndirectedGraphNode(node.label)
return mapping
def copy_edges(self, nodes, mapping):
for node in nodes:
new_node = mapping[node]
for neighbor in node.neighbors:
new_neighbor = mapping(neighbor)
new_node.neighbors.append(new_neighbor)
# ex2: Word Ladder
def ladderLength(self, start, end, dict):
dict.add(end)
queue = collections.deque([start])
visited = set([start])
distance = 0
while queue:
distance += 1
size = len(queue)
for i in range(size):
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 0
def 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 Islands
DIRECTIONS = [(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 Path
OFFSETS = [(-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 ii
def 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 sorting
class 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