当我们谈论深度优先搜索（DFS）和广度优先搜索（BFS）时，我们通常在解决图或树相关问题时使用它们。
🧚🏻♀️简单理解为对树状结构的遍历-横向 、竖向
- 深度优先搜索为树状结构的横向执行，从第一行遍历子节点、叶子节点，依次直到最后一行。
- 广度优先搜索为树结构的竖向执行，把树结构平面铺开、以层级数为列数，从第一列依次执行。
深度优先搜索（DFS）的原理很简单：我们从起始节点开始，沿着一条路径不断向下探索，直到达到终点或者无法继续为止。如果遇到终点，就找到了一条路径；如果无法继续，则回溯到上一个节点，然后尝试探索其他路径。这个过程会递归地进行，或者使用栈来存储节点的顺序。
相比之下，广度优先搜索（BFS）的原理稍微有些不同：我们从起始节点开始，逐层地访问其邻居节点。也就是说，我们首先访问起始节点的邻居节点，然后是邻居节点的邻居节点，依此类推，直到遍历完所有节点或者找到目标节点为止。为了遍历节点的顺序，我们使用队列数据结构。
- DFS：深度优先搜索可以用于找到一条路径、判断图中是否存在循环、拓扑排序、生成连通分量等。
- BFS：广度优先搜索可以用于找到最短路径、生成最小生成树、进行网络分析等。
深度优先搜索（DFS）示例代码：
// 图的邻接表表示 const graph = { A: ['B', 'C'], B: ['D', 'E'], C: ['F', 'G'], D: [], E: [], F: [], G: [] }; // 使用深度优先搜索遍历图 function dfs(graph, start) { const visited = new Set(); // 存储已访问节点的集合 function traverse(node) { visited.add(node); // 将当前节点标记为已访问 console.log(node); // 打印遍历的节点 const neighbors = graph[node]; // 获取当前节点的邻居节点 for (const neighbor of neighbors) { // 遍历当前节点的邻居节点 if (!visited.has(neighbor)) { // 如果邻居节点未被访问过 traverse(neighbor); // 递归遍历邻居节点 } } } traverse(start); // 从起始节点开始进行深度优先搜索 return visited; // 返回所有已访问的节点 } dfs(graph, 'A'); // 对图进行深度优先搜索，从起始节点 'A' 开始，并打印遍历结果
在上述代码中，图使用邻接表表示，dfs 函数使用递归方式实现了深度优先搜索。从起始节点 'A' 开始，递归访问其邻居节点，并在访问时输出节点的值。
广度优先搜索（BFS）示例代码：
// 广度搜索 BFS let graph = { 'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'D', 'E'], 'D': ['B', 'C', 'E'], 'E': ['C', 'D', 'F'], 'F': ['E','W'], 'W':['C'] }; function bfs(graph, startPoint) { let queue = []; // 用于存储待访问节点的队列 let result = []; // 存储遍历结果的数组 queue.push(startPoint); // 将起始节点添加到队列 result.push(startPoint); // 将起始节点添加到遍历结果 while (queue.length > 0) { // 当队列不为空时进行循环 let point = queue.shift(); // 取出队列中的第一个节点作为当前节点 let nodes = graph[point]; // 获取当前节点的所有邻居节点 for (let node of nodes) { // 遍历当前节点的邻居节点 if (result.includes(node)) continue; // 如果邻居节点已经在遍历结果中，则跳过 result.push(node); // 将邻居节点添加到遍历结果中 queue.push(node); // 将邻居节点添加到队列中，以便后续访问其邻居节点 } } return result; // 返回遍历结果 } console.log(bfs(graph, 'B')); // 执行广度优先搜索，从起始节点 'B' 开始，并输出遍历结果
在上述代码中，图使用邻接表表示，bfs 函数使用队列实现了广度优先搜索。从起始节点 'A' 开始，将其加入队列并标记为已访问，然后依次从队列中取出节点，并访问其邻居节点，同时将邻居节点加入队列中，直到队列为空。
案例
深度优先搜索（DFS）和广度优先搜索（BFS）在前端项目中有许多实际的应用场景。下面有两个常见的前端开发项目案例
1、组件树遍历
在前端开发中，经常会有需要对组件树进行遍历的场景，例如渲染组件、查找组件等。下面是一个使用DFS进行组件树遍历的示例：
function dfs_component_traversal(component) { console.log(component); // 处理当前组件 if (component.children) { for (const child of component.children) { dfs_component_traversal(child); // 递归遍历子组件 } } }
以上的代码展示了一个使用深度优先搜索进行组件树遍历的函数。我们可以根据组件的层级关系，从根组件开始递归地遍历每个组件及其子组件，以实现对整个组件树的遍历和操作。
这个算法可以帮助我们在前端项目中处理组件之间的关系，例如渲染组件、查找相关组件等。通过对组件树的深度遍历，我们可以有序地处理组件及其子组件，并执行相应的操作。
2、页面导航
在前端开发中，页面导航是一个常见的需求。我们可以使用广度优先搜索来实现页面导航功能，以确保按照层级关系有序地展示页面。
function bfs_page_navigation(page) { const queue = [page]; // 使用队列作为辅助数据结构来进行广度优先搜索 while (queue.length > 0) { const current = queue.shift(); // 移除队列头部元素作为当前页面 console.log(current); // 处理当前页面 for (const child of current.children) { queue.push(child); // 将子页面加入队列 } } }
以上代码展示了一个使用广度优先搜索进行页面导航的函数。在这个函数中，我们使用队列作为辅助数据结构来进行广度优先搜索。通过不断将子页面加入队列，并按照队列中的顺序处理每个页面，可以实现按照层级关系有序地导航页面。
更多示例
const root = { value: 1, children: [ { value: 2, children: [], }, { value: 3, children: [ { value: 7, children: [ { value: 8, children: [], }, ], }, ], }, { value: 4, children: [ { value: 6, children: [], }, ], }, ], }; // 在深度优先搜索 - 堆 // 我们首先处理当前节点，然后递归地处理每个子节点、直到叶子节点（没有子节点的节点），最后依次遍历完成 const digui = (node)=>{ console.log(node.value) if(node.children){ for(const children of node.children){ digui(children) } } } // 广度优先搜索-栈，把多维树结构，取出来平铺，依次访问。 // 在广度优先搜索中，我们使用队列来保存待访问的节点，确保按照层级顺序进行遍历。 // 每次从队列中取出队头节点，处理该节点后，将其邻居节点（子节点）入队，以便后续遍历。这样，就可以依次访问所有节点，并保持层级顺序。 function breadthFirstSearch(root) { if (!root) { return; } const queue = []; // 创建一个空队列，用于存放待访问的节点 queue.push(root); // 将根节点入队 while (queue.length !== 0) { // 当队列不为空时循环执行以下步骤 const current = queue.shift(); // 出队队头节点作为当前节点 console.log(current.value); // 进行二次加工或其他操作，这里简单地输出节点的值 for (const child of current.children) { // 遍历当前节点的邻居节点（子节点） queue.push(child); // 将未访问过的邻居节点入队 } } } console.log(digui(root)) console.log(breadthFirstSearch(root))
