//深搜遍历从起点出发能走的所有节点
//对于一个节点,只要发现了没走过的点就走到它,如果有多个点可走就任选一个(递归调用)
//由于是从起点开始遍历,因此遍历过程也是产生路径的过程 ,因此深搜遍历是有路径信息的 ,单纯的根据数据结构遍历所有点是没有路径信息的
Dfs(V)
{
if(V是旧点) return ;
将V标记为旧点;
for U in 和V相邻的点 :
if(满足能走的条件) // 不仅要考虑这两个点是不是连通的,还要考虑剪枝的条件限制,通过剪枝减少某些不必要路径(减少递归次数)
Dfs(U));
}
//深搜遍历图上所有节点,注意区分仅仅调用Dfs(V)
while(能找到新节点K)
{
Dfs(K) ;
}
//深搜寻找从起点V到终点的最优路径
Dfs(V)
{
if(找到终点)
判断是否为最优路径
for U in 和V相邻的点 :
if(满足能走的条件) // 不仅要考虑这条路能不能走,还要考虑剪枝的条件限制,通过剪枝减少某些不必要路径(减少递归次数)
{
//走V->U这条路 ,更新路径信息
visited(V->U)=1;//标记为已经走过
updateParam() ;
//以U为起点继续走
Dfs(U));
//重置走V->U这条路的路径信息,接下来尝试走其他和V相邻的点
visited(V->U)=0;
resetParam(); //上条语句走好了U->终点或不能走这条子路径,当我们在递归中加入这条语句后,在执行完这条语句后那条子路径就被删除了
}
}
- 若将深搜理解为扩展路径的一种递归算法,则可以从分解子问题递归的角度来理解
- 甚至可以将深搜理解为在递归的状态图,这个图上进行深搜 。这样的话,我们可以用Dfs这种搜索方法去写递归函数。
- 剪枝:可行性剪枝:该方法判断继续搜索 能否 得出答案,如果不能直接回溯。例如要求得到x=x0,但按照当前情况继续递归下去x一定会 大于或者小于 x0,而不可能=x0,此时就不再继续 ;最优性剪枝:它记录当前得到的最优值,如果当前结点已经无法产生比当前最优解更优的解时,可以提前回溯。
- Dfs也是递归,因此Dfs也可以用动态规划 ,比如用一个数组存某个点的最优路径, 之后再走到这个点时就不用再运算了
- 深搜寻路时如何更快找到路径,简单点的理解可以看我的博客鸣人和佐助(老婆)