广度优先搜索(BFS)算法学习平台

📚 广度优先搜索算法原理

💡 什么是BFS？

广度优先搜索（Breadth-First Search, BFS）是一种用于图和树数据结构的遍历算法。它从根节点开始，逐层遍历所有相邻节点，直到找到目标节点或遍历完所有节点。

🎯 核心思想

BFS使用队列（Queue）数据结构来实现"先入先出"（FIFO）的遍历顺序。算法会优先访问距离起始节点最近的节点，再逐步扩展到更远的节点。

📝 算法步骤

将起始节点加入队列，并标记为已访问
当队列不为空时：
- 从队列头部取出一个节点
- 访问该节点的所有未访问邻居节点
- 将这些邻居节点加入队列，并标记为已访问
重复步骤2直到队列为空或找到目标节点

⚡ 特性与复杂度

✅ 可以找到从起始节点到目标节点的最短路径
⏱️ 时间复杂度：O(V + E)，其中V是节点数，E是边数
💾 空间复杂度：O(V)，最坏情况下需要存储所有节点

🌟 典型应用场景

🗺️ 最短路径查找（如地图导航）
🌐 网络拓扑发现
♟️ 棋盘游戏AI走法生成
👥 社交网络好友推荐
🦠 病毒传播模拟

🎬 BFS算法可视化演示

🎮 控制面板

🏃 演示速度

800ms

📋 操作说明

• 👆 点击节点可设置为起始点
• 🟡 橙色：队列中待访问
• 🟢 绿色：已访问完成
• 🔴 红色：当前正在访问

📦 当前队列 (Queue)

队列为空

💬 当前步骤

点击"开始演示"按钮开始BFS遍历 🚀

// BFS算法伪代码 ✨
function BFS(startNode):
    let queue = new Queue()
    let visited = new Set()
    
    queue.enqueue(startNode)
    visited.add(startNode)
    
    while queue is not empty:
        currentNode = queue.dequeue()
        // 处理当前节点 🔍
        visit(currentNode)
        
        for each neighbor in currentNode.neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)

✏️ 交互式练习

📝 练习题目

给定下面的图结构，从节点A出发，按照BFS算法的遍历顺序，依次选择要访问的节点。完成后点击"提交答案"按钮验证是否正确。

🎯 你的答案（点击节点按顺序选择）

请点击上方节点按BFS顺序选择 👆

💡 BFS小提示

💭 BFS是逐层遍历，同一层的节点顺序可以根据邻居顺序不同而有差异。
🔄 每个节点只会被访问一次，不要重复选择已经选过的节点。
📥 队列是先进先出结构，先进入队列的节点会被先取出访问。
🎯 BFS特别适合解决最短路径、最少步数这类问题。

🤔 拓展思考

想一想，如果图中存在环路，BFS为什么不会陷入死循环？如果我们想要找到从节点A到节点E的最短路径，BFS是如何保证找到的路径是最短的？