散分了,深度优先思想和广度优先思想是某些算法的基础吗?
鄙人初学数据结构,我觉得:除了图论算法中的深度遍历以及广度遍历,似乎下列算法的执行过程也和它们也有一定的关联:
深度优先思想的算法举例:
文件夹的递归删除---普通树的后序遍历;
归并排序的递归算法--二叉树的后序遍历
快速排序的递归算法---二叉树的先序遍历;
把一个数拆成若干个完全平方数的和(不允许含有1)---递归算法的基本思路:用作差法依次生成子树,一直到达叶子节点,如果是完全平方数则向上回溯至根节点,如果不符合则继续生成同一层次的叶子节点,程序的执行顺序是一颗“先序遍历”的普通树(最坏情况是遍历完毕,最好情况只需找到第一个叶子节点)。
广度优先思想的算法举例:
文件夹的非递归删除--先借助队列层序遍历,把文件全部入栈,然后依次弹栈,弹栈的顺序正好是普通树层序遍历的反序;
快速排序的非递归算法--依然是通过队列,标准的广度遍历;
二叉堆---当建立顺序结构的二叉堆时,大的循环是从倒数第二层的最右边的节点一直遍历到根节点(这是层序遍历的反序),而对于每一个节点,都是去层序遍历它的左右子树的其中之一。
是不是我以后还会接触到“深度类型”以及“广度类型”的算法呢?难道冥冥之中它们有着某种内在联系?
[解决办法]
这俩是很多算法的基础,图论中的大多数算法都要用到dfs和bfs。
[解决办法]
事实上LZ列举的算法举例本质上的数据结构都是以图来组织的,所以会看出dfs和bfs算法
[解决办法]
离散数学,图论。
[解决办法]
每次才散20分。
[解决办法]
路过,学习一下。
[解决办法]
很有思想,人很漂亮!
[解决办法]
我是来膜拜大神的