BFS 广度优先搜索缩写,bfs广度优先搜索全称
1.BFS算法框架BFS:适用于搜索最短路径，如：求一棵二叉树的最小深度、最小步数和最小交换数，一般用队列，其空间复杂度远大于DFS。DFS:适用于搜索所有解，比如：求最短距离，一般用def BFS(start，Target): 计算从起点到目标的最短距离 q=[] # queue，First-in 先进先出visited={} #避免返回q.append(start) #将起点添加到visited队列中add(start) step=0 #记录扩散步骤的数量，同时Q:for I in range(len(Q)):cur=Q . pop()#确定是否到达终点，如果cur==target: return step #将与cur相邻的节点添加到队列中for j in cur.adj():如果j不在visited队列中：q.insert (0，j) # Queue: FIFO visited.add(j) #更新步骤数step=1 二叉树111的最小深度。二叉树的最小深度
给定一棵二叉树，求其最小深度。
最小深度是从根节点到最近的叶节点的最短路径上的节点数。
注意：叶节点是指没有子节点的节点。
输入：root=[3，9，20，null，null，15，7]
示例2:
输入：root=[2，null，3，null，4，null，5，null，6]
树中节点数量的范围是[0，105]
-1000=节点值=1000
解决方案：
#二叉树节点的定义。
#类TreeNode:
# def __init__(self，val=0，left=None，right=None):
# self.val=val
# self.left=left
# self.right=right
类别解决方案：
def minDepth(self，root: TreeNode) - int:
如果不是根：返回0
q=[root]
步骤=1
一边问：
大小=长度(q)
对于范围内的I(尺寸):
node=q.pop(0)
#判断是否到达终点，以及结束条件
如果node.left==None且node.right==None:
返回步骤
#将相邻节点添加到队列中
if node.left！=无：
附加(node.left)
if node.right！=无：
附加(node.right)
#更新步骤
步骤=1
返回步骤
if __name__==__main__ :
# root=[3，9，20，null，null，15，7]
root=TreeNode(3)
node1=TreeNode(9)
node2=TreeNode(20)
node3=TreeNode(15)
node4=TreeNode(7)
root.left=node1
root.right=node2
节点2.left=节点3
node2.right=node4
s=解决方案()
print(s.minDepth(root))
3.二叉树的序列遍历
102.二叉树的序列遍历
给出你的二叉树的根节点root，并返回其节点值的序列遍历。(即从左到右逐层访问所有节点)。
示例1:
输入：root=[3，9，20，null，null，15，7]
产出：[[3]、[9，20]、[15，7]]
示例2:
输入：root=[1]
输出：[[1]]
示例3:
输入：root=[]
输出：[]
树中的节点数在[0，2000]范围内
-1000=节点值=1000
解决方案：
#二叉树节点的定义。
#类TreeNode:
# def __init__(self，val=0，left=None，right=None):
# self.val=val
# self.left=left
# self.right=right
类别解决方案：
def levelOrder(self，root: TreeNode) - List[List[int]]:
如果root==None:
return []
q=[root]
res=[]
一边问：
Level=[] #记录每个级别节点的值
对于范围内的I(len(q)):
node=q.pop()
level.append(节点.值)
#表示这个节点没有左右节点。
如果node.left==None且node.right==None:
继续
if node.left！=无：
q.insert(0，node.left)
if node.right！=无：
插入(0，node.right)
#将每层的结果添加到res
资源追加(级别)
返回资源
4.打开转盘锁。
52.打开转盘锁。
你有一个带四个圆形指轮的转盘锁。每个拨轮有10个数字：“0”、“1”、“2”、“3”、“4”、“5”、“6”、“7”、“8”、“9”。每个指轮都可以自由旋转：例如，将“9”改为“0”，将“0”改为“9”。每次旋转只能旋转一个拨号盘的一个数字。
锁的初始数字是“0000”，一个代表四个指轮的数字的字符串。
deadends列表包含一组死亡数字。一旦拨号盘的号码与列表中的任何元素相同，锁将被永久锁定，不能再次旋转。
Target表示可以解锁的数字。您需要给出解锁所需的最小旋转次数。如果无论如何都无法解锁，返回-1。
示例1:
input:dead ads=[ 0201 ， 0101 ， 0102 ， 1212 ， 2002]，target= 0202
可能的移动顺序是‘0000’-‘1000’-‘1100’-‘1200’-‘1201’-‘1202’-‘0202’。
请注意，序列“0000”-“0001”-“0002”-“0102”-“0202”无法解锁，
因为这个锁会在拨‘0102’的时候被锁住。
示例2:
输入：dead ads=[ 8888 ]，target=0009
说明：将最后一位数字反方向旋转一次，旋转到‘0000’-‘0009’。
示例3:
input:dead ads=[ 8887 ， 8889 ， 8878 ， 8898 ， 8788 ， 8988 ， 7888 ， 9888]，target= 888
输出：-1
说明：无法旋转到目标数，未锁定。
1=deadends.length=500
死路一条。长度==4
目标长度==4
目标不在死胡同中
而目标消音[I]仅由几个数字组成。
解决方案：
类别解决方案：
def openLock(self，dead ads:List[str]，target: str) - int:
if target==0000 :
返回0
Visited={0000} #记录用尽的密码，以防止返回。
q=[0000]
步骤=0 #步数
一边问：
对于范围内的I(len(q)):
num=q.pop()
#如果恰好是目标就退出
如果数量==目标：
返回步骤
如果数量减少：
继续
#切换密码锁以将一个节点的未遍历的相邻节点添加到队列中。
对于范围(4)中的j:
#拨号上网
up=self.plus_one(num，j)
#向下拨号
down=self.minus_one(num，j)
#如果已经访问过，就不要添加到已访问过。
如果未访问：
q.insert(0，向上)
visited.add(up)
如果down不在访问中：
q.insert(0，向下)
visited.add(向下)
#增加步数
步骤=1
返回-1
def plus_one(self，num，j):
a=列表(数量)
如果a[j]==9 :
a[j]=0
否则：
a[j]=str(int(a[j]) 1)
返回“”。加入(a)
def minus_one(self，num，j):
a=列表(数量)
如果a[j]==0 :
a[j]=9
否则：
a[j]=str(int(a[j]) -1)
返回“”。加入(a)
参考：BFS算法框架例程详解
5.钥匙和房间
81.钥匙和房间
有n个房间，房间从0到n-1编号。最初，除了0号房间，所有房间都是锁着的。你的目标是进入所有的房间。但是，没有拿到钥匙，你不能进入锁着的房间。
当你进入一个房间时，你可能会发现里面有一套不同的钥匙。每把钥匙都有对应的房间号，也就是说钥匙可以打开的房间。你可以用所有的钥匙打开其他房间。
给你一个房间数组，其中rooms[i]是当你进入房间I时可以得到的一组钥匙，如果所有房间都可以进入，返回true，否则返回false。
示例1:
输入：房间=[[1]，[2]，[3]，[]]
输出：真
让我们从0号房间开始，得到1号钥匙。
然后我们去了1号房间，拿到了2号钥匙。
然后我们去2号房间拿3号钥匙。
最后，我们去了3号房间。
因为我们能够进入每个房间，所以我们返回true。
示例2:
输入：房间=[[1，3]，[3，0，1]，[2]，[0]]
输出：假
说明：我们进不了2号房间。
n==房间.长度
2=n=1000
0=房间[i]。长度=1000
1=总和(房间数[i])。长度)=3000
0=房间[i][j] n
所有房间[i]的值互不相同。
解决方案：
类别解决方案：
def canvisitollrooms(self，rooms: List[List[int]]) - bool:
Visited={0} #记录已用尽的键，防止返回。
队列=[0]
排队时：
index_keys=queue.pop()
对于i in rooms[index_keys]:
如果我没有被访问：
visited.add(i)
queue.insert(0，I)
返回len(已访问)==len(房间)
对于这个问题，您也可以使用DFS，只需用queue.append替换queue.insert
参考：7行DFS 8行BFS，两种方法，三种方式实现超细节趣味，0基础解Python
6.BFS遍历图
# -编码：utf-8 -
def bfs(_graph，s):
Bf遍历图
:参数图形：图形
:param s:从哪个点开始遍历？
:返回：
q=[s]
已访问={s}
一边问：
vertex=q.pop()
nodes=_ graph[顶点]
对于节点中的节点：
如果节点未被访问：
visited.add(节点)
q.insert(0，节点)
打印(顶点)
if __name__==__main__ :
# Graph可以抽象成一个字典，key代表当前节点，value是该节点的下一个节点集。
图形={
A: [B ， C]，
B: [A ， C ， D]，
C: [A ， B ， D ， E]，
D: [B ， C ， E ， F]，
E: [C ， D]，
F: [D]，
Bfs(图， A) #从A点开始，输出A，B，C，D，E，f。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。