8-search

发表于 更新于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 1 分钟

搜索专题

《算法笔记》第8章搜索专题，包括BFS和DFS。

深度优先搜索

Depth first search（DFS），以深度作为首要因素，每次都遍历一条完整的路径，然后返回上一层的岔路口，继续进行深度的遍历。

假设是在一个迷宫当中寻找出口，那么DFS的意思是每次找到一个岔路口，做个标记，然后找第一条岔路，往下走，找不到出口就回来，继续下一条岔路。对于岔路口的标记属于越往后出现的岔路，越是会被首先回顾，这个是属于栈的思想。

在实现的时候，我们可以使用递归的方式。对于递归的子函数，新生成的子函数会被首先返回，递归的实现本身就依赖于系统栈。

DFS的伪代码：

1
2
3
4
5
6
7
void DFS(int depth, int args) {
  // 对当前的depth进行某些题目需要的操作，判断是否满足条件，比如是否越界，是否找到迷宫的出口等等
  if (depth==MAX_DEPTH) return;
  // 开始遍历岔路，不同的岔路深度是一样的，区别在于其它和题目相关的条件
  DFS(depth+1, args1);
  DFS(depth+1, args2);
}

广度优先搜索

Breadth first search（BFS），以广度作为第一关键词，它访问当前岔路口的所有岔路，而不是顺着某一条岔路继续走下去。

因此，在实现的时候，就不能再采用DFS以递归为途径的遍历手段。还是以迷宫为背景，假设我们希望找到最短的路径是什么。对于当前到达的岔路口S，依次访问岔路A、岔路B、岔路C....，如果都不满足条件，再顺着岔路A的下一个岔路继续走。可以看出来，这个实际是队列的思想，把当前路口的所有岔路入队，然后依次出队，对于出队的岔路，把它的子岔路再入队等待后续的访问。

BFS的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BFS(int data, int args) {
  queue<node> q; // BFS需要用到的队列
  // 创建队首元素
  node * n = new node;
  n.data = data;
  q.push(n);
  while(!q.empty()) {
    // 当前的队首元素出队
    node n_tmp = q.front();
    q.pop();
    // 进行某些判断，例如求和，是否超出边界等
    // n_tmp的所有子结点入队
    while(n_tmp的所有子结点) {
      q.push()
    }
  }
}