广度优先搜索(BFS)算法是一种通过逐层遍历实现图或树结构搜索的经典方法,其核心代码通常包含队列数据结构、访问标记数组和循环迭代三要素。 该算法能高效解决最短路径、连通性检测等问题,Python实现仅需10-20行代码即可完成基础框架。
-
队列初始化
使用collections.deque()创建双端队列,将起始节点加入队列并标记为已访问。例如在迷宫问题中,队列初始化为起点坐标(0,0),同时建立二维数组visited记录访问状态。 -
循环处理队列
通过while循环持续处理队列直到为空,每次从队首取出当前节点。对于二叉树遍历,此时可打印节点值;在图搜索中则需获取该节点的所有未访问邻接节点。 -
邻接节点处理
检查当前节点的所有邻接节点,未访问的节点会被加入队列尾部并立即标记。网络爬虫应用时,这里会提取页面的所有新链接加入待抓取队列。 -
终止条件
队列为空时自动终止循环,此时所有可达节点均被处理。社交网络分析中,此阶段可输出某用户的三度好友关系图谱。
实际编写时需注意处理环形结构防止死循环,树结构可省略visited数组。算法时间复杂度为O(V+E),适合处理节点间距离均匀的场景,如地铁换乘方案计算。建议结合具体问题调整节点扩展逻辑和终止条件。