当前位置：首页 > article >正文

深度优先和广度优先【栈、堆前端举例】

article 2025/1/14 13:54:12

深度优先和广度优先：

深度优先搜索（DFS）和广度优先搜索（BFS）是两种用于图和树遍历的算法，它们各自有不同的应用场景和特点。

深度优先 DFS：

‌深度优先搜索（DFS）‌ 的核心思想是“深入探索，直至无路可走，然后再回溯”。它从起始节点开始，沿着一条路径一直遍历到最后一个节点，然后回溯到上一个节点继续遍历其他路径。DFS适合用于查找目标节点在深度较大的情况下，可以节省存储空间，但可能导致无限循环。DFS的实现通常使用递归或栈，它适用于需要探索所有路径的场景，如解决迷宫问题、检测图中的环、拓扑排序、图的连通性问题等‌。

深度优先在二叉树上三种遍历顺序：

先序遍历（前序遍历）‌：

遍历顺序：根节点 -> 左子树 -> 右子树。
在先序遍历中，首先访问的是根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。

中序遍历‌：

遍历顺序：左子树 -> 根节点 -> 右子树。
在中序遍历中，首先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。这种遍历方式也被称为对称遍历。

后序遍历‌：

遍历顺序：左子树 -> 右子树 -> 根节点。
在后序遍历中，首先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。

广度优先 BFS：

‌广度优先搜索（BFS）‌ 则是一层一层往下遍历，即先访问当前层的所有节点，然后再访问下一层的所有节点。BFS适合用于查找目标节点在深度较小的情况下，可以找到最短路径（在无权图中），但需要较多的存储空间。BFS的实现通常使用队列，它适用于寻找最短路径的场景，如在无权图中寻找最短路径、社交网络中的朋友推荐、人际关系分析等‌。

‌队列：

队列是一种先进先出（FIFO）的数据结构‌，从任务调度到消息处理系统，队列都起着至关重要的作用。**在队列中，元素被按照加入的顺序排列，先加入的元素会先被移除。**队列的基本操作包括入队（enqueue），即在队列尾部添加一个元素；出队（dequeue），即移除队列头部的元素；以及查看队首（peek），即获取队列头部的元素但不移除；还有检查是否为空（isEmpty），即判断队列是否没有元素‌。

队列的应用例子：任务队列

队列是一种先进先出的数据结构，非常适合用于任务队列的管理。例如，在前端开发中，我们可能需要按顺序执行多个异步任务，如多个API请求或动画序列。

class TaskQueue {
    constructor() {
        this.queue = [];
    }

    enqueue(task) {
        this.queue.push(task);
    }

    dequeue() {
        // 删除开头元素
        return this.queue.shift();
    }

    isEmpty() {
        return this.queue.length === 0;
    }
}

// 使用示例
let taskQueue = new TaskQueue();

// 模拟异步任务，如API请求
function asyncTask(id) {
    return new Promise((resolve) => {
        setTimeout(() => {
            console.log(`Task ${id} completed`);
            resolve();
        }, 1000);
    });
}

// 将任务加入队列
taskQueue.enqueue(asyncTask(1));
taskQueue.enqueue(asyncTask(2));
taskQueue.enqueue(asyncTask(3));

// 按顺序执行队列中的任务
async function processQueue() {
    while (!taskQueue.isEmpty()) {
        await taskQueue.dequeue();
    }
}

processQueue();

栈：

‌栈则是一种后进先出（LIFO）的数据结构‌，它适合用于需要后进先出的场景，如深度优先搜索（DFS）中的回溯策略。在栈中，最后加入的元素会最先被移除。栈的基本操作包括入栈（push），即将元素添加到栈顶；出栈（pop），即移除栈顶的元素；以及查看栈顶元素（peek）等‌

栈的应用例子之浏览器历史记录：

栈是一种后进先出的数据结构，非常适合模拟浏览器的“后退”功能。每当用户访问一个新的网页时，我们可以将该网页的信息入栈。当用户想要返回上一页时，我们可以从栈中弹出最近访问的网页信息，从而实现类似后退功能的效果。

class BrowserHistoryStack {
    constructor() {
        this.stack = [];
    }

    push(page) {
        this.stack.push(page);
    }

    pop() {
        return this.stack.pop();
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    isEmpty() {
        return this.stack.length === 0;
    }
}

// 使用示例
let history = new BrowserHistoryStack();
history.push('homePage');
history.push('aboutPage');
console.log(history.pop()); // 输出: aboutPage
console.log(history.top()); // 输出: homePage
console.log(history.isEmpty()); // 输出: false