关于bfs与dfs的标记区别

回顾一下dfs与bfs的使用,由于二者都需要避免走重复的路,所以二者都需要对数组进行标记

而二者的标记操作的不同点是

dfs会对数组的标记进行清除(包含两种标记,一种对形参变量的标记,这个清除是返回上一层时自动清除,另一种是对全局变量的标记,这个清除是要手动进行,在上一个dfs()中上面进行标记,在下一个dfs()上面清除标记,并进行其他标记,总之由于dfs建立了平行时空,所以可以清除标记),

而bfs不会对数组的标记进行清除

所以dfs可针对选择顺序会影响结果的问题(即先选上还是先选下还是先选左还是先选右对最终结果有影响),而bfs只针对选择顺序不会影响结果的问题(即先选哪个方向都没影响)

典型的就是用dfs解决开采石油的问题(开采手法影响结果)https://www.nowcoder.com/acm/contest/76/A,而bfs解决水洼积水问题(对水洼积水的遍历顺序不会影响结果)

关于bfs与dfs的标记区别

上一篇:DOM元素尺寸和位置(clientwidth ,scrollwidth , offsetwidth.......)


下一篇:kubeadm添加新master或node、unknown flag --experimental-upload-certs