不同于广度优先搜索里使用一个额外的队列来帮助寻找,深度优先的原理是回溯,也就是说一查到底,然后到底了回溯到上一级,然后以此寻找, 直到寻找完毕。
1
2 3
5 6 8 13
这个的寻找就是 这么来的 1 2 5 6 3 8 13,就是比如1 开始寻找2然后继续找 找到5 然后5没有了,就回溯到root上,root一看我还有个孩子就是6然后6也找完毕了,又回到2然后2发现自己没了,就回溯到1 然后1 发现自己还有个孩子3 ... 这个过程跟皇帝的顺位继承制度一样大皇子继承,然后大皇子死了大皇孙继承,然后大皇孙死了 大皇子的二儿子继承,然后大皇子家死绝了,才轮到二皇子。emm这么看其实还挺惨。
其实深度优先是没有什么技巧的,它的执行过程不过是计算机实际执行的过程而已,没有任何的技巧,现实中计算机最舒服的执行方式就是深度优先了,至于说为什么执行完毕就回到了上一级,这纯属是递归的概念。所以可以把深度优先理解为一个简单的递归罢了。
func(d *DNode)DFS(ma map[*DNode]int,value interface{})*DNode{
ma[d]++ // 为了防止重复的节点
var t *DNode
if d.Child == nil && d.Value != value {
return nil
}
if d.Value == value {
return d
}
for _,v := range d.Child {
if _,ok := ma[v];!ok {
t = v.DFS(ma,value)
if t != nil {
return t
}
}
}
return t
}
-
广度优先是最合适人类思维的方法,它需要使用队列来记录节点,每次pop就可以把这个节点的孩子加入进去可以说舍弃自己保全孩子
-
深度优先没有技巧,只是一个普通的递归,它是最适合计算器的思考方式。回溯其实意思就是递归的过程中的处理,因为递归的过程肯定是要回溯的,只不过回溯这个名次的意思就是说在递和归的道路上做一些小动作,仅此而已。这个算法中,在归的适合做的动作就是 查看返回值是否不是nil,不是就返回这个值。