一、定义
深度优先遍历（Depth-First Search，DFS）和广度优先遍历（Breadth-First Search，BFS）是两种主要的图或树结构的遍历算法。
DFS优先深入地探索一个节点的子节点，直到该节点的所有子节点都已被探索完，然后再回溯到该节点的同级节点进行探索；
BFS则优先探索一个节点的所有同级节点，再逐级向下探索。
在前端的工作中，如果遇到树形 DOM 结构、树型控件、级联选择等等需求，都需要使用到DFS和BFS。
二、算法步骤
2.1 树
树是一种分层数据的抽象模型，树可以看做是一种特殊的链表，只是链表只有一个 next 指向下一个节点，而树的每个节点都有多个 next 指向下一个节点。
一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点：
image.png
JavaScript 中没有树这种数据结构，但是可以用 Object 和 Array 来模拟一颗树。
const tree = {
value:"a",
children:[
{
value:"b",
children:[
{
value:"d",
children:[
{
value:"e",
children:[]
}
]
}
]
},
{
value:"c",
children:[
{
value:"f",
children:[]
},
{
value:"g",
children:[]
}
]
}
]
}
var 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",
},
],
},
],
},
];
2.2 深度优先遍历（DFS）
深度优先遍历，尽可能深的搜索树的分支。
image.png
image.png
序号表示被搜索的顺序，它的算法口诀是：
访问根节点；
对根节点的 children 挨个（递归）进行深度优先遍历。
# tree 为上述的结构
# 深度优先代码
const dfs = (node)=>{
console.log(node.value);
node.children.forEach(dfs);
}
# 调用
dfs(tree);
打印结果输出顺序： a、b、d、e、c、f、g 。
2.3 广度优先遍历（BFS）
广度优先遍历，先访问离根节点最近的节点。
image.png
序号表示被搜索的顺序，先把同层的节点给遍历完，再去遍历子节点。它的算法口诀是：
新建一个队列，把根节点入队；
把对头出队并访问；
把对头的 children 挨个入队；
重复（循环）第二、三步，直到队列为空。
const bfs = (root)=>{
# 根节点入队
const stack = [root];
# 只要栈不为空就一直循环
while (stack.length > 0){
# 取出栈首
const node = stack.shift();
# 遍历根节点，把它的子节点推入栈尾
node.children.forEach((item)=> stack.push(item));
# 打印节点值
console.log(node.value);
}
}
bfs(tree);
打印结果输出顺序： a、b、c、d、e、f、g 。
三、使用场景 & 应用案例
3.1 深度优先遍历
● 在图或树的复杂结构中搜索特定节点。
● 用于解决如迷宫搜索、寻找连通性组件等问题。
● 查找文件路径
● 二叉树的遍历
3.2 广度优先遍历
● 寻找最短路径，如无权重图的最近节点或社交网络中的度数。
● 逐层遍历，如层级结构的打印。
● 权限系统
● Web 爬虫(广度优先搜索也被应用在互联网搜索引擎的网页爬虫技术中，以尽可能广泛地爬取页面。)
四、优点和缺点
4.1深度优先遍历 (DFS):
优点：
- 路径检测：DFS 非常适合搜索所有可能的路径，因为它走的“更深”。
- 内存较少：相比 BFS，DFS 使用的内存较少。因为它只需要存储单条路径上的节点。
缺点：
- 时间较多：在某些情况下，尤其是在目标节点离初始节点较近时，或者在解决最短路径问题时， DFS 可能需要花费不必要的更多时间。
- 无限循环：在非树形图结构中，由于 DFS 偏向深入，可能遇到不断深入但找不到解的历史循环问 题。
深度优先遍历的优点在于能快速找到解决方案，且易于实现，但有可能陷入死循环或者掉入一些非最优的情况。
4.2广度优先遍历 (BFS):
优点：
- 最短路径：在树形或图形结构中，BFS 可以找到从根节点到目标节点的最短路径。
- 层级遍历：由于 BFS 是逐层遍历，因此很适用于需要按层级遍历的场合。
缺点：
- 内存：相比 DFS，BFS 使用的内存较多。尤其是在树的分支很多时，因为它需要存储整个扩展的节 点队列。
- 路径检测：在需要找到所有可能的路径时，BFS效率较低。
广度优先遍历可以找到最优解，特别是在需要找到最短路径的问题中，但可能需要更多的存储空间。
五、时间和空间复杂度
5.1 BFS（广度优先搜索）
- 时间复杂度：是O(V+E)，其中V是图中顶点（Vertex）的数量，E是图中边（Edge）的数量。这是因为在算法执行过程中，每个顶点和每条边都会被探查一次。
- 空间复杂度：是O(V)，其中V是图中的顶点的数量。在最坏的情况下，即在队列中存放了图的所有顶点，所以空间复杂度与顶点的数量有关。
5.2 DFS（深度优先搜索）
- 时间复杂度：是O(V+E)，其中V是图中顶点（Vertex）的数量，E是图中边（Edge）的数量。与BFS一样，这是因为在算法执行过程中，每个顶点和每条边都会被访问一次。
- 空间复杂度：是O(V)，其中V是图中的顶点的数量。在最坏的情况下，即在调用栈中存放了图的所有顶点，所以空间复杂度与顶点的数量有关。
注意：以上的复杂度分析都是基于邻接列表的图数据结构进行的。如果使用邻接矩阵，由于需要遍历每个点对应的所有边，因此BFS和DFS的时间复杂度会变为O(V^2)。
所以，当选择图的数据结构时（例如，邻接矩阵还是邻接列表），需要考虑到实际应用的特点，如图的稀疏或密集程度，以选择最优的数据结构，从而提高程序的效率。
六、 总结
深度优先遍历和广度优先遍历是两种基本且重要的图与树的遍历算法，选择使用哪一种遍历方法取决于问题的具体需求，理解它们的运作原理及适用场景是所有算法学习基础。
网友评论