js版本的（广、深）度优先搜索0. 前言1.队列、栈2.BFS1.1 矩阵形式的图的遍历1.2 树的BFS举例3.DFS

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<row;j++){
			if(arr[i][j]){ //如果是1
				if(!visited[j]){
					quene.push(j)//队列加入未访问
				}
			}
		}
		quene.shift()//取出队列第一个
		visited[i] = true//记录已经访问
		while(visited[quene[0]]){
			quene.shift()
		}
		order.push(i)//记录顺序
		i = quene[0]
	}
	return {visited:visited,result:!!visited[end],order:order}
}
bfs(map,0,4)
复制代码

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
}
复制代码

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'
}
复制代码

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
}
复制代码