深度优先搜索和广度优先搜索

内容预览:
  •   3、有向图的广度优先搜索   下面是有向图的广度优先搜索过程:  ...~
  • 三、两者实现方式对比   深度优先搜索用栈(stack)来实现,整个过程...~
  • 并把这个元素记为它下一级元素的前驱~

  深度优先搜索和广度优先搜索都是图的遍历算法。

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

  1、介绍

  深度优先搜索(DFS),顾名思义,在进行遍历或者说搜索的时候,选择一个没有被搜过的结点(一般选择顶点),按照深度优先,一直往该结点的后续路径结点进行访问,直到该路径的最后一个结点,然后再从未被访问的邻结点进行深度优先搜索,重复以上过程,直至所有点都被访问,遍历结束。

  一般步骤:

  • (1)访问顶点v;

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

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

  可以看出,深度优先算法使用递归即可实现。

  2、无向图的深度优先搜索

  下面以无向图为例,进行深度优先搜索遍历:

  

  遍历过程:

  

  所以遍历结果是:A→C→B→D→F→G→E。

  3、有向图的深度优先搜索

  下面以有向图为例,进行深度优先遍历:

  

  遍历过程:

  

  所以遍历结果为:A→B→C→E→D→F→G。

二、广度优先搜索(Breadth First Search)

  1、介绍

  广度优先搜索(BFS)是图的另一种遍历方式,与DFS相对,是以广度优先进行搜索。简言之就是先访问图的顶点,然后广度优先访问其邻接点,然后再依次进行被访问点的邻接点,一层一层访问,直至访问完所有点,遍历结束。

  2、无向图的广度优先搜索

  下面是无向图的广度优先搜索过程:

  

  所以遍历结果为:A→C→D→F→B→G→E。

  3、有向图的广度优先搜索

  下面是有向图的广度优先搜索过程:

  

  所以遍历结果为:A→B→C→E→F→D→G。

三、两者实现方式对比

  深度优先搜索用栈(stack)来实现,整个过程可以想象成一个倒立的树形:

  1. 把根节点压入栈中。
  2. 每次从栈中弹出一个元素,搜索所有在它下一级的元素,把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
  3. 找到所要找的元素时结束程序。
  4. 如果遍历整个树还没有找到,结束程序。

  广度优先搜索使用队列(queue)来实现,整个过程也可以看做一个倒立的树形:

  1. 把根节点放到队列的末尾。
  2. 每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
  3. 找到所要找的元素时结束程序。
  4. 如果遍历整个树还没有找到,结束程序。

 

以上就是:深度优先搜索和广度优先搜索 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论