搜索（DFS BFS）

DFS

常规DFS:

二叉树前序,中序，后序遍历-CSDN博客

void postorderTraversal(root)初始化一个空列表 arrfind访问总树(root,arr)return arrvoid 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 = 0while True:ch = read_next_character()if ch is None:  # 结束条件，适用于字符串结束return lengthif ch == 'x':length += 1elif 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)
}

P1141 01迷宫（dfs+染色联通块）-CSDN博客

main()对于每个矩阵中的点 (i, j)如果 visit[i][j] 未标记标记 visit[i][j] 为当前联通块 kDFS探索(i, j)更新联通块 k 的大小为 n        // item[k]对应k个联通块大小k++, 重置 n 为 1void 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:  # 如果已经填完所有位置# 根据当前排列更新答案returnfor i from 1 to 9:  # 尝试每一个数字if not visited[i]:  # 如果数字i没有被访问过# 标记数字i为已访问arr[position] = i  # 在当前位置放置数字idfs(position + 1)  # 移动到下一个位置# 回溯，标记数字i为未访问function check_condition():# 将arr数组的不同段转换成数字并检查是否满足(l - a) * c == b的条件# 如果条件满足，则增加ans的值

BFS:

保证最短路径：在寻找最短路径问题中，BFS 能够保证一旦找到目标节点，该路径就是最短的。层级遍历：这意味着首先访问距离起点最近的节点，然后依次访问距离逐渐增加的节点。

所以：首次到达任一节点的路径肯定是从起点到该节点的最短路径。

常规BFS:

问题 R: 胜利大逃亡（bfs）-CSDN博客

问题 N： A strange lift（BFS）-CSDN博客

function bfs(x, y, z, T):初始化队列arr将起点{0,0,0,0}加入队列标记起点为已访问while 队列不为空:取出队列首节点为currentif current是终点且val <= T:清空队列输出current.val并返回for 每个可能的移动方向:计算新位置new_posif new_pos有效且未访问且不是墙:标记new_pos为已访问new_pos.val = current.val + 1将new_pos加入队列输出-1  # 没有找到有效路径