Appearance
简介
搜索算法:枚举问题的所有可能答案,并逐一校验。
案例
设集合
- 若
,则 和 必属于 。
已知
以
对于复杂的问题,可以先抽象出关系图,再搜索求解。
广度优先搜索(BFS)
广度优先搜索(Breadth First Search,BFS)按层次搜索节点。其原理如下:
- 建立空队列。
- 将根节点入队。
- 取出队头,将其所有子节点入队。
- 重复上一步直到队列为空。
BFS 搜索该图的步骤:
- 节点
入队; - 节点
出队, 入队; - 节点
出队, 入队; - 节点
出队, 入队; - 节点
出队; - 节点
出队; - 节点
出队; - 节点
出队。
同一个节点不能被重复访问,否则将导致死循环。
cpp
bool vis[]; // vis[u]:节点 u 是否访问过
void bfs(int s) {
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int u = Q.top();
Q.pop();
for ( /* 枚举 u 的子节点 v */ ) {
if (!vis[v]) {
Q.push(v);
vis[v] = true;
}
}
}
}
深度优先搜索(DFS)
深度优先搜索(Depth First Search,DFS)尽可能往更深处搜索节点。其本质是递归。
DFS 搜索该图的步骤:
- 访问根节点
; - 访问子节点
; - 访问子节点
; - 访问子节点
;
- 访问子节点
- 访问子节点
; - 访问子节点
; - 访问子节点
。
- 访问子节点
- 访问子节点
同一个节点不能被重复访问,否则将导致死循环。
cpp
bool vis[]; // vis[u]:节点 u 是否访问过
void dfs(int s) {
vis[s] = true;
for ( /* 枚举 u 的子节点 v */ ) {
if (!vis[v]) {
dfs(v);
}
}
}
多维搜索:前驱
搜索二维数组
现在从某个节点开始搜索,枚举子节点的工作就显得繁琐。以 DFS 为例:
cpp
bool vis[][]; // vis[x][y]: a[x][y] 是否访问过
void dfs(int x, int y) {
vis[x][y] = true;
if (x + 1 <= n && !vis[x + 1][y])
dfs(x + 1, y);
if (x - 1 >= 1 && !vis[x - 1][y])
dfs(x - 1, y);
if (y + 1 <= n && !vis[x][y + 1])
dfs(x, y + 1);
if (y - 1 >= 1 && !vis[x][y - 1])
dfs(x, y - 1);
}
届时可以通过前驱节省工作量。
cpp
bool vis[][];
const int dx[] = {1, 0, -1, 0}; // 第一维度前驱
const int dy[] = {0, 1, 0, -1}; // 第二维度前驱
void dfs(int x, int y) {
vis[x][y] = true;
for (int i = 0; i < 4; i ++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny]) {
dfs(nx, ny);
}
}
}