BFS

1. 从根节点开始,首先访问该节点。
2. 然后依次访问它所有的相邻节点(这些节点是第二层)。
3. 再依次访问这些相邻节点的所有相邻节点(这些节点是第三层)。
4. 以此类推,直到遍历完所有节点。

特点:

1. 最短路径 - BFS可以找到根节点到其他节点的最短路径。
2. 层级遍历 - 可以按层级遍历一个图。
3. 无回路图保证遍历全部节点 - 在无回路的图中,BFS保证遍历所有节点而且不会陷入无限循环。

应用场景:

1. 最短路径问题 - 比如网络路由寻址
2. 网页爬虫 - 从根URL开始按层级遍历所有链接页面
3. 解决棋盘问题 - 比如模拟推箱子等游戏