算法学习:DFS和BFS

最近要做一个节点树的遍历,记录下两种遍历算法。这两种遍历针对普通的树结构,非二叉树。看懂了,非常简单。

深度优先遍历(depthFirstSearch—DFS)

看下面的图比较直观,按照层级一级一级遍历,先一条分支走到底,再回过来按同样的方法查找另外一个分支,一般采用递归方式。

广度优先遍历(broadFirstSearch—BFS)

看下面的图,也是按照层级,一层一层查找,不同的是,从源节点开始,查找子节点,所有的子节点操作完之后,再操作上所有子节点的孙节点。

 

上代码:

var data3 = [
 {
 name: 'a',
 children: [
 { name: 'b', children: [{ name: 'e' }] },
 { name: 'c', children: [{ name: 'f' }] },
 { name: 'd', children: [{ name: 'g' }] },
 ],
 },
 {
 name: 'a2',
 children: [
 { name: 'b2', children: [{ name: 'e2' }] },
 { name: 'c2', children: [{ name: 'f2' }] },
 { name: 'd2', children: [{ name: 'g2' }] },
 ],
 }
]

// 深度遍历, 使用递归
function getName(data) {
let t1 = +new Date();
 const result = [];
 let index = 0
 data.forEach(item => {
 const map = data => {
 let tempO = {}
 tempO[data.name] = index;
 index ++
 result.push(tempO);
 data.children && data.children.forEach(child => map(child));
 }
 map(item);
 })
console.log(+new Date() - t1);
 return result;
}

// 广度遍历, 创建一个执行队列, 当队列为空的时候则结束
function getName2(data) {
 let t1 = +new Date();
 let result = [];
 let queue = data;
 let index = 0
 while (queue.length > 0) {
 [...queue].forEach(child => {
 queue.shift();
 let temp ={}; temp[child.name] = index;
 result.push(temp);
 index ++
 child.children && (queue.push(...child.children));
 });
 }
 console.log(+new Date() - t1);
 return result;
}

console.log(getName(data3))
console.log(getName2(data3))

对于算法来说 无非就是时间换空间 空间换时间

 

总结:

  1. 深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大
  2. 深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点
  3. 深度优先采用的是堆栈的形式, 即先进后出;广度优先则采用的是队列的形式, 即先进先出

 

使用:所以对于深度优先和广度优先,计算出来的结果是完全不一样的,实际运用可以根据需要进行选择。如果对顺序有要求的,可能需要按DFS来计算,如果对于顺序没有要求的,可以采用BFS

发表评论

记录工作生活点滴。

返回
顶部