跳到主内容

深度优先搜索和广度优先搜索 - Javascript版本

深度优先搜索和广度优先搜索是指在一个图中,从一个节点出发,搜索所有节点,并且按照深度优先搜索的方式进行搜索,下图展示了深度优先搜索和广度优先搜索的例子

DFS和BFS

可以看出,深度优先是先从上到下的,然后从左到右的遍历,广度优先是先从左到右,然后从上到下的遍历,下面我们来实践一下

给出一个数据结构如下的数据

const data = [
{
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 dfs(data) {
let ret = [];
for (let i = 0; i < data.length; i++) {
const item = data[i];
ret.push(item.name);
if (item.children) {
// 如果有孩子,递归获取结果
ret = ret.concat(dfs(item.children));
}
}
return ret;
}

//  ['a', 'b', 'e', 'c', 'f', 'd', 'g', 'a2', 'b2', 'e2', 'c2', 'f2', 'd2', 'g2']

广度优先遍历

广度优先遍历一般通过队列来实现,先进先出

function bfs(data) {
if (data.length === 0) return [];
const ret = [];
const queue = data.slice(); // 拷贝一份,避免副作用
while (queue.length) {
// 出队
const item = queue.shift();
ret.push(item.name);
if (item.children) {
// 按顺序有孩子就入队
queue.push(...item.children);
}
}
return ret;
}
//  ['a', 'a2', 'b', 'c', 'd', 'b2', 'c2', 'd2', 'e', 'f', 'g', 'e2', 'f2', 'g2']