[Leetcode]BFS广度优先搜索——python版本

[Leetcode]BFS广度优先搜索——python版本

本篇文章根据labuladong的算法小抄介绍BFS的常见算法，采用python3实现

文章目录

简介二叉树的最小深度，T111解开密码锁的最小次数，T752双向BFS优化

简介

BFS框架：把问题抽象成图，从一个点开始向四周扩散。一般用队列这种数据结构，每次将一个节点周围的所有节点加入队列。对二叉树而言，BFS实际上就是层级遍历。

DFS框架：就是回溯算法。

区别：BFS找到的路径一定是最短的，但代价是空间复杂度可能比DFS大很多。一般在找最短路径时用BFS，其他时候还是用DFS多。

BFS的应用：在一幅图中找到从起点start到终点target的最近距离。

框架：

def BFS(start,target):
    q = Queue.Queue() #核心数据结构
    visited = set() #避免走回头路
    
    q.put(start)
    visited.add(start)
    step = 0 #记录扩散步数
    while q:
        size = len(q)
        #将当前队列中的所有节点向四周扩散
        for i in range(size):
            cur = q.get()
            #到达终点
        	if cur == target:
                return step
            #添加cur的相邻节点进队列
            for x in graph[cur]:
                if not x in visited:
                    q.put(x)
                    visited.add(x)
        step += 1

二叉树的最小深度，T111

起点：root

终点：最靠近根节点的叶子节点（两个子节点都是None）

def minDepth(root):
    if not root:
        return 0
    q = collections.deque([(root,1)]) #可迭代，且为一个整体
    while q:
        node,depth = q.popleft()
        if (not node.left) and (not node.right):
            return depth
        if node.left:
            q.append([node.left,depth+1])
        if node.right:
            q.append([node.right,depth+1])
    return 0

解开密码锁的最小次数，T752

问题：转盘锁有4个拨轮，每个有10个数字（0-9）。每次只能旋转一个拨轮的一个数字。锁初始为"0000"。

列表deadends包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁就会被永久锁定。

target表示正确密码，需要给出解锁需要的最小旋转次数，如果不能解锁，返回-1

方法：每个节点代表一个密码，有8个相邻节点。

需要处理的细节：1. visited防止死循环；2. 对deadends的处理

def openLock(deadends,target):
    
    #将s[j]向上拨动一次
    def plusOne(s,j):
        if s[j] == '9':
            s[j] = '0'
        else:
            s[j] = chr(ord(s[j])+1)
        return s
    #将s[j]向下拨动一次
    def minusOne(s,j):
        if s[j] == '0':
            s[j] = '9'
        else:
            s[j] = chr(ord(s[j])-1)
        return s
    
    if (target in deadends) or ('0000' in deadends):
        return -1
    if target == "0000":
        return 0
    
    visited = set("0000")
    for x in deadends:
        visited.add(x)
    q = collections.deque([("0000",0)])

    while q:
        s,count = q.popleft()
        for i in range(4):
            up = plusOne(s,i)
            if not up in visited:
                if up == target:
                    return count + 1
                q.append((up,count+1))
                visited.add(up)
            down = minusOne(s,i)
            if not down in visited:
                if down == target:
                    return count + 1
            	q.append((down,count+1))
                visited.add(down)
    return -1

优化：可以把dead中的元素放到visited里。

双向BFS优化

双向BFS可以进一步提高算法的效率。传统的BFS框架是从起点开始向四周扩散，遇到终点时停止；双向BFS是从起点和终点同时开始扩散，当两边有交集时停止。

只有明确知道终点在哪的情况才可以使用双向BFS。

T752密码锁的优化：

def openLock(deadends,target):
    deads = set(deadends)
    q1 = set()
    q2 = set()
    visited = set()
    
    step = 0
    q1.add("0000")
    q2.add(target)
    
    while q1 and q2:
        temp = set()
        #将q1中的节点向周围扩散
    	for cur in q1:
            if cur in deads:
                continue
            if cur in q2:
                return step
            visited.add(cur)
        
        	#将一个节点的未遍历节点加入集合
            for i in range(4):
                up = plusOne(cur,i)
                if up not in visited:
                    temp.add(up)
                down = minusOne(cur,i)
                if down not in visited:
                    temp.add(down)
        step += 1
        #交换q1，q2，下一轮扩散q2
        q1 = q2
        q2 = temp