广度优先搜索 python_【python刷题】广度优先搜索（BFS）

一般来说，BFS使用的数据结构是队列。

BFS模板

from collections import deque

def BFS(start, target):

q = deque() # 核心数据结构

visited = set() # 避免走回头路

q.append(start) # 将起点加入到队列

visited.add(start)

step = 0 # 记录扩散的步数

while q is not None:

s = len(q)

for i in range(s):

cur = q.popleft() # 删除队列首元素

if cur == target:

return step

for x in adj[cur]: # adj的键为cur，值是一个列表，表示与cur相邻的节点

if x not in visited:

q.append(x)

visited.add(x)

step += 1

leetcode 111 二叉树的最小深度

class Solution:

def minDepth(self, root: TreeNode) -> int:

if not root:

return 0

from collections import deque

queue = deque()

queue.append(root)

depth = 0

while queue:

depth = depth + 1

l = len(queue)

for i in range(l):

t = queue.popleft()

if not t.left and not t.right:

return depth

if t.left:

queue.append(t.left)

if t.right:

queue.append(t.right)

递归方法

class Solution:

def minDepth(self, root: TreeNode) -> int:

if not root: return 0

if not root.left: return self.minDepth(root.right) + 1

if not root.right: return self.minDepth(root.left) + 1

return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

leetcode 752 打开转盘锁

class Solution:

import copy

def openLock(self, deadends: List[str], target: str) -> int:

from collections import deque

target = list(map(lambda x: int(x), list(target)))

deadends = [list(map(lambda x: int(x), list(deadend))) for deadend in deadends]

queue = deque()

queue.append([0,0,0,0])

visited = []

visited.append([0,0,0,0])

step = 0

while len(queue) != 0:

l = len(queue)

for i in range(l):

cur = queue.popleft()

if cur in deadends:

continue

if cur == list(target):

return step

for j in range(4):

up = self.plusOne(cur, j)

down = self.subOne(cur, j)

if up not in visited:

queue.append(up)

visited.append(up)

if down not in visited:

queue.append(down)

visited.append(down)

step += 1

return -1

def plusOne(self, s, i):

s = copy.deepcopy(s)

if s[i] == 9:

s[i] = 0

else:

s[i] += 1

return s

def subOne(self, s, i):

s = copy.deepcopy(s)

if s[i] == 0:

s[i] = 9

else:

s[i] -= 1

return s

我们进行优化，使用双向BFS，使用这种优化方法我们需要知道最终的终点在哪。

class Solution:

import copy

def openLock(self, deadends: List[str], target: str) -> int:

target = list(map(lambda x: int(x), list(target)))

deadends = [list(map(lambda x: int(x), list(deadend))) for deadend in deadends]

q1 = []

q2 = []

q1.append([0,0,0,0])

q2.append(target)

visited = []

step = 0

while len(q1) != 0 and len(q2) != 0:

tmp = []

for cur in q1: # 将q1中的元素进行扩散

if cur in deadends:

continue

if cur in q2:

return step

visited.append(cur)

# 将一个节点的未遍历邻居加入到visited

for j in range(4):

up = self.plusOne(cur, j)

down = self.subOne(cur, j)

if up not in visited:

tmp.append(up)

if down not in visited:

tmp.append(down)

step += 1

q1 = q2 # 这里交换q1和q2，下一轮扩散的是q2

q2 = tmp

return -1

def plusOne(self, s, i):

s = copy.deepcopy(s)

if s[i] == 9:

s[i] = 0

else:

s[i] += 1

return s

def subOne(self, s, i):

s = copy.deepcopy(s)

if s[i] == 0:

s[i] = 9

else:

s[i] -= 1

return s