广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。
广度优先搜索算法主要有四个特性：
空间复杂度：由于对空间的大量需求，因此BFS并不适合解非常大的问题，对于类似的问题，应用IDDFS已达节省空间的效果。
时间复杂度：最差情形下，BFS必须查找所有到可能节点的所有路径。
完全性：广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。
最佳解：若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，BFS仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS的改良算法成本一致搜索法来解决。然而，若非加权图形，则所有边的长度相等，BFS就能找到最近的最佳解。
最后，广度优先搜索是可以于计算机游戏中平面网络的。
BFS可用来解决计算机游戏（例如即时策略游戏）中找寻路径的问题。在这个应用中，使用平面网格来代替图形，而一个格子即是图中的一个节点。所有节点都与它的邻居（上、下、左、右、左上、右上、左下、右下）相接。
值得一提的是，当这样使用BFS算法时，首先要先检验上、下、左、右的邻居节点，再检验左上、右上、左下、右下的邻居节点。这是因为BFS趋向于先查找斜向邻居节点，而不是四方的邻居节点，因此找到的路径将不正确。BFS应该先查找四方邻居节点，接着才查找斜向邻居节点1。
———-
欢迎加入小红圈，分享更多有价值的内容。
小红圈是一款专注于知识内容产出、沉淀的社群管理工具，为用户提供便捷的社群运营管理功能和内容变现渠道，基于微信公众号、小程序、App客户端三种使用场景，可帮助内容创作者们一分钟快速搭建专属的付费社群。