0. 前言

广度优先搜索(BFS)和深度优先搜索(DFS)，大家可能在oj上见过，各种求路径、最短路径、最优方法、组合等等。于是，我们不妨动手试一下js版本怎么玩。

1.队列、栈

队列是先进先出，后进后出，常用的操作是取第一个元素（shift）、尾部加入一个元素（push）。

栈是后进先出，就像一个垃圾桶，后入的垃圾先被倒出来。常用的操作是，尾部加入元素（push），尾部取出元素（pop）

2.BFS

BFS是靠一个队列来辅助运行的。顾名思义，广度搜索，就是对于一个树形结构，我们一层层节点去寻找目标节点。

按照这个顺序进行广度优先遍历，明显是队列可以完美配合整个过程：

1进队列【1】

取出队列第一个元素1，将1的子节点234按顺序加入队列后面【2，3，4】

取出队首元素2，将他的子节点按顺序加入队列【3，4，5，6】

取出3，将子节点7加入【4，5，6，7】

取出4，将子节点89加入【5，6，7，8，9】

取出5，没有子节点，没有什么干

继续一个个取出

到了最后，队列清空，树也遍历了一次

1.1 矩阵形式的图的遍历

假设有几个点，我们需要设计一个算法，判定两个点有没有相通

假设点12345是这样的结构：

问：1能不能到达5

显然我们一眼看上去是不会到达的，如果是设计算法的话，怎么做呢？

我们把点之间的关系用一个矩阵表示，0表示不连接，n行m列的1表示点n通向点m

var map = [ [0,1,1,0,0],[0,0,1,1,0],[0,1,1,1,0],[1,0,0,0,0],[0,0,1,1,0]]复制代码

function bfs(arr,start,end){	var row = arr.length	var quene = []	var i = start	var visited = {}//记录遍历顺序	var order = [] //记录顺序，给自己看的	quene.push(i) //先把根节点加入	while(quene.length){ //如果队列没有被清空，也就是还没遍历完毕		for(var j = 0;j

1.2 树的BFS举例

举个例子，3月24号今日头条笔试题第二题的最少操作步数：

定义两个字符串变量：s和m，再定义两种操作，第一种操作： m = s; s = s + s; 第二种操作： s = s + m; 假设s, m初始化如下： s = "a"; m = s; 求最小的操作步骤数，可以将s拼接到长度等于n 输入一个整数n，表明我们需要得到s字符长度，0<n<10000 案例： in: 6 out: 3

思路：利用广度优先搜索，假设左节点是操作1，右节点是操作2，这样子就形成了操作树。利用bfs的规则，把上层的父节点按顺序加入队列，然后从前面按顺序移除，同时在队列尾部加上移除的父节点的子节点。我这里，先把父节点拿出来对比，他的子节点放在temp，对比完了再把子节点追加上去

每个节点分别用两个数记录s，m。发现第一次两种操作是一样的，所以我就略去右边的了

function bfs(n){	if(n<2||n!==parseInt(n)||typeof n !=='number') return	if(n==2) return 1	var quene = [[2,1]]//从2开始	var temp = []//存放父节点队列的子节点	var count = 0	var state = false//判断是否结束循环	while(!state){		while(quene.length){
   //如果队列不是空，从前面一个个取，并把他的子节点放在temp			var arr = quene.pop()			if(arr[0]==n){
   //找到了直接结束				state = true				break			}				temp.push([arr[0]*2,arr[1]*2])				temp.push([arr[0]+arr[1],arr[1]])		}		count++//队列已经空，说明这层的节点已经全部检索完，而且子节点也保存好了		quene = [...temp]//队列是子节点所有的元素集合,重复前面操作		temp = []	}	return count}复制代码

3.DFS

DFS着重于这个搜索的过程，一般以“染色”的形式配合栈来运行，也比较彻底。V8老生代的垃圾回收机制中的标记-清除也利用了DFS。我们定义三种颜色：黑白灰，白色是未处理过的，灰是已经经过了但没有处理，黑色是已经处理过了还是前面那幅图

我们用两个数组，一个是栈，一个是保存我们遍历顺序的，数组的元素拿到的都是原对象树的引用，是会改变原对象的节点颜色的

从根节点开始，把根节点1压入栈，染成灰色【1：灰】

发现1的白色子节点2，压入栈染色【1：灰，2：灰】

发现2的白色子节点5，入栈染色【1：灰，2：灰，5：灰】

发现5没有白色子节点，于是5已经确认是遍历过的，5出栈染黑色【1：灰，2：灰】，【5：黑】

回溯2，发现2还有白色子节点6，6入栈染灰，发现6没有子节点，6出栈染黑色，【1：灰，2：灰】，【5：黑，6：黑】；又发现2没有白色子节点，2出栈染黑色【1：灰】，【5：黑，6：黑，2：黑】

2又回溯1，发现1还有白色子节点3，3入栈染灰【1：灰，3：灰】，【5：黑，6：黑，2：黑】

同样的，7没有白色子节点，7入栈直接出栈染黑，【1：灰，3：灰】，【5：黑，6：黑，2：黑，7：黑】；3没有白色子节点【1：灰】出栈染黑，【5：黑，6：黑，2：黑，7：黑，3：黑】

到了4，【1：灰，4：灰】，他有白色子节点89，而89没有白色子节点，所以89入栈又直接出栈了【1：灰，4：灰】，【5：黑，6：黑，2：黑，7：黑，3：黑，8：黑，9：黑】

4这次就没有白色子节点了，到他出栈染黑，【1：灰】，【5：黑，6：黑，2：黑，7：黑，3：黑，8：黑，9：黑，4：黑】

回溯，发现1没有白色子节点，最后1出栈染黑，【5：黑，6：黑，2：黑，7：黑，3：黑，8：黑，9：黑，4：黑，1：黑】

我们可以看到，入栈的时候，从白色染灰色，出栈的时候，从灰色到黑色。整个过程中，染黑的顺序类似于二叉树的后序遍历

v8的垃圾回收，将持有引用的变量留下，没有引用的变量清除。因为如果持有引用，他们必然在全局的树中被遍历到。如果没有引用，那这个变量必然永远是白色，就会被清理

我们用对象来表示上面这棵树：

var tree = {	val: 1,	children: [		{
   val: 2,children: [{
   val:5,children:null,color:'white'},{
   val: 6,children:null,color:'white'}],color:'white'},		{
   val: 3,children: [{
   val: 7,children:null,color:'white'}],color:'white'},		{
   val: 4,children: [{
   val:8,children:null,color:'white'},{
   val: 9,children:null,color:'white'}],color:'white'}	],	color: 'white'}复制代码

开始我们的DFS：

function dfs ( tree ) {	var stack = []//记录栈	var order = []//记录遍历顺序	!function travel (node) {		stack.push(node)//入栈		node.color = 'gray'		console.log(node)		if(!node.children) {
   //没有子节点的说明已经遍历到底			node.color = 'black'			console.log(node)			stack.pop()			order.push(node)			return		}		var children = node.children			children.forEach(child=>{			travel(child)		})		node.color = 'black'		stack.pop()//出栈		order.push(node)		console.log(node)	}(tree)	return order}复制代码

过程用递归比较简单，上面大部分代码都是调试代码，自己可以改一下测试其他的类似场景。遍历完成后，tree上面每一个节点都是黑色了。遍历中间过程，每一个节点入栈的时候是灰色的，出栈的时候是黑色的。