• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

浅谈DFS与BFS

开发技术 开发技术 2周前 (05-02) 5次浏览

搜索(深搜回溯与广搜)

1.深搜与回溯

深度优先搜索,简称为深搜或 “DFS” (Depth First Search),

是图运算的一种搜索方式,简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.大致的搜索过程如下

深度优先遍历图的方法是,

从图中某顶点v出发:

(1)访问顶点v;

(2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 

当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.而在走迷宫时,有是我们会走到一条死路中,所以我们不得不退回到上一步,对下一个进行搜索

void DFS(int 当前状态)  
{  
      if(当前状态为边界状态)  
      {  
        记录或输出  
        return;  
      }  
      for(i=0;i<n;i++)     
      {  
           //扩展出一个子状态。  
           修改了全局变量  
           if(子状态满足约束条件)  
            {  
              dfs(子状态)  
           }  
            恢复全局变量//回溯部分  
      }  
}  

这个代码大体上就是DFS的全过程了,

“一直往下走,走不通了就掉头,换一条路再往下走”便是深搜的精髓.

深搜的特点:

(1)深度优先搜索法有递归以及非递归两种设计方法。一般的,当搜索深度较小、问题递归方式比较明显时,用递归方法设计好,它可以使得程序结构更简捷易懂。当数据量较大时,由于系统堆栈容量的限制,递归容易产生溢出,用非递归方法设计比较好。

(2)深度优先搜索方法有广义和狭义两种理解。广义的理解是,只要最新产生的结点(即深度最大的结点)先进行扩展的方法,就称为深度优先搜索方法。在这种理解情况下,深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是,仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法,实际上是在数据库中产生一个结点之间的搜索树,因此也属于图搜索算法的范畴。

(3)不保留全部结点的深度优先搜索法,由于把扩展望的结点从数据库中弹出删除,这样,一般在数据库中存储的结点数就是深度值,因此它占用的空间较少,所以,当搜索树的结点较多,用其他方法易产生内存溢出时,深度优先搜索不失为一种有效的算法。
(4)不一定会得到最优解,这个时候需要修改原算法:把原输出过程的地方改为记录过程,即记录达到当前目标的路径和相应的路程值,并与前面已记录的值进行比较,保留其中最优的,等全部搜索完成后,才把保留的最优解输出。

广搜(BFS)

广度优先搜索:宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫 BFS ,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

搜索的大致过程如这样:

对每一个子节点的可能节点进行搜索,

已知图G=(V,E)和一个源顶点s,宽度优先搜索以一种系统的方式探寻G的边,从而“发现”s所能到达的所有顶点,并计算s到所有这些顶点的距离(最少边数),该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v,宽度优先树中从s到v的路径对应于图G中从s到v的最短路径,即包含最小边数的路径。该算法对有向图和无向图同样适用。—-百度百科

利用队列先进先出的特性,把每个点的后继存入队列,不断地弹出,进行判断.

void BFS()

{ … …//初始化起点入队

   while(!q.empty()) //判断队是否为空

   {   … …//获取队首元素

       if(... …)

{… …}//判断是否是终点

       for(int i=0;i<4;i++)//四个方向

       {   k.x=p.x+dir[i][0];                

k.y=p.y+dir[i][1];

          //向各个方向走一步             

if(judge())//判断能不能走         

{ … …//各种处理                

vis[k.x][k.y]=1; //标记              

q.push(k); //入队

           }

       }

   }

}

一个比较经典的搜索题目,DFS和BFS都可以做

例题

洛谷P1596

题解


程序员灯塔
转载请注明原文链接:浅谈DFS与BFS
喜欢 (0)