DFS
常规DFS:
void postorderTraversal(root)
初始化一个空列表 arr
find访问总树(root,arr)
return arr
void find(temp, arr)
if temp 为空
return
// 调用顺序由前中后序决定
find递归访问左子树
find递归访问右子树
arr加入当前节点
DFS+回溯:
全排列：
问题 A: 求全排列（1）(DFS(排列类))-CSDN博客
全排列的伪代码（标记，向深搜索，回溯）：
void dfs(Node* node) {
if (node 是已访问) {
return;
}
标记 node 为已访问;
temp.push_back(nums[i]);
dfs(nextNode); //对于 node 的每一个未访问的邻接节点 nextNode
temp.pop_back(nums[i]);
标记 node 为未访问;
}
多层嵌套:
P8650 [蓝桥杯 2017 省 A] 正则问题(dfs )-CSDN博客
def calculate_expression_length():
length = 0
while True:
ch = read_next_character()
if ch is None: # 结束条件，适用于字符串结束
return length
if ch == 'x':
length += 1
elif ch == '(':
length += calculate_expression_length() # 进入子表达式的递归计算
elif ch == ')':
return length # 结束当前递归层次
elif ch == '|':
length = max(length, calculate_expression_length()) # 开始新的选项计算，并与之前的长度比较
DFS+并查集：
问题 C: Oil Deposits（DFS+类并查集）-CSDN博客
统计油田数量伪代码：
void dfs(x,y){
for i in range(next[i][]):
(x,y)向周围八个位置延伸(x1,y1)
if (x1,y1) == @:
(x1,y1) == * // 标记
dfs(x1,y1)
}main()
对于每个矩阵中的点 (i, j)
如果 visit[i][j] 未标记
标记 visit[i][j] 为当前联通块 k
DFS探索(i, j)
更新联通块 k 的大小为 n // item[k]对应k个联通块大小
k++, 重置 n 为 1
void DFS(x, y)
(x,y)->四个方向延伸(nx,ny)
如果 (nx, ny) 在矩阵范围内 且 map[x][y] ≠ map[nx][ny] 且 visit[nx][ny] 未标记
标记 (nx,ny) 为当前联通块 k
增加当前联通块的大小 n++
DFS(nx, ny)
DFS+断点划分：
P8599 [蓝桥杯 2013 省 B] 带分数(dfs+全排列+断点判断)_洛谷p8599 [蓝桥杯 2013 省 b] 带分数java-CSDN博客 Note: target=a+b/c (a,b,c分别由1~9的不同数字组成)
function dfs(position):
if position == 9: # 如果已经填完所有位置
# 根据当前排列更新答案
return
for i from 1 to 9: # 尝试每一个数字
if not visited[i]: # 如果数字i没有被访问过
# 标记数字i为已访问
arr[position] = i # 在当前位置放置数字i
dfs(position + 1) # 移动到下一个位置
# 回溯，标记数字i为未访问
function check_condition():
# 将arr数组的不同段转换成数字并检查是否满足(l - a) * c == b的条件
# 如果条件满足，则增加ans的值BFS:
保证最短路径：在寻找最短路径问题中，BFS 能够保证一旦找到目标节点，该路径就是最短的。层级遍历：这意味着首先访问距离起点最近的节点，然后依次访问距离逐渐增加的节点。
所以：首次到达任一节点的路径肯定是从起点到该节点的最短路径。
常规BFS:
问题 N： A strange lift（BFS）-CSDN博客
function bfs(x, y, z, T):
初始化队列arr
将起点{0,0,0,0}加入队列
标记起点为已访问
while 队列不为空:
取出队列首节点为current
if current是终点且val <= T:
清空队列
输出current.val并返回
for 每个可能的移动方向:
计算新位置new_pos
if new_pos有效且未访问且不是墙:
标记new_pos为已访问
new_pos.val = current.val + 1
将new_pos加入队列
输出-1 # 没有找到有效路径
