dfs.md

深度优先搜索 DFS

不同于广度优先搜索里使用一个额外的队列来帮助寻找，深度优先的原理是回溯，也就是说一查到底，然后到底了回溯到上一级，然后以此寻找， 直到寻找完毕。

      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，不是就返回这个值。