算法入门----深度优先搜索

之前推动过一篇算法题 一天一题，深搜枚举与区间合并(0809)，里面用到了深度优先搜索，有同学留言说不会，小编花了几天，整理总结了一些深度优先搜索的。

现实中运用的场景

• 一些组织结构是用树结构来存储的，我们可能需要查找满足条件的某个/些人。

• 实现一个网页的爬虫，当我们爬到一个页面的时候，可能里面还有很多其他的链接，我们可以继续往下爬取。

• 在一些游戏中，我们常常要计算一个点能否到达另外一个点。（广度优先在大部分情况下会更加合理）

• 在线商城统计类目树中各个类目商品的总量。（一开始数量是记在叶子类目上的）

思想

有一句话，叫做“只要学不死，就往死里学，学到死为止”。深度优先搜索就是这样子的，只要还没达到目标深度，就继续往下面搜。

来看个例子，我们用深度优先搜索来遍历一个图。

在这个图中，虚线表示回溯。

模板

有人说深度优先搜索很难实现，哪有这么难。。。大部分其实还是可以上模板的。

public void dfs(int dep, Context context){

if (dep >= 目标深度){

}

if (context 达到 目标状态){

}

if (context已经搜索过){

退出；

}

dfs(dep + 1， context->context')

}

我们来解释一下这么一段伪代码，首先深度优先搜索我们一般会去记录深度，还有上下文的信息。

一般深搜我们用递归实现，如果怕爆栈的可以做深度保护，或者使用手工栈。

进入深搜后，我们一般有4种情况，视具体需求来定

• 第一种是到达目标深度。举个栗子（我们要查找陈经理下面2层的所有员工）。

• 第二种是判断是否达到目标状态。（我们要搜索陈经理下面有没有一个叫做沙茶敏的人，已经找到了！）

• 第三种是判断这个状态是否已经搜索过，我们爬a.com的时候进入了b.com，b.com里面又有一个连接是a.com，这个时候就没必要再找了。

• 第四种是边界判断，判断这个状态是否合法。（例如判断是否为Null）

接下来是状态转移，当前搜索的点可以到达哪个节点。我们在下面的栗子里面再来看看吧。

实例

栗子1：二叉树的（前序）遍历

栗子2：在一个n*m地图上，有一些点可以走，一些点不能走，初始位置在xa,ya,每一秒能向上下左右移动一个单位，问问能不能在规定k时间到达xb,yb.

总结

好了，看到这里，你应该已经会深度优先搜索了。