这是我参与更文挑战的第14天，活动详情查看： 更文挑战
最近想把自己刷算法题的经验心得整理一下，一方面为了复习巩固，另一方面也希望我的分享能够帮助到更多在学习算法的朋友。
专栏名称叫《算法锦囊》，在讲解算法时会注重整体性，但不会面面俱到，适合有一定算法经验的人阅读。
这一次我们重点来看DFS和BFS，这一部分的所有题目和源码都上传到了github的该目录下，题解主要用Python语言实现。
概述
深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。
广度优先搜索算法（Breadth-First Search，缩写为 BFS），又称为宽度优先搜索，是一种图形搜索算法。简单的说，BFS 是从根结点开始，沿着树的宽度遍历树的结点。如果所有结点均被访问，则算法中止。
把它们放在一起是因为很多题目往往这两种方法都能做，只是遍历的方向不一样。
这里面涉及到的思想在前面递归那一节里已经有所涉及，今天来重点看一下DFS和BFS的运用。
代码模板
DFS的递归写法
visited = set()
def dfs(node, visited):
if node in visited: # terminator
# already visited
return
visited.add(node)
# process current node here.
...
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
复制代码DFS的非递归写法
def DFS(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process (node)
nodes = generate_related_nodes(node)
stack.push(nodes)
# other processing work
...
复制代码BFS的写法
def BFS(graph, start, end):
queue = []
queue.append([start])
visited.add(start)
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
queue.push(nodes)
# other processing work
...
复制代码200. 岛屿数量
首先来看这道经典的DFS题目，200. 岛屿数量。
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
复制代码我们可以先去遍历这个矩阵，如果遇到1，则岛屿数加1，同时我们要把这一片岛屿，即包括这个1以及和它相邻的所有1，全部改成0。
于是按这个思路很快写出DFS的解法。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def _dfs(i, j):
grid[i][j] = "0"
for dx, dy in directions:
n_i, n_j = i + dx, j + dy
if 0 <= n_i < row and 0 <= n_j < col and grid[n_i][n_j] == "1":
_dfs(n_i, n_j)
count = 0
row, col = len(grid), len(grid[0])
directions = [[-1,0],[1,0],[0,1],[0,-1]]
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
count += 1
_dfs(i, j)
return count
复制代码另外要注意一点的是，我上面的写法改变了原数组，如果不想改变原数组，可以利用visited集合来存储所有访问过的元素。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def _dfs(i, j):
visited.add((i, j))
for m, n in direction:
if 0 <= i+m < row and 0 <= j+n < col and grid[i+m][j+n] == '1' and (i+m, j+n) not in visited:
_dfs(i+m, j+n)
if not grid or not grid[0]: return 0
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
row, col = len(grid), len(grid[0])
visited = set()
count = 0
for i in range(row):
for j in range(col):
if grid[i][j] == '1' and (i, j) not in visited:
count += 1
_dfs(i, j)
return count
复制代码我们在把岛屿“夷为平地”的时候，目前用的DFS，另外这里也可以利用BFS来实现，借助于queue，我们利用一种“波纹扩散”的方式，去对相邻的1进行遍历。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
direction = [(1,0),(0,1),(-1,0),(0,-1)]
row = len(grid)
col = len(grid[0])
count = 0
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
count += 1
# 采取贪心的原则，这里能置为0就先置为0
grid[i][j] = '0'
queue = [(i, j)]
while queue:
a, b = queue.pop(0)
for m, n in direction:
if 0 <= a+m < row and 0 <= b+n < col and grid[a+m][b+n] == '1':
queue.append((a+m, b+n))
grid[a+m][b+n] = '0'
return count
复制代码这道题也可以用并查集的思路去做，关于并查集，后面会专门有专题介绍。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]: return 0
uf = UnionFind(grid)
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
row, col = len(grid), len(grid[0])
for i in range(row):
for j in range(col):
if grid[i][j] == '0':
continue
for d in direction:
nr, nc = i+d[0], j+d[1]
if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == '1':
uf.union(i*col+j, nr*col+nc)
return uf.count
class UnionFind:
def __init__(self, grid):
m, n = len(grid), len(grid[0])
self.count = 0
self.parent = [-1] * (m*n)
self.rank = [0] * (m*n)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
self.parent[i*n+j] = i*n+j
self.count += 1
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, x, y):
rootx = self.find(x)
rooty = self.find(y)
if rootx != rooty:
self.parent[rootx] = rooty
self.count -= 1
复制代码130. 被围绕的区域
趁热打铁，我们来看 130. 被围绕的区域。
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
复制代码这道题跟前面的岛屿数量有异曲同工之妙，不同的是，这道题的做法是只要遍历边缘的“O”就行了，并将边缘的“O”以及它的相邻位置的“O”标记为别的字母比如“#”，此时剩下的“O”就全部是中心的了，把它们标记成“X”，最后再把“#”改回“O”。
DFS解法：
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def _dfs(i, j):
if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] in ['X', '#']: return
board[i][j] = '#'
_dfs(i-1, j)
_dfs(i+1, j)
_dfs(i, j-1)
_dfs(i, j+1)
if not board or not board[0]: return
m, n = len(board), len(board[0])
for i in range(0, m):
for j in range(0, n):
is_edge = i == 0 or j == 0 or i == m-1 or j == n-1
if is_edge and board[i][j] == 'O':
_dfs(i, j)
print(board)
for i in range(0, m):
for j in range(0, n):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == '#':
board[i][j] = 'O'
复制代码BFS解法：
import collections
class Solution:
def solve(self, board: List[List[str]]) -> None:
if not board:
return
n, m = len(board), len(board[0])
que = collections.deque()
for i in range(n):
if board[i][0] == "O":
que.append((i, 0))
if board[i][m - 1] == "O":
que.append((i, m - 1))
for i in range(m - 1):
if board[0][i] == "O":
que.append((0, i))
if board[n - 1][i] == "O":
que.append((n - 1, i))
while que:
x, y = que.popleft()
board[x][y] = "A"
for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and board[mx][my] == "O":
que.append((mx, my))
for i in range(n):
for j in range(m):
if board[i][j] == "A":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
复制代码127. 单词接龙
接下来，我们来挑战一道困难题，127. 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
复制代码因为要求最短的转换序列，所以不太适合用DFS（DFS能算出结果，但是最先算出来的结果不一定是最优解，必须要全部递归完才行），我们用BFS来做。
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
wordList = set(wordList)
queue = [(beginWord, 1)]
while queue:
word, length = queue.pop(0)
if word == endWord:
return length
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
next_word = word[:i] + c + word[i+1:]
if next_word in wordList:
queue.append((next_word, length+1))
wordList.remove(next_word)
return 0
复制代码每次改变一个字符，如果在单次集合里，则把它放进队列里，并把序列长度+1，直到最先找到我们要的答案为止。
这道题我们可以继续优化，我们可以看到，终点和起点是对称的，既然可以从起点BFS，那为何不能从终点BFS。
所以我们可以从起点和终点分别进行BFS，直到它们相会，这也叫双向BFS。
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList: return 0
front = {beginWord}
back = {endWord}
dist = 1
wordList = set(wordList)
word_len = len(beginWord)
while front:
dist += 1
next_front = set()
for word in front:
for i in range(word_len):
for c in string.ascii_lowercase:
if c != word[i]:
new_word = word[:i] + c + word[i+1:]
if new_word in back:
return dist
if new_word in wordList:
next_front.add(new_word)
wordList.remove(new_word)
front = next_front
if len(back) < len(front):
front, back = back, front
return 0
复制代码注意，在算法里面，我们通过比较起点和终点的队列长度，来确定下一次是用起点还是终点的队列。
433. 最小基因变化
最后，我们用这道题来巩固DFS和BFS。433. 最小基因变化。
一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
例如，基因序列由"AACCGGTT" 变化至 "AACCGGTA" 即发生了一次基因变化。
与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
注意：
起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
如果一个起始基因序列需要多次变化，那么它每一次变化之后的基因序列都必须是合法的。
假定起始基因序列与目标基因序列是不一样的。
示例 1：
start: "AACCGGTT"
end: "AACCGGTA"
bank: ["AACCGGTA"]
返回值: 1
复制代码首先用DFS。
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
bank = set(bank)
if end not in bank:
return -1
change_map = {
"A": "CGT",
"C": "AGT",
"G": "CAT",
"T": "CGA",
}
min_count = len(bank) + 1
def dfs(current, count, current_bank):
nonlocal min_count
# terminator
if count > min_count:
return
if current == end:
if count < min_count:
min_count = count
return
if not current_bank:
return
# process
for i, s in enumerate(current):
for char in change_map[s]:
new = current[:i] + char + current[i + 1:]
if new not in current_bank:
continue
current_bank.remove(new)
# drill down
dfs(new, count + 1, current_bank)
# reverse state
current_bank.add(new)
dfs(start, 0, bank)
return min_count if min_count <= len(bank) else -1
复制代码然后是BFS
class Solution:
def minMutation(self, start, end, bank):
queue = [(start, 0)]
bank = set(bank)
while queue:
cur, count = queue.pop(0)
if cur == end: return count
for i in range(0, len(start)):
for ch in ['A', 'C', 'G', 'T']:
new = cur[0:i] + ch + cur[i+1:]
if new in bank:
queue.append((new, count+1))
bank.remove(new)
return -1
复制代码当然这题也可以用双向BFS
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
if end not in bank:
return -1
start_set = {start}
end_set = {end}
bank = set(bank)
length = 0
change_map = {'A': 'TCG', 'T': 'ACG', 'C': 'ATG', 'G': 'ATC'}
while start_set:
length += 1
new_set = set()
for node in start_set:
for i, s in enumerate(node):
for c in change_map[s]:
new = node[:i] + c + node[i + 1:]
if new in end_set:
return length
if new in bank:
new_set.add(new)
bank.remove(new)
start_set = new_set
if len(end_set) < len(start_set):
start_set, end_set = end_set, start_set
return -1
复制代码© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
