guodong's blog

master@zhejiang university
   

BFS and DFS

概述

BFS和DFS,这两个是一个缩写,全称是 BFS:Breadth-First-Search,宽度优先搜索;DFS:Depth-first search,深度优先搜索。两者都是搜索方法。

对于一个图来说,搜索就是从某个点开始,不停的搜索与它相连的点,直到所有的点都被搜索到了。

如上图,如果从1开始搜索的话,BFS的步骤就是先搜索与1直接连的,也就是2和5。再从2开始搜索与他相连的,即3,随后从5搜索到4。然后从3开始搜索,因为4已经被检索过,所以跳过,然后从4开始搜索,找到了6.

我们发现,搜索的时候找到所有子树后停止,然后再从同级的(宽度)树开始搜索到子树。

对于DFS来说,从1开始,搜索到其中一个相连的,为2,然后直接从2开始搜索,到3,然后从3开始到4,再到5(注意不是6),此时没路走了,然后回到前面的4,找到了6,没路。回到前面4,没路,回到前面3,没路,回到前面2,找到了5,发现已经找过了,再回到1.结束。

DFS和BFS主要是运用于对于图和树的搜索,但是绝大部分问题模型都是可以建模变成一个图或者树的,所以差不多不少问题都会涉及到这两个。

下面谈怎么用代码来实现算法。

图的建立

定义:给定一个图,对于每个点来说就是标号1,2,3,,,,N。表示有N个节点,(一般情况下都已经标好号了。)对于边,两个顶点之间的连线就是边。

储存一个图(存图的含义就是对于每个u,记录他能到的所有点)有三种方法:

邻接矩阵:直接来一个N*N的二维数组,这个空间效率太差,其次对于两个点有两条边的话,也没法表示。

邻接链表:使用一个链表的方式保存一个结点的所有边,然后每个点都有一个链表。对于一个点u,将他指向的所有点{Vi},按照插入的先后顺序,建立单链表,当有新的点进入时,采用尾插法增加链表,采用尾插法,然后为了满足建立,{Vi}的顺序是不被要求的,故,在建成的图中会发现u点指向的点的遍历顺序是最后加入的最先遍历出来。

以上方法实现了对一个点的操作,那么对于一个图来说是有很多的点和边构成的,那么就可以通过一系列的{Ui}来完成对图的表示。

U1:v11->v12->v13->…(一条单链表)

U2:v21->v22->v23->…

……

Ui:vi1->vi2->vi3->…

邻接表的遍历,对一个点遍历时,通过Ui就一直next,直到结束为NULL。

比如下图:

前向星:他和链表几乎没什么区别,就是每次添加新的边的时候往开头加,而不是往最后加。不采用尾插法的原因是,每一次的插入都要遍历一遍{Vi}非常浪费时间。

算法实现

BFS的实现需要通过队列来保存。因为每次找到和点u相连的之后要一个个找这些点,符合先进先出。 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。栈(stacks)是一种只能通过访问其一端来实现数据存储与检索的线性数据结构,具有后进先出(last in first out,LIFO)的特征。

在python里,队列有queue对象(collections里的deque方法),栈就是普通的list。

在c++里,队列quene,栈stack

DFS:需要一个栈,因为每次都是搜到之后不停的往下搜,符合先进先出。但是一般来说不用栈,而是直接通过函数的递归就行了。

至于这两个的用途,其实在一定程度上是可以相互转化的,但是有些需要各自的特性的话就不行了。

DFS主要的特性是深度优先,总是不停的往下找,走到没路才罢休。

BFS则是从root开始扩展,每一层都是精密的搜索完整了才下一个。

参考链接 :

https://www.cnblogs.com/whywhy/p/4888632.html

https://blog.csdn.net/triple_wdf/article/details/78152725

https://blog.csdn.net/coutamg/article/details/65935374

 

 




上一篇:
下一篇:

头像

guodong

没有评论


你先离开吧:)



发表评论

电子邮件地址不会被公开。 必填项已用*标注