图的搜索(遍历) – BFS & DFS

2018年12月19日Otstar Lin

BFS,即 Breath First Search(广度优先搜索)

DFS,即 Deep First Search (深度优先搜索)

图的搜索是对于连通图的一种遍历策略,常用于走迷宫的问题

本文的算法基于C语言编写,过几天会使用Java重写这两个算法

另外本文的算法是对基于数组的图进行搜索,基于链表的搜索暂时未弄 (逃

1.BFS

广度优先搜索顾名思义,就是在广范围进行搜索,从一个顶点V0开始,辐射状地优先遍历其周围较广的区域

算法的基本思路

在广搜中不需要记录节点是否走过,但是要记录上一个节点的位置,若将整个过程画成树,即可观察到广搜是一层一层进行遍历的(这里就不画图了,逃),这时若要搜索下一层节点就需要读取上一层节点的位置,并对父节点的所有节点逐个进行搜索,将符合要求的子节点逐个存入下一层节点,直到判断到达终点即停止搜索

基础算法采用递归,存储搜索各层节点采用队列,但由于C语言中没有队列所以采用结构体数组代替,使用二维结构体数组,其中一维对应层数,另一维存储该层的节点,另外若要使广搜拥有寻迹功能,即可以输出行进路程中每一步,就需要在结构体中增加一个结构体指针指向父节点,然后记录最后一个节点的地址,通过访问指针来访问父节点,直到到达起点

算法的实现

本算法由于要进行寻迹操作,所以保留了每一层的数据,若不需要寻迹建议只保留两个队列,即两个一维结构体数组

2.DFS

深度优先搜索类似于广度优先搜索,也是一种图的搜索算法,但是不同于广度优先搜索,广搜注重范围,而深搜注重深度,通俗来说,广搜就是广撒网,深搜就是一路走到黑,不撞南墙不回头\( ̄︶ ̄\))

算法的基本思路

深搜需要定义一个跟原图相同的数组,然后通过该数组对数据进行标记,若已经走过就标记,回到父节点时将父节点的标记取消,基础算法依旧使用递归

算法的实现

两种算法的比较

广搜由由于需要维护多条路径,同时存储多条路径,所以在正常情况下广搜使用的内存会比深搜多,编写也相对复杂,但是由于广搜一般是采用队列来存储路径所以没有爆栈的危险(C语言不适用),而深搜是使用栈进行存储的,由于系统分配给程序的栈是有限的,所以当深度过高时深受可能会出现爆栈。

一般来说用DFS解决的问题都可以用BFS来解决。DFS多用于连通性问题因为其运行思想与人脑的思维很相似,故解决连通性问题更自然。BFS多用于解决最短路问题,其运行过程中需要储存每一层的信息,所以其运行时需要储存的信息量较大,资源的消耗也较多。但是在不同问题中两者占优的情况是不同的,当图较为复杂二者其实差别不大。

说点什么

您将是第一位评论人!

avatar
  Subscribe订阅  
提醒
Prev Post Next Post