Python算法-深度优先搜索&广度优先搜索（DFS&BFS）
2021-09-13 本文已影响0人
ShowMeCoding
深度优先算法-DFS(Deep-first Search)
- 用到了递归的思想
- DFS: 从root节点开始，尽可能深的搜索一个分支，把一个分支搜索结束之后再进行下一个分支
- DFS主要应用：二叉树搜索+图搜索
- DFS和回溯算法的区别：回溯算法 = DFS + 剪枝
二叉树的遍历
144-前序遍历
- 前序遍历：根节点-左子树-右子树
- 递归+广度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorder(root:TreeNode):
# 递归的终止条件:节点上没有值
if root == None:
return
res.append(root.val)
preorder(root.left)
preorder(root.right)
res = []
preorder(root)
return res
- 栈+深度优先搜索
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
res = []
node = root
if root == None:
return res
while stack or node:
while node:
res.append(node.val)
stack.append(node)
node = node.left
node = stack.pop() # 向上寻找根节点
node = node.right # 遍历右子树
return res
94-中序遍历
- 中序遍历：左子树-根-右子树
- 递归+广度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
def inorder(root:TreeNode):
if root == None:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
res = []
inorder(root)
return res
- 栈+深度优先搜索
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack: # 栈不为空就循环
# 左子树中所有最左边的孩子进栈
while root.left:
stack.append(root.left)
root = root.left
cur = stack.pop() # 弹出一个左孩子记为当前节点，看它有没有右孩子
res.append(cur.val) # 每弹出一次记得记录一下
if cur.right: # 如果当前节点有右孩子的话，右孩子进栈，把这个右孩子当作新的根节点
stack.append(cur.right)
root = cur.right
return res
145-后序遍历
- 后序遍历：左子树-右子树-根
- 递归+广度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def posterorder(root:TreeNode):
if root == None:
return
posterorder(root.left)
posterorder(root.right)
res.append(root.val)
res = []
posterorder(root)
return res
- 栈+深度优先搜索
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
prev = None
if root == None:
return res
while root or stack:
# 遍历最左子树的的节点
while root:
stack.append(root)
root = root.left
root = stack.pop()
if not root.right or root.right == prev:
res.append(root.val)
prev = root
root = None
else:
stack.append(root)
root = root.right
return res
102-层序遍历
- 队列+广度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
deque = []
if root == None:
return res
deque.append(root)
while deque:
size = len(deque) # size控制遍历的层数
list = []
while size > 0:
cur = deque.pop(0)
list.append(cur.val)
if cur.left:
deque.append(cur.left)
if cur.right:
deque.append(cur.right)
size -= 1
res.append(list)
return res
- 方法2：深度优先搜索:一条路走到黑
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
result = []
if root is None:
return result
self.dfs(root, result, 0) # 从第零层开始
return result
def dfs(self, node, result, level):
'''
node: 当前的节点
level：当前的层数
'''
# 递归终止条件
if node is None:
return
if level > len(result)-1: # 当前的层数大于result数组的长度-1时(0>-1)
result.append([]) # 添加一个空数组，保证可以添加该层的元素
result[level].append(node.val) # 添加元素到指定的层
if node.left is not None:
self.dfs(node.left, result, level+1)
if node.right is not None:
self.dfs(node.right, result, level+1)
617-合并二叉树
- 基本思想：使用 前序遍历
- 递归+深度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
def dfs(r1, r2):
if not r1:
return r2
if not r2:
return r1
r1.val = r1.val + r2.val # 在r1上进行合并
r1.left = dfs(r1.left, r2.left)
r1.right = dfs(r1.right, r2.right)
return r1
return dfs(root1, root2)
- 栈+广度优先搜索
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1:
return root2
if not root2:
return root1
stack = [(root1, root2)]
while stack:
r1, r2 = stack.pop(0)
r1.val += r2.val
# 如果r1和r2的左子树都不为空，就放到队列中
# 如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
if r1.left and r2.left:
stack.append((r1.left, r2.left))
elif r1.left == None:
r1.left = r2.left
if r1.right and r2.right:
stack.append((r1.right, r2.right))
elif r1.right == None:
r1.right = r2.right
return root1
938-二叉搜索树的范围和
输入：root = [10, 5, 15, 3, 7, null, 18], low=7, high=15
输出：32
解释：返回值为位于[low, high]之间的所有结点的和
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
# 递归法
result = 0
if root is None: # 递归的终止条件
return 0
leftSum = self.rangeSumBST(root.left, low, high) # 左子树符合条件的和
rightSum = self.rangeSumBST(root.right, low, high) # 右子树符合条件的和
result = leftSum + rightSum
if root.val >= low and root.val <= high: # 条件符合的值
result += root.val
return result
| 10 | ||||
| 5 | 15 | |||
| 3 | 7 | null | 18 |
大树满足条件的和 等于 每个子树满足条件的数的和之和
2) DFS方法
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
# dfs法
result = 0
queue = [] # 辅助队列
queue.append(root)
while len(queue) > 0: # 队列不为空
size = len(queue)
while size > 0:
cur = queue.pop()
if cur.val >= low and cur.val <= high:
result += cur.val
if cur.left is not None: # 存在左子树
queue.append(cur.left)
if cur.right is not None: # 存在右子树
queue.append(cur.right)
size -= 1 # size控制每一层遍历
return result
| 栈的长度 | ||||||
|---|---|---|---|---|---|---|
| 1 | 10 | |||||
| 2 | 15 | 5 | ||||
| 2 | 7 | 3 | ||||
| 3 | 18 | 7 | 3 |
result = 0 + 10 + 15 + 18
200. 岛屿数量
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
解释：
["1","1"] ； "1"
["1","1"] ； "1","1"
方法1：DFS
深度优先搜索必然会使用到递归
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if grid is None or len(grid) == 0:
return 0
result = 0
row = len(grid) # 行数
col = len(grid[0]) # 列数
# 找岛屿，同化
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
result += 1
self.dfs(grid, i, j, row, col) # 同化：把 1 变为 0
return result
def dfs(self, grid, x, y, row, col):
# 递归的终止条件
if x < 0 or y < 0 or x >= row or y >= col or grid[x][y] == '0':
return
grid[x][y] = '0' # 将 ‘1’变为 ‘0’
# 上\下\左\右 查找可变为‘0’的区域
self.dfs(grid, x-1, y, row, col)
self.dfs(grid, x+1, y, row, col)
self.dfs(grid, x, y-1, row, col)
self.dfs(grid, x, y+1, row, col)
方法2：广度优先搜索
必须使用到辅助队列，用于判断
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if grid is None or len(grid) == 0:
return 0
result = 0
row = len(grid)
col = len(grid[0])
q = [] # 辅助队列
for i in range(0, row):
for j in range(0, col):
if grid[i][j] == '1':
result = result + 1
q.append([i,j])
grid[i][j] = '0'
while len(q) > 0:
cur = q.pop(0) # 出队
x = cur[0]
y = cur[1]
# 如果位置坐标为‘1’同化之后添加坐标至队列中，
# 如果同化全部完成，坐标只会出列
if x-1 >= 0 and grid[x-1][y] == '1':
grid[x-1][y] = '0'
q.append([x-1, y])
if y-1 >= 0 and grid[x][y-1] == '1':
grid[x][y-1] = '0'
q.append([x, y-1])
if x+1 < row and grid[x+1][y] == '1':
grid[x+1][y] = '0'
q.append([x+1, y])
if y+1 < col and grid[x][y+1] == '1':
grid[x][y+1] = '0'
q.append([x, y+1])
return result
方法3：并查集
找到共同的祖先
- Union(x,y)：合并x,y为同一个祖先
- Find(x)：找x的祖先 x=root[x]
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if grid == None or len(grid) == 0:
return 0
row = len(grid)
col = len(grid[0])
waters = 0 # 水域
uf = UnionFind(grid) # 实例化类
for i in range(0, row):
for j in range(0, col):
if grid[i][j] == '0':
waters = waters + 1
# 实现同化
else:
directions = [[0,1], [0,-1], [1,0], [-1,0]]
for d in directions:
x = i + d[0]
y = j + d[1]
if x>=0 and x<row and y>=0 and y<col and grid[x][y]=='1':
uf.union(x*col+y, i*col+j)
# 输出：（岛屿数+水域数） - 水域数
return uf.getCount() - waters
class UnionFind:
def __init__(self, grid):
# 由二维数组构建一个一维数组
row = len(grid)
col = len(grid[0])
self.count = row * col
self.root = [-1] * row * col # 长度
for i in range(0, row * col):
self.root[i] = i # 每一个树都有自己独立的祖先
# 寻找祖先
def find(self, x):
if x == self.root[x]:
return self.root[x]
else:
self.root[x] = self.find(self.root[x])
return self.root[x]
# 只有找到最终的祖先后才union
def union(self, x, y):
rootx = self.find(x)
rooty = self.find(y)
if rootx != rooty:
self.root[rootx] = rooty
self.count -= 1
# 返回合并之后的 岛屿数+水域数
def getCount(self):
return self.count
733-图像渲染
对相同像素的相邻位置进行渲染
- 方法1：深度优先搜索
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
row = len(image)
col = len(image[0])
color = image[sr][sc] # 获取需要渲染的像素
# 当需要渲染的像素和目标像素值相等时，不需要渲染
if color == newColor:
return image
# 深度优先搜索
def dfs(r, c):
if image[r][c] == color:
image[r][c] = newColor
# 向上渲染
if r >= 1:
dfs(r-1, c)
# 向下渲染
if r+1 < row:
dfs(r+1, c)
# 向左渲染
if c >= 1:
dfs(r, c-1)
# 向右渲染
if c+1 < col:
dfs(r, c+1)
dfs(sr, sc)
return image
- 方法2：广度优先搜索
from queue import Queue
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
if image[sr][sc] == newColor:
return image
# 设置四个方向的偏移量,上，下，左，右
directions = {(-1,0), (1,0), (0,-1), (0,1)}
# 构造一个队列，放入起始点
que = Queue()
que.put((sr, sc))
# 记录初始颜色
initcolor = image[sr][sc]
# 当队列不为空
while not que.empty():
# 取出队列的点进行染色
point = que.get()
image[point[0]][point[1]] = newColor
# 遍历四个方向
for direction in directions:
# 新的点（new_i, new_j）,行和列
new_i = point[0] + direction[0]
new_j = point[1] + direction[1]
# 如果这个点在定义域内 且 颜色与初始点颜色相同
if 0 <= new_i < len(image) and 0 <= new_j < len(image[0]) and image[new_i][new_j] == initcolor:
que.put((new_i, new_j))
return image
695-岛屿的最大面积
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
- 深度优先搜索
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = 0
# i和j为网格的坐标位置
for i, l in enumerate(grid):
for j, n in enumerate(l):
ans = max(self.dfs(grid, i, j), ans)
return ans
def dfs(self, grid, cur_i, cur_j) -> int:
# 超出范围，递归终止条件-所有的网格节点全部变为0
if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
return 0
grid[cur_i][cur_j] = 0
ans = 1
# 对相邻位置进行搜索并记录每个岛屿的面积
for di, dj in [[0,1], [0,-1], [1,0], [-1,0]]:
next_i, next_j = cur_i + di, cur_j + dj
ans += self.dfs(grid, next_i, next_j)
return ans
- 栈+广度优先搜索
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = 0
for i, l in enumerate(grid):
for j, n in enumerate(l):
cur = 0
stack = [(i,j)]
while stack:
cur_i, cur_j = stack.pop()
if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
continue
cur += 1
grid[cur_i][cur_j] = 0
for di, dj in [[0,1], [0,-1], [1, 0], [-1, 0]]:
next_i, next_j = cur_i + di, cur_j + dj
stack.append((next_i, next_j))
ans = max(ans, cur)
return ans
