深度优先遍历与广度优先遍历的区别

Question

如题所述

Answer 1

一、指代不同

1、深度优先遍历：是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

2、广度优先遍历：系统地展开并检查图中的所有节点，以找寻结果。

二、特点不同

1、深度优先遍历：所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统。正如前面所说的，搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。

2、广度优先遍历：并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

三、算法不同

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

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

参考资料来源：百度百科-广度优先遍历

参考资料来源：百度百科-深度优先遍历

Answer 2

一、指代不同

1、深度优先遍历：是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

2、广度优先遍历：系统地展开并检查图中的所有节点，以找寻结果。

二、特点不同

1、深度优先遍历：所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统。正如前面所说的，搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。

2、广度优先遍历：并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

三、算法不同

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

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

Answer 3

深度优先遍历与广度优先遍历是图遍历的算法（不明白好好研究一下数据结构图遍历那一章）。
深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。
广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有结点都被访问完为止。

可以看到两种方法最大的区别在于前者从顶点的第一个邻接点一直访问下去再访问顶点的第二个邻接点；后者从顶点开始访问该顶点的所有邻接点再依次向下，一层一层的访问。本回答被提问者采纳

Answer 4

一个向下…一个从左到右