百度百科:事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.通过栈实现。
简单讲就是一路走到底,再换支路,二叉树的中序遍历就是利用深度优先搜索算法。
我们同样的拿一个二叉树的中序遍历看一看,加深记忆。
如果是图的结构,利用深度优先搜索算法,一定要记住去重,防止死循环。如:
这里只介绍递归的写法,递归内部相当保留一个栈,刚好适合。
以二叉树的中序遍历为基础
Set set = new HashSet();
public void dfs(TreeNode node) {
boolean status = set.add(node); //防止形成环路
if (!status) return;
if (node.left != null) dfs(node.left); //深入下一层
System.out.print(node.val); //业务处理
if (node.right != null) dfs(node.right);
}
其实就是递归中加多一个判断环路的步骤。建议再看看二叉树中序遍历的递归写法,更能体会出深度优先搜索算法是用栈实现的。二叉树遍历
百度百科介绍:BFS,其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)
简单的讲就是想水波纹,一层层的向外推进。
以leetcode:102题为例
一层层的输出,先广度再层层递进。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
if (root == null) return lists;
Queue<TreeNode> queue = new LinkedList<>(); //使用队列保存同一层节点
queue.add(root);
//Set set = new HashSet(); //1.防止形成环路
while (!queue.isEmpty()) {
int size = queue.size(); //得到队列中同一层 有N个
List<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) { //遍历N次,即取出队列中同一层节点
//boolean status = set.add(node); //2.防止形成环路
//if (!status) return;
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) queue.add(node.left); //下一层节点先保存到队列中
if (node.right != null) queue.add(node.right);
}
lists.add(list);
}
return lists;
}
跟我们平时看见修建树木的感觉差不多,但是这个更像是在苹果树刚结果,选择质量比较差的减掉,留下一部分精挑细选的小果,把整棵树的营养集中到一部分果实身上,增加果实质量,卖出更高的价格。
算法中剪枝也是类似概念,当广度或者深度优先搜索算法后面走的路径很多的时候,怎么充分利用资源,把不需要的路径去掉。
百度百科:AlphaBeta剪枝算法是一个搜索算法旨在减少在其搜索树中,被极大极小算法评估的节点数。
记住,在使用搜索算法时,找到问题中的限制信息或者一些特征,把问题简单化,剪去不需要的路径。