查找算法008-深度、广度优先搜索


为了学习DFS和BFS,我们首先要知道什么是图的遍历:

图遍历又称图的遍历,属于数据结构中的内容。指的是从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作,图的许多其它操作都是建立在遍历操作的基础之上。






一、深度优先搜索(DFS:Depth First Search


事实上,深度优先搜索属于图算法的一种,简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.


基本思想:

深度优先搜索法是树的先根遍历的推广,它的基本思想是:从图G的某个顶点v0出发,访问v0,然后选择一个与v0相邻且没被访问过的顶点vi访问,再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问,依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w,从w出发按同样的方法向前遍历,直到图中所有顶点都被访问。


举例说明:

下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束)

happysneaker.com




一、广度优先搜索(BFS:Breadth First Search


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


算法思想:


广度优先搜索(BFS)类似于二叉树的层序遍历算法,它的基本思想是:首先访问起始顶点v,然后由v出发,依次访问v的各个未被访问过的邻接顶点w1,w2,w3….wn,然后再依次访问w1,w2,…,wi的所有未被访问过的邻接顶点,再从这些访问过的顶点出发,再访问它们所有未被访问过的邻接顶点….以此类推,直到途中所有的顶点都被访问过为止。


算法步骤、举例:


如下图,首先访问结点A,然后找到A的邻接结点B和C,访问这两个结点。然后从B出发,找到B的未被访问的结点邻接结点D和E,然后访问这两个结点,然后从结点C出发,找到C的未被访问的邻接结点F和G,然后访问这两个结点,然后从结点D出发,找到D的违背访问的邻接结点H,访问这个结点。然后从结点E出发…依此类推。

happysneaker.com


Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论